Constraints
- 1 <= x <= 9
- At most 100 calls will be made to push, pop, top, and empty
- All the calls to pop and top are valid.
Idea #1 (Time: O(N), Memory: O(N))
- push: enqueue everything
- pop: dequeue everything, return last one, revert without last one.
- top: dequeue everything, return last one, revert!
- empty: same as empty
Test Cases
Example 1:
Input
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 2, 2, false]
Explanation
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // return 2
myStack.pop(); // return 2
myStack.empty(); // return False
Code
class Node: def __init__(self, data): self.data = data self.next = None class Queue: def __init__(self): self.front = None self.rear = None def enqueue(self, data): if self.front is None: self.front = self.rear = Node(data) else: node = Node(data) self.rear.next = node self.rear = node def dequeue(self): if self.front is None: return None node = self.front if self.front == self.rear: self.front = self.rear = None else: self.front = self.front.next return node.data def is_empty(self): return self.front is None class MyStack: def __init__(self): self.myqueue = Queue() def push(self, x: int) -> None: self.myqueue.enqueue(x) def pop(self) -> int: buf = list() while not self.myqueue.is_empty(): buf.append(self.myqueue.dequeue()) res = buf[-1] buf = buf[:-1] for elem in buf: self.myqueue.enqueue(elem) return res def top(self) -> int: res = self.pop() self.myqueue.enqueue(res) return res def empty(self) -> bool: return self.myqueue.is_empty() 
Top comments (0)