队列是一种先进先出的数据结构，栈是一种先进后出的数据结构，形象一点就是这样：

目录

1、LeetCode232. 用栈实现队列

2、LeetCode225. 用队列实现栈

---

1、LeetCode232. 用栈实现队列

使用栈实现队列的下列操作：

push(x) -- 将一个元素放入队列的尾部。pop() -- 从队列首部移除元素。peek() -- 返回队列首部的元素。empty() -- 返回队列是否为空。 示例: MyQueue queue = new MyQueue(); queue.push(1); queue.push(2); queue.peek(); // 返回 1 queue.pop(); // 返回 1 queue.empty(); // 返回 false

说明:

你只能使用标准的栈操作 -- 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）。

首先，队列的 API 如下：

class MyQueue { /** 添加元素到队尾 */ public void push(int x); /** 删除队头的元素并返回 */ public int pop(); /** 返回队头元素 */ public int peek(); /** 判断队列是否为空 */ public boolean empty(); }

我们使用两个栈 s1, s2 就能实现一个队列的功能（这样放置栈可能更容易理解）：

class MyQueue { private Stack<Integer> s1, s2; public MyQueue() { s1 = new Stack<>(); s2 = new Stack<>(); } // ... }

当调用 push 让元素入队时，只要把元素压入 s1 即可，比如说 push 进 3 个元素分别是 1,2,3，那么底层结构就是这样：

/** 添加元素到队尾 */ public void push(int x) { s1.push(x); }

那么如果这时候使用 peek 查看队头的元素怎么办呢？按道理队头元素应该是 1，但是在 s1 中 1 被压在栈底，现在就要轮到 s2 起到一个中转的作用了：当 s2 为空时，可以把 s1 的所有元素取出再添加进 s2，这时候 s2 中元素就是先进先出顺序了。

/** 返回队头元素 */ public int peek() { if (s2.isEmpty()) // 把 s1 元素压入 s2 while (!s1.isEmpty()) s2.push(s1.pop()); return s2.peek(); }

同理，对于 pop 操作，只要操作 s2 就可以了。

/** 删除队头的元素并返回 */ public int pop() { // 先调用 peek 保证 s2 非空 peek(); return s2.pop(); }

最后，如何判断队列是否为空呢？如果两个栈都为空的话，就说明队列为空：

/** 判断队列是否为空 */ public boolean empty() { return s1.isEmpty() && s2.isEmpty(); }

至此，就用栈结构实现了一个队列，核心思想是利用两个栈互相配合。

值得一提的是，这几个操作的时间复杂度是多少呢？有点意思的是 peek 操作，调用它时可能触发 while 循环，这样的话时间复杂度是 O(N)，但是大部分情况下 while 循环不会被触发，时间复杂度是 O(1)。由于 pop 操作调用了 peek，它的时间复杂度和 peek 相同。

像这种情况，可以说它们的最坏时间复杂度是 O(N)，因为包含 while 循环，可能需要从 s1 往 s2 搬移元素。

但是它们的均摊时间复杂度是 O(1)，这个要这么理解：对于一个元素，最多只可能被搬运一次，也就是说 peek 操作平均到每个元素的时间复杂度是 O(1)。

完整代码：

class MyQueue { /** Initialize your data structure here. */ private Stack<Integer> inStack = null; private Stack<Integer> outStack = null; public MyQueue() { inStack = new Stack(); outStack = new Stack(); } /** Push element x to the back of queue. */ public void push(int x) { inStack.push(x); } /** Removes the element from in front of queue and returns that element. */ public int pop() { peek(); return outStack.pop(); } /** Get the front element. */ public int peek() { if(outStack.isEmpty()){ while(!inStack.isEmpty()){ outStack.push(inStack.pop()); } } return outStack.peek(); } /** Returns whether the queue is empty. */ public boolean empty() { return (inStack.isEmpty() && outStack.isEmpty()); } }

2、LeetCode225. 用队列实现栈

使用队列实现栈的下列操作：

push(x) -- 元素 x 入栈pop() -- 移除栈顶元素top() -- 获取栈顶元素empty() -- 返回栈是否为空

注意:

你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。你所使用的语言也许不支持队列。 你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）。

如果说双栈实现队列比较巧妙，那么用队列实现栈就比较简单粗暴了，只需要一个队列作为底层数据结构。首先看下栈的 API：

class MyStack { /** 添加元素到栈顶 */ public void push(int x); /** 删除栈顶的元素并返回 */ public int pop(); /** 返回栈顶元素 */ public int top(); /** 判断栈是否为空 */ public boolean empty(); }

       先说 push API，直接将元素加入队列，同时记录队尾元素，因为队尾元素相当于栈顶元素，如果要 top 查看栈顶元素的话可以直接返回：

class MyStack { Queue<Integer> queue = null; int peekEle = Integer.MIN_VALUE; /** Initialize your data structure here. */ public MyStack() { queue = new LinkedList<>(); } /** Push element x onto stack. */ public void push(int x) { queue.offer(x); peekEle = x; } /** Get the top element. */ public int top() { return peekEle; } /** Returns whether the stack is empty. */ public boolean empty() { return queue.isEmpty(); } }

我们的底层数据结构是先进先出的队列，每次 pop 只能从队头取元素；但是栈是后进先出，也就是说 pop API 要从队尾取元素。

解决方法简单粗暴，把队列前面的都取出来再加入队尾，让之前的队尾元素排到队头，这样就可以取出了：

/** 删除栈顶的元素并返回 */ public int pop() { int size = q.size(); while (size > 1) { q.offer(q.poll()); size--; } // 之前的队尾元素已经到了队头 return q.poll(); }

这样实现还有一点小问题就是，原来的队尾元素被提到队头并删除了，但是 top_elem 变量没有更新，我们还需要一点小修改：

/** Removes the element on top of the stack and returns that element. */ public int pop() { int size = queue.size(); while(size > 2){ queue.offer(queue.poll()); size--; } peekEle = queue.peek();//倒数第二个为栈顶值 queue.offer(queue.poll()); return queue.poll(); }

很明显，用队列实现栈的话，pop 操作时间复杂度是 O(N)，其他操作都是 O(1)​。

个人认为，用队列实现栈是没啥亮点的问题，但是用双栈实现队列是值得学习的。

      从栈 s1 搬运元素到 s2 之后，元素在 s2 中就变成了队列的先进先出顺序，这个特性有点类似「负负得正」，确实不太容易想到。