使用堆栈实现队列的以下操作。

push(x)——将元素x推到队列的后面。

pop()——从队列前面移除元素。

peek()——获取前端元素。

empty()——返回队列是否为空。

class MyQueue {

  Stack<Integer> input;
  Stack<Integer> output;

  /** Initialize your data structure here. */
  public MyQueue() {
    input = new Stack<Integer>();
    output = new Stack<Integer>();
  }

  /** Push element x to the back of queue. */
  public void push(int x) {
    input.push(x);
  }

  /** Removes the element from in front of queue and returns that element. */
  public int pop() {
    peek();
    return output.pop();
  }

  /** Get the front element. */
  public int peek() {
    if(output.isEmpty()) {
        while(!input.isEmpty()) {
            output.push(input.pop());
        }
    }
    return output.peek();
  }

  /** Returns whether the queue is empty. */
  public boolean empty() {
    return input.isEmpty() && output.isEmpty();
  }
}

如何反转堆栈

要理解如何使用两个堆栈构造队列，您应该清楚地了解如何反转堆栈。记住堆叠是如何工作的，它非常类似于你厨房里的盘子堆。最后洗完的盘子会放在干净盘子堆的最上面，这在计算机科学中被称为后进先出(LIFO)。

让我们想象我们的堆栈像一个瓶子，如下所示;

如果我们分别压入整数1,2,3，那么3将在堆栈的顶部。因为1会先被推，然后2会被放在1的上面。最后，将3放在堆栈的顶部，我们的堆栈的最新状态表示为一个瓶子，如下所示;

现在我们的堆栈表示为一个装满值3,2,1的瓶子。我们想要反转堆栈使堆栈顶部的元素为1而堆栈底部的元素为3。我们能做什么?我们可以拿起瓶子，把它倒着拿，这样所有的值都应该按顺序颠倒?

是的，我们可以这样做，但那是一个瓶子。为了完成同样的过程，我们需要有第二个堆栈，它将以相反的顺序存储第一个堆栈元素。让我们把已填充的堆栈放到左边，把新的空堆栈放到右边。为了颠倒元素的顺序，我们将从左堆栈中取出每个元素，并将它们推入右堆栈。你可以在下图中看到我们这样做时发生了什么;

我们知道如何反转堆栈。

使用两个堆栈作为队列

On previous part, I've explained how can we reverse the order of stack elements. This was important, because if we push and pop elements to the stack, the output will be exactly in reverse order of a queue. Thinking on an example, let's push the array of integers {1, 2, 3, 4, 5} to a stack. If we pop the elements and print them until the stack is empty, we will get the array in the reverse order of pushing order, which will be {5, 4, 3, 2, 1} Remember that for the same input, if we dequeue the queue until the queue is empty, the output will be {1, 2, 3, 4, 5}. So it is obvious that for the same input order of elements, output of the queue is exactly reverse of the output of a stack. As we know how to reverse a stack using an extra stack, we can construct a queue using two stacks.

