Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/232.html
232 Implement Queue using Stacks
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 operations are valid
push to top,
peek/pop from top,
size, and
is empty
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).
@tag-stack
Algorithm
As long as the element is inserted from the front every time, for example, if a queue is 1, 2, 3, 4
, then we save it in the stack as 4, 3, 2, 1
, and then return to the top element 1, also It is the first element of the queue.
The difficulty
of this question is the push function. We need an auxiliary stack tmp, and store the elements of s
into tmp in reverse order. At this time, add a new element x
, and then store the elements in tmp back. This is the order we want , The other three operations also directly call stack operations.
To optimize above, because every time you push, you have to flip both stacks,
So, have stacks new
and old
, the new pushed elements are cached in _new
first, and all elements in _new
are moved to _old
only when the operations are pop and peek, which improves efficiency.
Code
Java
-
public class Implement_Queue_using_Stacks { class MyQueue { private Stack<Integer> stack1; private Stack<Integer> stack2; public MyQueue() { this.stack1 = new Stack<Integer>(); this.stack2 = new Stack<Integer>(); } // Push element x to the back of queue. public void push(int x) { stack1.push(x); } // Removes the element from in front of queue. public int pop() { if (!stack2.isEmpty()) { return stack2.pop(); // stack is queue-order, queue-head at this-stack-top } else { while (!stack1.isEmpty()) { stack2.push(stack1.pop()); } return stack2.pop(); } } // Get the front element. public int peek() { int ret = 0; if (!stack2.isEmpty()) { ret = stack2.peek(); } else { while (!stack1.isEmpty()) { stack2.push(stack1.pop()); } ret = stack2.peek(); } return ret; } // Return whether the queue is empty. public boolean empty() { return stack1.isEmpty() && stack2.isEmpty(); } } }
-
// OJ: https://leetcode.com/problems/implement-queue-using-stacks // Time: O(1) amortized. // Space: O(1) class MyQueue { stack<int> in, out; public: MyQueue() {} void push(int x) { in.push(x); } int pop() { int val = peek(); out.pop(); return val; } int peek() { if (out.empty()) { while (in.size()) { out.push(in.top()); in.pop(); } } return out.top(); } bool empty() { return in.empty() && out.empty(); } };
-
class MyQueue: def __init__(self): self.stk1 = [] self.stk2 = [] def push(self, x: int) -> None: self.stk1.append(x) def pop(self) -> int: self.move() return self.stk2.pop() def peek(self) -> int: self.move() return self.stk2[-1] def empty(self) -> bool: return not self.stk1 and not self.stk2 def move(self): if not self.stk2: while self.stk1: self.stk2.append(self.stk1.pop()) # 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() ############ class MyQueue: def __init__(self): self.sk = [] self.rsk = [] def push(self, x: int) -> None: self.sk.append(x); def pop(self) -> int: self.peek() return self.rsk.pop() def peek(self) -> int: if self.rsk: return self.rsk[-1] else: while self.sk: self.rsk.append(self.sk.pop()) return self.rsk[-1] def empty(self) -> bool: return not (self.sk or self.rsk) # 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()