자료구조 with Python : 스택 2개로 큐 구현하기
큐를 구현하는 방법 중 하나는 스택을 두 개 사용하는 것이다. 여기서는 스택 자료구조를 직접 사용하지 않고 파이썬 내장 리스트를 사용하여 스택을 대신한다.
큐의 구조
- enqueue : 뒤 쪽으로 원소를 삽입하는 함수
- dequeue : 가장 앞에 위치한 원소를 제거하면서 반환하는 함수
- is_empty : 큐가 비어있는지 확인하는 함수
- transfer : in_stack의 원소들을 모두 out_stack으로 옮기는 함수
스택 2개를 사용한 큐의 구현
class Queue(object):
def __init__(self):
self.in_stack = []
self.out_stack = []
def isEmpty(self):
return not(bool(self.in_stack) or bool(self.out_stack))
def transfer(self):
while self.in_stack:
self.out_stack.append(self.in_stack.pop())
def enqueue(self, item):
return self.in_stack.append(item)
def dequeue(self):
if not self.out_stack:
self.transfer()
if not self.isEmpty():
return self.out_stack.pop()
else:
print("Queue is empty!")
def __repr__(self):
tmp = []
tmp += self.out_stack[::-1]
tmp += self.in_stack
if tmp:
return repr(tmp)
else:
return "Queue is empty!"enqueue를 하게 되면 in_stack 리스트에 데이터를 입력한다. 그러다 dequeue를 실행했을 때 out_stack이 비어있으면 in_stack의 모든 원소들을 pop하여서 가져온다. 이후에 out_stack의 원소들을 pop하게 되면 큐의 동작처럼 FIFO로 데이터가 출력되는 것을 확인할 수 있다.
확인코드
queue = Queue()
for i in range(1, 4):
queue.enqueue(i)
print(queue)
print("dequeue: {0}".format(queue.dequeue()))
print("dequeue: {0}".format(queue.dequeue()))
queue.enqueue(4)
queue.enqueue(5)
print(queue)
print("dequeue: {0}".format(queue.dequeue()))
print(queue)
고찰
가장 중요한 아이디어는 in_stack의 데이터들은 모두 out_stack보다 늦게 들어온 데이터라는 것이다. out_stack에 원소가 있다면 in_stack에서 원소를 가져오지 않고 pop을 해야했다. LIFO를 두 번 사용해서 FIFO로 만드는 게 꽤 흥미로웠다.
'프로그래밍 > 자료구조' 카테고리의 다른 글
| [자료구조][Python] : Queue(큐) (0) | 2021.10.02 |
|---|---|
| [자료구조][Python] : Stack(스택) (0) | 2021.09.15 |
