阅读:0       作者:严长生

栈实现队列,用两个栈实现队列方法详解(含实现代码)

栈怎样才能实现和队列一样从栈的底层抽出元素呢?一般会用两个栈来实现队列。

首先,我们将两个栈分别定义为 stack1 与 stack2。

实现方案 1

我们让入队操作在 stack1 中执行,而出队操作在 stack2 中执行。执行方式如下。
  • 入队:直接向 stack1 中入栈。
  • 出队:将 stack1 中的所有元素出栈,依次入栈到 stack2 中,然后弹出 stack2 中的栈顶元素,接着把 stack2 中的所有元素出栈,依次压入 stack1 中。

为了便于理解,我们借助图 1 解释上述入队操作。


图 1 入队操作

出队操作如图 2 所示。


图 2 出队操作

来回入队、出队比较烦琐,尤其是出队比较麻烦,需要先将元素从 stack1 倒入 stack2 里,然后在 stack2 弹出元素之后又倒回到 stack1 里。有没有更好的办法呢?当然有,方案 2 就是改进之后的思路。

实现方案 2

入队都在 stack1 中进行,stack2 用于出队,同时保证所有元素都在一个栈里,且遵守以下规则。
  • 入队:不管 stack1 是否为空栈,都将 stack2 中的所有元素压入 stack1 中。
  • 出队:若 stack2 不为空栈,则直接从 stack2 中弹出元素;若 stack2 为空栈,则把 stack1 中的元素倒入 stack2 中,再从 stack2 中弹出元素;若两个栈都是空的,则说明队列为空队,不能出队。这与方案 1 的思路一样,只不过把倒回去的这个操作放到了入队时执行,却使连续入队、出队的效率提高了。

还有更好的办法吗?当然有。方案 3 就是一种更优的解决办法。

实现方案 3

入队都在 stack1 中进行,出队在 stack2 中进行,同时遵守以下规则。
  • 入队:直接把元素压入 stack1 中。
  • 出队:如果 stack2 不为空,则直接弹出 stack2 中的元素;如果 stack2 为空,则将 stack1 中的所有元素倒入 stack2 中,然后弹出 stack2 中的栈顶元素。同样,若两个栈都为空栈,则队列为空队,无法出队。

这个方案在入队时非常简单,而在出队时,多数情况下可以直接通过出队 stack2 实现,若需要把 stack1 中的元素倒入 stack2 中,则一般不用每次都进行这样操作。最坏的情况就是出队一个元素、入队一个元素这样的循环操作,导致每次出队都要转移元素。

其实这三种方案的操作是一样的。总体来说,方案 3 是非常好的方案。

下面为方案 3 的代码实现。
package me.irfen.algorithm.ch02.extend;
import me.irfen.algorithm.ch02.Stack;
public class Stack2Queue {
    private Stack stack1;
    private Stack stack2;
    private int maxLength;

    public Stack2Queue(int capacity) {
        maxLength = capacity;
        stack1 = new Stack(capacity);
        stack2 = new Stack(capacity);
    }

    public boolean put(int item) {
        if (stack1.isFull() || maxLength == size()) {
            // 满了
            return false;
        }
        stack1.push(item);
        return true;
    }

    public int poll() {
        if (!stack2.isEmpty()) {
            return stack2.pop();
        } else {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
            return stack2.pop();
        }
    }

    public int size() {
        return stack1.size() + stack2.size();
    }
}
下面是测试代码:
package me.irfen.algorithm.ch02.extend;
public class Stack2QueueTest {
    public static void main(String[] args) {
        Stack2Queue queue = new Stack2Queue(5);
    queue.put(1);
    queue.put(2);
    System.out.println(queue.poll()); // 1
    queue.put(3);
    queue.put(4);
    System.out.println(queue.poll()); // 2
    System.out.println(queue.poll()); // 3,本次会把3、4两个元素从stack1倒入stack2
}
}