目录链接：https://www.jianshu.com/p/9c0ada9e0ede
用栈实现队列
用栈实现队列(Implement Queue using Stacks)
使用栈实现队列的下列操作：
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 操作）。
切题
一、Clarification
没有特别需要注意的边界问题
二、Possible Solution
队列先入先出，栈先入后出，需要两个栈inputstack、outputstack 来实现队列的功能。
push 直接入inputstack栈；
pop 、 peek 先看outputstack栈是否有元素，有就从栈顶取，如果没有从inputstack栈依次出栈，并将出栈元素依次入outputstack栈直到inputstack为空，再看outputstack栈是否有元素
empty 需要判断两个栈inputstack、outputstack 是否为都为空
Python3 实现
出入双栈 Py3
用栈实现队列(Implement Queue using Stacks) Py3 出入双栈实现
#@author:leacoder
#@des: 用栈实现队列
class MyQueue:
def __init__(self):
self.inputstack = []
self.outputstack = []
def push(self, x: int) -> None:
self.inputstack.append(x)
def pop(self) -> int:
if 0!=len(self.outputstack):
return self.outputstack.pop()
else:
while 0!=len(self.inputstack):
self.outputstack.append(self.inputstack.pop())
return self.outputstack.pop()
def peek(self) -> int:
if 0!=len(self.outputstack):
return self.outputstack[-1]
else:
while 0!=len(self.inputstack):
self.outputstack.append(self.inputstack.pop())
return self.outputstack[-1]
def empty(self) -> bool:
return 0==len(self.inputstack) and 0==len(self.outputstack)
# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()
1.push(x) -- 将x放入 入栈（inputstack ）
2.pop() -- 判断 出栈（outputstack）是否为空，不为空从出栈（outputstack）直接取元素；为空则先将入栈（inputstack）所有元素依次取出放入出栈（outputstack）中，再从出栈（outputstack）取元素
3.peek() -- 同pop()
4.empty() -- 判断出入栈是否都为空（inputstack 、outputstack）
Java 实现
出入双栈 Java
实现逻辑不变
用栈实现队列(Implement Queue using Stacks) Java 出入双栈实现
C++实现
出入双栈 C++
用栈实现队列(Implement Queue using Stacks) C++ 出入双栈实现
GitHub链接：
https://github.com/lichangke/LeetCode
知乎个人首页：
https://www.zhihu.com/people/lichangke/
个人Blog:
https://lichangke.github.io/
欢迎大家来一起交流学习
