Implement a last in first out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal queue (push, top, pop, and empty).
MyStack 클래스는
- push(int x): 스택 상단에 요소 삽입
- pop(): 스택 상단 요소 제거하고 그 요소 반환
- top(): 스택 상단 요소 반환
- empty(): 스택 비었는지 여부 반환
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
list
pop(0)과 insert(0, v)에서 $O(n)$ 메모리 이동이 발생dequequeqefrom queue import LifoQueue
class MyStack:
def __init__(self):
"""
Initialize your data structure here.
"""
self.que = LifoQueue()
def push(self, x: int) -> None:
"""
Push element x onto stack.
"""
self.que.put(x)
def pop(self) -> int:
"""
Removes the element on top of the stack and returns that element.
"""
return self.que.get()
def top(self) -> int:
"""
Get the top element.
"""
return self.que.queue[-1]
def empty(self) -> bool:
"""
Returns whether the stack is empty.
"""
return self.que.qsize() == 0
Runtime: 32 ms, faster than 57.41% of Python3 online submissions for Implement Stack using Queues. Memory Usage: 14.4 MB, less than 48.18% of Python3 online submissions for Implement Stack using Queues.