Computer Science/Data Structure & Algorithm
stack 2개로 queue 만들기
Dan-k
2020. 12. 5. 18:59
반응형
stack 2개를 이용하면 queue를 만들 수 있다.
stack은 LIFO (Last In First Out)
queue 는 FIFO (First In First Out)
즉, stack을 두개를 이용해서 빈 스택에 다른 스택을 담고 다시 빼는 식으로 queue를 만들 수 있는 것이다.
구현 코드 예시
# stack 2개로 queue 만들기
class Stack:
def __init__(self):
self.stack = []
def __repr__(self):
return f"{self.stack}"
def push(self,item):
self.stack.append(item)
def pop(self):
return self.stack.pop()
def is_empty(self):
if len(self.stack) == 0 : return True
else : return False
st = Stack()
st.push(1)
st.push(2)
st.push(3)
print(st)
[1,2,3]
st.pop()
3
print(st)
[1,2]
class Queue:
def __init__(self):
self.qu = Stack()
self.stack2 = Stack()
def __repr__(self):
return f"{self.qu}"
def push(self,item):
self.qu.push(item)
self.que = self.qu
def pop(self):
while not self.qu.is_empty():
self.stack2.push(self.qu.pop())
result = self.stack2.pop()
while not self.stack2.is_empty():
self.qu.push(self.stack2.pop())
return result
qu = Queue()
qu.push(1)
qu.push(2)
qu.push(3)
print(qu)
[1,2,3]
qu.pop()
1
print(qu)
[2,3]
728x90
반응형
LIST