如何实现只有堆栈实现的队列？

Question

我知道有2个堆栈但是怎么用一个？

Answer 1

您可以通过使用递归函数调用来"欺骗"弹出堆栈,然后推送正在排队的项目,然后在递归调用展开时按下弹出的内容.但这实际上是两个堆栈,因为系统程序计数器是一个堆栈.

Answer 2

下面是java的实现：

• 在Enqueue操作时，我们可以直接将元素压入堆栈。

• 在出队操作期间，

  • 递归地从主堆栈中弹出所有元素，直到堆栈大小等于 1。
  • 如果堆栈大小 = 1，则从堆栈中弹出项目，并返回相同的项目。
  • 将所有弹出的元素推回堆栈。

下面是经过测试的程序。

public class QueueUsingSingleStack {

    Stack<Integer> stack = new Stack<>();

    private void enqueue(int i) {
        stack.push(i);
    }

    private int dequeue() throws Exception {
        if (stack.size() == 0)
            throw new Exception("Queue is Empty");

        if (stack.size() == 1)
            return stack.pop();

        int data = stack.pop();
        int retVal = dequeue();
        stack.push(data);
        return retVal;
    }

    public static void main(String[] args) throws Exception {
        QueueUsingSingleStack queue = new QueueUsingSingleStack();
        queue.enqueue(10);
        queue.enqueue(20);
        queue.enqueue(30);
        queue.enqueue(40);

        System.out.println(queue.dequeue());
        System.out.println(queue.dequeue());
        System.out.println(queue.dequeue());
        System.out.println(queue.dequeue());

    }

}