我们的队列模型将由两个堆栈组成。一个堆栈将用于入队操作(左边的堆栈#1，将被称为输入堆栈)，另一个堆栈将用于出队操作(右边的堆栈#2，将被称为输出堆栈)。看看下面的图片;

我们的伪代码如下;

---

入队操作

Push every input element to the Input Stack

出列操作

If ( Output Stack is Empty)
    pop every element in the Input Stack
    and push them to the Output Stack until Input Stack is Empty

pop from Output Stack

---

让我们分别将整数{1,2,3}编入队列。整数将被压入位于左侧的输入堆栈(堆栈#1);

那么如果执行出队列操作会发生什么呢?每当执行出队列操作时，queue将检查输出堆栈是否为空(参见上面的伪代码)。如果输出堆栈为空，则输入堆栈将在输出上提取，因此输入堆栈的元素将反转。在返回值之前，队列的状态如下所示;

检查输出堆栈(堆栈#2)中元素的顺序。很明显，我们可以从输出堆栈中弹出元素，这样输出将与从队列中退出队列时相同。因此，如果我们执行两次出队列操作，首先我们将分别获得{1,2}。那么元素3将是输出堆栈中唯一的元素，而输入堆栈将为空。如果我们将元素4和5编入队列，那么队列的状态将如下所示;

现在输出堆栈不是空的，如果我们执行出队列操作，只有3个将从输出堆栈中弹出。这样的状态如下所示;

同样，如果我们再执行两个出队列操作，在第一个出队列操作时，queue将检查Output Stack是否为空，这是true。然后弹出输入堆栈的元素，并将它们推到输出堆栈，直到输入堆栈为空，然后队列的状态将如下所示;

很容易看出，两个出队列操作的输出将是{4,5}

用两个栈构造队列的实现

下面是Java中的一个实现。我不打算使用现有的Stack实现所以这里的示例将会重新发明轮子;

C - 1) MyStack类:简单的堆栈实现

public class MyStack<T> {

    // inner generic Node class
    private class Node<T> {
        T data;
        Node<T> next;

        public Node(T data) {
            this.data = data;
        }
    }

    private Node<T> head;
    private int size;

    public void push(T e) {
        Node<T> newElem = new Node(e);

        if(head == null) {
            head = newElem;
        } else {
            newElem.next = head;
            head = newElem;     // new elem on the top of the stack
        }

        size++;
    }

    public T pop() {
        if(head == null)
            return null;

        T elem = head.data;
        head = head.next;   // top of the stack is head.next

        size--;

        return elem;
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public void printStack() {
        System.out.print("Stack: ");

        if(size == 0)
            System.out.print("Empty !");
        else
            for(Node<T> temp = head; temp != null; temp = temp.next)
                System.out.printf("%s ", temp.data);

        System.out.printf("\n");
    }
}

C - 2) MyQueue类:使用两个堆栈的队列实现

public class MyQueue<T> {

    private MyStack<T> inputStack;      // for enqueue
    private MyStack<T> outputStack;     // for dequeue
    private int size;

    public MyQueue() {
        inputStack = new MyStack<>();
        outputStack = new MyStack<>();
    }

    public void enqueue(T e) {
        inputStack.push(e);
        size++;
    }

    public T dequeue() {
        // fill out all the Input if output stack is empty
        if(outputStack.isEmpty())
            while(!inputStack.isEmpty())
                outputStack.push(inputStack.pop());

        T temp = null;
        if(!outputStack.isEmpty()) {
            temp = outputStack.pop();
            size--;
        }

        return temp;
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

}

C - 3)演示代码

public class TestMyQueue {

    public static void main(String[] args) {
        MyQueue<Integer> queue = new MyQueue<>();

        // enqueue integers 1..3
        for(int i = 1; i <= 3; i++)
            queue.enqueue(i);

        // execute 2 dequeue operations 
        for(int i = 0; i < 2; i++)
            System.out.println("Dequeued: " + queue.dequeue());

        // enqueue integers 4..5
        for(int i = 4; i <= 5; i++)
            queue.enqueue(i);

        // dequeue the rest
        while(!queue.isEmpty())
            System.out.println("Dequeued: " + queue.dequeue());
    }

}

C - 4)样品输出

Dequeued: 1
Dequeued: 2
Dequeued: 3
Dequeued: 4
Dequeued: 5

使用堆栈实现队列的以下操作。

push(x)——将元素x推到队列的后面。

pop()——从队列前面移除元素。

peek()——获取前端元素。

empty()——返回队列是否为空。

class MyQueue {

  Stack<Integer> input;
  Stack<Integer> output;

  /** Initialize your data structure here. */
  public MyQueue() {
    input = new Stack<Integer>();
    output = new Stack<Integer>();
  }

  /** Push element x to the back of queue. */
  public void push(int x) {
    input.push(x);
  }

  /** Removes the element from in front of queue and returns that element. */
  public int pop() {
    peek();
    return output.pop();
  }

  /** Get the front element. */
  public int peek() {
    if(output.isEmpty()) {
        while(!input.isEmpty()) {
            output.push(input.pop());
        }
    }
    return output.peek();
  }

  /** Returns whether the queue is empty. */
  public boolean empty() {
    return input.isEmpty() && output.isEmpty();
  }
}

我的PHP解决方案

<?php
$_fp = fopen("php://stdin", "r");
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
    $queue = array();
    $count = 0;
    while($line = fgets($_fp)) {
        if($count == 0) {
            $noOfElement = $line;
            $count++;
            continue;
        }
        $action = explode(" ",$line);
        $case = $action[0];
        switch($case) {
            case 1:
                $enqueueValue = $action[1];
                array_push($queue, $enqueueValue);
                break;
            case 2:
                array_shift($queue);
                break;
            case 3:
                $show = reset($queue);
                print_r($show);
                break;
            default:
                break;
        }
    }
?>

我将在Go中回答这个问题，因为Go在其标准库中没有丰富的集合。

由于堆栈真的很容易实现，我想我应该尝试使用两个堆栈来完成一个双端队列。为了更好地理解我是如何得到我的答案的，我将实现分为两部分，第一部分希望更容易理解，但它是不完整的。

type IntQueue struct {
    front       []int
    back        []int
}

func (q *IntQueue) PushFront(v int) {
    q.front = append(q.front, v)
}

func (q *IntQueue) Front() int {
    if len(q.front) > 0 {
        return q.front[len(q.front)-1]
    } else {
        return q.back[0]
    }
}

func (q *IntQueue) PopFront() {
    if len(q.front) > 0 {
        q.front = q.front[:len(q.front)-1]
    } else {
        q.back = q.back[1:]
    }
}

func (q *IntQueue) PushBack(v int) {
    q.back = append(q.back, v)
}

func (q *IntQueue) Back() int {
    if len(q.back) > 0 {
        return q.back[len(q.back)-1]
    } else {
        return q.front[0]
    }
}

func (q *IntQueue) PopBack() {
    if len(q.back) > 0 {
        q.back = q.back[:len(q.back)-1]
    } else {
        q.front = q.front[1:]
    }
}

它基本上是两个堆栈，我们允许堆栈的底部相互操纵。我还使用了STL命名约定，其中堆栈的传统push、pop、peek操作都有一个front/back前缀，无论它们是指队列的前面还是后面。

上面代码的问题是它没有非常有效地使用内存。事实上，它会不断增长，直到空间耗尽。这太糟糕了。解决这个问题的方法是尽可能重用堆栈空间的底部。我们必须引入一个偏移量来跟踪这一点，因为围棋中的切片一旦收缩就不能在前面生长。

type IntQueue struct {
    front       []int
    frontOffset int
    back        []int
    backOffset  int
}

func (q *IntQueue) PushFront(v int) {
    if q.backOffset > 0 {
        i := q.backOffset - 1
        q.back[i] = v
        q.backOffset = i
    } else {
        q.front = append(q.front, v)
    }
}

func (q *IntQueue) Front() int {
    if len(q.front) > 0 {
        return q.front[len(q.front)-1]
    } else {
        return q.back[q.backOffset]
    }
}

func (q *IntQueue) PopFront() {
    if len(q.front) > 0 {
        q.front = q.front[:len(q.front)-1]
    } else {
        if len(q.back) > 0 {
            q.backOffset++
        } else {
            panic("Cannot pop front of empty queue.")
        }
    }
}

func (q *IntQueue) PushBack(v int) {
    if q.frontOffset > 0 {
        i := q.frontOffset - 1
        q.front[i] = v
        q.frontOffset = i
    } else {
        q.back = append(q.back, v)
    }
}

func (q *IntQueue) Back() int {
    if len(q.back) > 0 {
        return q.back[len(q.back)-1]
    } else {
        return q.front[q.frontOffset]
    }
}

func (q *IntQueue) PopBack() {
    if len(q.back) > 0 {
        q.back = q.back[:len(q.back)-1]
    } else {
        if len(q.front) > 0 {
            q.frontOffset++
        } else {
            panic("Cannot pop back of empty queue.")
        }
    }
}

有很多小函数，但6个函数中有3个只是另一个的镜像。

不过，时间的复杂性会更糟。一个好的队列实现在常数时间内完成所有事情。

Edit

不知道为什么我的答案在这里被否决了。如果我们编程，我们会关心时间复杂度，使用两个标准堆栈来创建队列是低效的。这是一个非常有效和相关的观点。如果有人觉得有必要再投反对票，我很想知道为什么。

更详细一点:关于为什么使用两个堆栈比使用一个队列更糟糕:如果您使用两个堆栈，并且有人在发件箱为空时调用dequeue，则需要线性时间才能到达收件箱的底部(正如您可以在Dave的代码中看到的那样)。

您可以将队列实现为单链表(每个元素指向下一个插入的元素)，保留一个额外的指针指向最后一个插入的元素进行推操作(或使其成为循环列表)。在此数据结构上实现队列和出队列非常容易，只需常数时间即可完成。这是最坏情况的常数时间，不是平摊。而且，正如注释中要求澄清的那样，最坏情况下常数时间严格来说比平摊常数时间要好。