내 풀이
class MyStack:
def __init__(self):
q1 = deque()
q2 = deque()
def push(self, x: int) -> None:
"""
Push element x onto stack.
"""
while self.q1:
self.q2.append(self.q1.popleft())
self.q1.append(x)
while self.q2:
self.q1.append(self.q2.popleft())
def pop(self) -> int:
"""
Removes the element on top of the stack and returns that element.
"""
return self.q1.popleft()
def top(self) -> int:
"""
Get the top element.
"""
return self.q1[0]
def empty(self) -> bool:
"""
Returns whether the stack is empty.
"""
return len(self.q1)==0큐 두 개를 이용한다. 첫 번째 큐에 push를 하면 첫 번째 큐의 기존에 있던 것들을 순서 그대로 두번째 큐에 옮긴 다음, 첫 번째 큐에 push를 한다. 그러고 옮겼던 것들을 다시 그대로 다 옮겨주면 push한 것이 가장 왼쪽에 있다.
책 풀이
class MyStack:
def __init__(self):
self.q = collections.deque()
def push(self, x: int) -> None:
self.q.append(x)
for _ in range(len(self.q) - 1):
self.q.append(self.q.popleft())
def pop(self) -> int:
return self.q1.popleft()
def top(self) -> int:
return self.q1[0]
def empty(self) -> bool:
return len(self.q1)==0조금만 더 생각해보면 아예 하나의 큐로도 구현 가능하다.
