【算法】栈与队列的相互成全

前置知识

• 数据结构—栈与队列。
• 编程语言:Java，但不用任何容器，只用数组。容器版本的读者应该在学习数据结构时实现过了。

题目1:用栈实现队列

• 回顾， 栈的特点是后进先出，队列的特点是先进先出。
• 我们要用栈中的push，pop,peek,isEmpty操作实现队列中的offer,poll,peek,isEmpty.

题目1解决方案

假设栈是[1,2,3,4,5]的序列，栈顶元素是5。从栈的角度，出栈顺序应该是[5,4,3,2,1]。 但是我们逻辑上要搞队列， 那么删除序列应该是先进栈的先出来实现队列的效果， 出栈序列应该是[1,2,3,4,5]。 对吧？！！

假设我们有两个栈， 分别是stackPush和stackPop。进栈从stackPush进入，然后把栈中元素倒入stackPop中， 这样就实现了逆序了， 然后由stackPop进行输出。

话虽如此，但还是不够细节。
下面继续捋一下细节
入栈:无脑入stackPush。
出栈：从stackPop输出。
入栈出栈后应该还有一个额外的倒栈操作，pushToPop。什么情况下需要倒入呢？答案很明显， 如果输出栈stackPop为空则需要倒入元素。
倒入元素时还需要注意，必须把输入栈`stackPush·倒完。

总结
1. 如果stackPop为空，则允许倒入， 否则不能倒入， 因为会破坏输出的序列。请自行举例论证。
2. 如果要从stackPush倒入到stackPop，则需要一次性的倒完所有数据， 否则后续元素入栈再倒入会打乱输出序列。

代码部分

class MyQueue {
public static int MAX = 101;//题目最多压栈100次，全局数组最大100.
public static int[] stackPush = new int[MAX];
public static int pushSize;
public static int[] stackPop = new int[MAX];
public static int popSize;
    public MyQueue() {
    pushSize = popSize = 0;
    }
    private static void pushToPop() {
    //输出栈为空， 则执行
    if(popSize==0) {
    //倒入数据
    while(pushSize>0) {
    stackPop[popSize++] = stackPush[--pushSize];
    }
    }
    }
    public void push(int x) {
    stackPush[pushSize++] = x;
    pushToPop();//这里也要倒栈处理
    }
    
     public int pop() {
    int ret = stackPop[--popSize];
    pushToPop();//这里要倒栈处理
    return ret;
    }
    
    public int peek() {
    return stackPop[popSize-1];
    }
    
    public boolean empty() {
    return pushSize == 0 && popSize == 0;
    }
}

后续问题：你能否实现队列，使得每个操作都具有分摊的 O(1)时间复杂度？换句话说，即使其中一个操作可能需要更长的时间，执行n操作也将花费总的时间。O(n)。
上面的实现就是最快的，每个对象各自入栈出栈各自2次，一共4次。常量时间。
pushToPop摊还时间也是$O(1)$。单次开销可能$O(n)$,但均摊每个元素， 对于每个元素只倒一次。平均来看也是常量时间。

题目2:用队列实现栈

队列是一种先进先出的结构。

• 我们要用队列中的offer,poll,peek,isEmpty实现栈中的push，pop,peek,isEmpty。
• 我们还是要用数组实现，不过要避开所有与队列无关的操作行为。

假设有一组序列[a,b,c,d,e]。

• [a] 入队。
• [a,b] b元素入队， 但由于队列先进先出的特性， 此时出队就会是a，不可能是b。那么怎么做？就让a出队，再让a入队。那么序列变为[b,a], 调整之后，输出序列就满足栈的输出了。
• c入队， [b,a,c]。此时，按照栈的角度，输出应该是c，然后是b,最后是a。怎么做？ 让c前面的b,a出队在入队。 那么整体出队输出序列就是[c,b,a]逻辑上输出就是栈了。
• …

虽然使用的数组模拟队列实现，但全程只涉及了队列操作。100%perfect.

class MyStack {
public static int MAX = 100;
public static final int[] queue = new int[MAX];
public static int r,l;
public static int size;
    public MyStack() {
    l = r = size = 0;
    }
    
    public void push(int x) {
    int n = size;
    queue[r++] = x;
    r %= MAX;
    size++;
    while(n>0) {
    queue[r++] = queue[l++];
    l %= MAX;
    --n;
    }
    }
    
    public int pop() {
    int ret = queue[l];
    l = (l+1)%MAX;
    size--;
    return ret;
    }
    
    public int top() {
    return queue[l];
    }
    
    public boolean empty() {
    return size==0;
    }
}

单次push操作是$O(n)$, 入队后将所有入队元素前的所有元素重新入队相当于遍历一遍队列。其余操作均是常量时间。
这就是单队列实现栈的最优解了。
结束.
坚持。

原文地址：https://blog.csdn.net/2303_79972050/article/details/142989010

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！