232.Implement Queue using Stacks === ###### tags: `Easy`,`Stack`,`Queue` [232. Implement Queue using Stacks](https://leetcode.com/problems/implement-queue-using-stacks/) ### 題目描述 Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (`push`, `peek`, `pop`, and `empty`). Implement the `MyQueue` class: * `void push(int x)` Pushes element x to the back of the queue. * `int pop()` Removes the element from the front of the queue and returns it. * `int peek()` Returns the element at the front of the queue. * `boolean empty()` Returns `true` if the queue is empty, `false` otherwise. **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, the stack may not be supported natively. You may simulate a stack using a list or deque (double-ended queue) as long as you use only a stack's standard operations. ### 範例 **Example 1:** ``` Input ["MyQueue", "push", "push", "peek", "pop", "empty"] [[], [1], [2], [], [], []] Output [null, null, null, 1, 1, false] Explanation MyQueue myQueue = new MyQueue(); myQueue.push(1); // queue is: [1] myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue) myQueue.peek(); // return 1 myQueue.pop(); // return 1, queue is [2] myQueue.empty(); // return false ``` **Constraints**: * 1 <= `x` <= 9 * At most `100` calls will be made to `push`, `pop`, `peek`, and `empty`. * All the calls to `pop` and `peek` are valid. **Follow-up:** Can you implement the queue such that each operation is amortized `O(1)` time complexity? In other words, performing `n` operations will take overall `O(n)` time even if one of those operations may take longer. ### 解答 #### Python ```python= class MyQueue: def __init__(self): self.input_stk = [] self.output_stk = [] def push(self, x: int) -> None: self.input_stk.append(x) def pop(self) -> int: self.peek() return self.output_stk.pop() def peek(self) -> int: if not self.output_stk: while self.input_stk: front = self.input_stk.pop() self.output_stk.append(front) peek = self.output_stk[-1] return peek def empty(self) -> bool: return not self.input_stk and not self.output_stk ``` >[name=Kobe][time=Fri, Dec 16, 2022] #### C# ```csharp= public class MyQueue { Stack<int> target = new Stack<int>(); Stack<int> temp = new Stack<int>(); public void Push(int x) { while(target.Any()){ temp.Push(target.Pop()); } target.Push(x); while(temp.Any()){ target.Push(temp.Pop()); } } public int Pop() { return target.Pop(); } public int Peek() { return target.Peek(); } public bool Empty() { return !target.Any(); } } ``` >[name=Jim][time=Fri, Dec 16, 2022] #### Javascript ```javascript= class MyQueue { constructor() { this.stack = []; } push(x) { this.stack.push(x); } // use two stacks to implement queue pop() { const temp = []; while (this.stack.length > 1) { temp.push(this.stack.pop()); } const result = this.stack.pop(); while (temp.length > 0) { this.stack.push(temp.pop()); } return result; } peek() { return this.stack[0]; } empty() { return this.stack.length === 0; } } ``` >[name=Marsgoat][time= Dec 16, 2022] #### Java ```java= class MyQueue { Stack<Integer> input = new Stack<Integer>(); Stack<Integer> output = new Stack<Integer>(); public void push(int x) { input.push(x); } public int pop() { peek(); return 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(); } } ``` >[name=Kobe][time=Fri, Dec 16, 2022] ### Reference [回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)