問題：
Implement the following operations of a queue using stacks.
- push(x) -- Push element x to the back of queue.
- pop() -- Removes the element from in front of queue.
- peek() -- Get the front element.
- empty() -- Return whether the queue is empty.
Notes:- You must use only standard operations of a stack -- which means only push to top, peek/pop from top, size, and is empty operations are valid.
- Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
- You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).
大意：
用堆棧實現(xiàn)一個滿足下列操作的隊列吟逝。
- push(x)——push一個元素x到隊列尾部宰翅。
- pop()——從隊列頭部移除一個元素。
- peek()——獲取隊列頭部的元素。
- empty()——返回隊列是否是空的属桦。
注意：- 你必須使用標(biāo)準(zhǔn)的堆棧操作——也就是只有push到頂端、從頂端peek/pop终蒂、size以及empty操作是有效的席里。
- 根據(jù)你的語言，堆椪缶撸可能不是原生支持的碍遍。你可能要通過使用list或者deque（double-ended queue）模仿一個堆棧，就好像在使用標(biāo)準(zhǔn)的堆棧操作一樣阳液。
- 你可以假設(shè)所有的操作都是有效的（比如不會對一個空隊列進(jìn)行pop或者peek操作）怕敬。
思路：
這道題要我們用堆棧來實現(xiàn)隊列操作。堆棧和隊列最大的區(qū)別就在于堆棧是先進(jìn)后出的帘皿，而隊列是先進(jìn)先出的东跪。所以在實現(xiàn)的時候，其他操作都好說鹰溜，主要是pop和peek操作虽填，我們需要將堆棧本身移除新加入的元素改為移除堆棧底部最開始加入的元素，要達(dá)到這個操作就得用另一個堆棧來臨時存儲數(shù)據(jù)曹动，就像小時候玩的游戲斋日，要先把堆棧里的數(shù)據(jù)全部倒到另一個堆棧里，才能取出最底部的元素仁期，移除或者返回后桑驱，再將元素全部還原。
代碼（Java）：
class MyQueue {
private Stack<Integer> in = new Stack<>();
private Stack<Integer> out = new Stack<>();
// Push element x to the back of queue.
public void push(int x) {
in.push(x);
}
// Removes the element from in front of queue.
public void pop() {
while (!in.empty()) {
out.push(in.pop());
}
out.pop();
while (!out.empty()) {
in.push(out.pop());
}
}
// Get the front element.
public int peek() {
while (!in.empty()) {
out.push(in.pop());
}
int result = out.peek();
while (!out.empty()) {
in.push(out.pop());
}
return result;
}
// Return whether the queue is empty.
public boolean empty() {
return in.empty();
}
}
他山之石：
class MyQueue {
Stack<Integer> input = new Stack();
Stack<Integer> output = new Stack();
public void push(int x) {
input.push(x);
}
public void pop() {
peek();
output.pop();
}
public int peek() {
if (output.empty())
while (!input.empty())
output.push(input.pop());
return output.peek();
}
public boolean empty() {
return input.empty() && output.empty();
}
}
這個做法其實和我的做法大致是一致的跛蛋，但是我在進(jìn)行pop和peek操作時熬的，需要循環(huán)兩次來進(jìn)行倒出來又倒回去的工作。他的做法則是赊级，只有當(dāng)另一個堆椦嚎颍空了，才將原堆棧的元素倒過去理逊，因為每次倒都是全部倒空橡伞，新加入的元素會加到原堆棧去，而老元素都一批批地倒進(jìn)另一個堆棧了晋被，但我取元素的時候就是從老元素開始取得兑徘，所以只需要從另一個堆棧的頂部開始取就行了，畢竟倒一次順序就反過來了羡洛，當(dāng)取空了另一個堆棧后挂脑，就再倒一次，這樣時間復(fù)雜度就大大降低了。
合集：https://github.com/Cloudox/LeetCode-Record
