目錄鏈接：http://www.reibang.com/p/9c0ada9e0ede
用棧實(shí)現(xiàn)隊(duì)列
用棧實(shí)現(xiàn)隊(duì)列(Implement Queue using Stacks)
使用棧實(shí)現(xiàn)隊(duì)列的下列操作：
push(x) -- 將一個(gè)元素放入隊(duì)列的尾部工扎。
pop() -- 從隊(duì)列首部移除元素陪毡。
peek() -- 返回隊(duì)列首部的元素画切。
empty() -- 返回隊(duì)列是否為空裹纳。
示例:
MyQueue queue = new MyQueue();
queue.push(1);
queue.push(2);
queue.peek(); // 返回 1
queue.pop(); // 返回 1
queue.empty(); // 返回 false
說明:
你只能使用標(biāo)準(zhǔn)的棧操作 -- 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的屿讽。
你所使用的語言也許不支持棧邑蒋。你可以使用 list 或者 deque（雙端隊(duì)列）來模擬一個(gè)棧歇竟，只要是標(biāo)準(zhǔn)的棧操作即可。
假設(shè)所有操作都是有效的 （例如滔吠，一個(gè)空的隊(duì)列不會(huì)調(diào)用 pop 或者 peek 操作）纲菌。
切題
一、Clarification
沒有特別需要注意的邊界問題
二疮绷、Possible Solution
隊(duì)列先入先出翰舌，棧先入后出，需要兩個(gè)棧inputstack冬骚、outputstack 來實(shí)現(xiàn)隊(duì)列的功能椅贱。
push 直接入inputstack棧；
pop 只冻、 peek 先看outputstack棧是否有元素庇麦，有就從棧頂取，如果沒有從inputstack棧依次出棧喜德，并將出棧元素依次入outputstack棧直到inputstack為空山橄，再看outputstack棧是否有元素
empty 需要判斷兩個(gè)棧inputstack、outputstack 是否為都為空
Python3 實(shí)現(xiàn)
出入雙棧 Py3
用棧實(shí)現(xiàn)隊(duì)列(Implement Queue using Stacks) Py3 出入雙棧實(shí)現(xiàn)
#@author:leacoder
#@des: 用棧實(shí)現(xiàn)隊(duì)列
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 實(shí)現(xiàn)
出入雙棧 Java
實(shí)現(xiàn)邏輯不變
用棧實(shí)現(xiàn)隊(duì)列(Implement Queue using Stacks) Java 出入雙棧實(shí)現(xiàn)
C++實(shí)現(xiàn)
出入雙棧 C++
用棧實(shí)現(xiàn)隊(duì)列(Implement Queue using Stacks) C++ 出入雙棧實(shí)現(xiàn)
GitHub鏈接：
https://github.com/lichangke/LeetCode
知乎個(gè)人首頁：
https://www.zhihu.com/people/lichangke/
個(gè)人Blog:
https://lichangke.github.io/
歡迎大家來一起交流學(xué)習(xí)
