232 Implement Queue using Stacks 用棧實(shí)現(xiàn)隊(duì)列
Description:
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.
Example:
MyQueue queue = new MyQueue();
queue.push(1);
queue.push(2);
queue.peek(); // returns 1
queue.pop(); // returns 1
queue.empty(); // returns false
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).
題目描述:
使用棧實(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
說(shuō)明:
你只能使用標(biāo)準(zhǔn)的棧操作 -- 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的悠瞬。
你所使用的語(yǔ)言也許不支持棧陕凹。你可以使用 list 或者 deque（雙端隊(duì)列）來(lái)模擬一個(gè)棧萝映，只要是標(biāo)準(zhǔn)的棧操作即可望忆。
假設(shè)所有操作都是有效的 （例如罩阵，一個(gè)空的隊(duì)列不會(huì)調(diào)用 pop 或者 peek 操作）。
思路:
參考LeetCode #225 Implement Stack using Queues 用隊(duì)列實(shí)現(xiàn)棧
使用 2個(gè)棧完成隊(duì)列
- push()時(shí)間復(fù)雜度O(1), 空間復(fù)雜度O(1)
- pop()時(shí)間復(fù)雜度O(n), 空間復(fù)雜度O(n)
- top()時(shí)間復(fù)雜度O(n), 空間復(fù)雜度O(n)
- empty()時(shí)間復(fù)雜度O(1), 空間復(fù)雜度O(1)
代碼:
C++:
class MyQueue
{
public:
/** Initialize your data structure here. */
MyQueue()
{
}
/** Push element x to the back of queue. */
void push(int x)
{
in_stack.push(x);
}
/** Removes the element from in front of queue and returns that element. */
int pop()
{
move(in_stack, out_stack);
int result = out_stack.top();
out_stack.pop();
move(out_stack, in_stack);
return result;
}
/** Get the front element. */
int peek()
{
move(in_stack, out_stack);
int result = out_stack.top();
move(out_stack, in_stack);
return result;
}
/** Returns whether the queue is empty. */
bool empty()
{
return in_stack.empty();
}
private:
stack<int> in_stack;
stack<int> out_stack;
void move(stack<int> &a, stack<int> &b)
{
while (!a.empty())
{
b.push(a.top());
a.pop();
}
}
};
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue* obj = new MyQueue();
* obj->push(x);
* int param_2 = obj->pop();
* int param_3 = obj->peek();
* bool param_4 = obj->empty();
*/
Java:
class MyQueue {
private Stack<Integer> stack;
private Stack<Integer> temp;
private void move(Stack<Integer> a, Stack<Integer> b) {
while (!a.empty()) b.push(a.pop());
}
/** Initialize your data structure here. */
public MyQueue() {
stack = new Stack<>();
temp = new Stack<>();
}
/** Push element x to the back of queue. */
public void push(int x) {
stack.push(x);
}
/** Removes the element from in front of queue and returns that element. */
public int pop() {
move(stack, temp);
int result = temp.pop();
move(temp, stack);
return result;
}
/** Get the front element. */
public int peek() {
move(stack, temp);
int result = temp.peek();
move(temp, stack);
return result;
}
/** Returns whether the queue is empty. */
public boolean empty() {
return stack.empty();
}
}
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue obj = new MyQueue();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.peek();
* boolean param_4 = obj.empty();
*/
Python:
class MyQueue:
def __init__(self):
"""
Initialize your data structure here.
"""
self.stack = []
def push(self, x: int) -> None:
"""
Push element x to the back of queue.
"""
self.stack.append(x)
def pop(self) -> int:
"""
Removes the element from in front of queue and returns that element.
"""
temp = []
while self.stack:
temp.append(self.stack.pop())
result = temp.pop()
while temp:
self.stack.append(temp.pop())
return result
def peek(self) -> int:
"""
Get the front element.
"""
temp = []
while self.stack:
temp.append(self.stack.pop())
result = temp[-1]
while temp:
self.stack.append(temp.pop())
return result
def empty(self) -> bool:
"""
Returns whether the queue is empty.
"""
return len(self.stack) == 0
# 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()
