스택(stack)을 이용하여 큐(queue)를 구현해야 하는 경우, 하나의 큐 클래스를 정의한 뒤 그 안에 두 개의 스택 인스턴스를 만들어 활용할 수 있습니다. 삽입(enqueue), 삭제(dequeue), 비어 있는지 확인 등 큐의 핵심 연산은 모두 클래스 내부의 메서드 형태로 정의됩니다.
동작 원리
큐는 FIFO(선입선출) 방식으로 동작하지만, 스택은 LIFO(후입선출) 방식입니다. 따라서 스택 한 개만으로는 큐를 흉내 낼 수 없으며, 두 개의 스택을 조합해야 합니다. 새로운 데이터는 항상 첫 번째 스택(in_val)에 쌓고, 삭제 요청이 들어왔을 때 두 번째 스택(out_val)이 비어 있으면 첫 번째 스택의 모든 요소를 옮겨 담아 순서를 뒤집은 뒤 꺼내면 됩니다.
예제 코드
class Stack_structure:
def __init__(self):
self.items = []
def check_empty(self):
return self.items == []
def push_operation(self, data):
self.items.append(data)
def pop_operation(self):
return self.items.pop()
class Queue_structure:
def __init__(self):
self.in_val = Stack_structure()
self.out_val = Stack_structure()
def check_empty(self):
return self.in_val.check_empty() and self.out_val.check_empty()
def enqueue_operation(self, data):
self.in_val.push_operation(data)
def dequeue_operation(self):
if self.out_val.check_empty():
while not self.in_val.check_empty():
deleted_val = self.in_val.pop_operation()
self.out_val.push_operation(deleted_val)
return self.out_val.pop_operation()
my_instance = Queue_structure()
while True:
print('enqueue <값>')
print('dequeue')
print('quit')
my_input = input('수행할 연산을 입력하세요 : ').split()
operation = my_input[0].strip().lower()
if operation == 'enqueue':
my_instance.enqueue_operation(int(my_input[1]))
elif operation == 'dequeue':
if my_instance.check_empty():
print('큐가 비어 있습니다')
else:
deleted_elem = my_instance.dequeue_operation()
print('삭제된 요소 : ', int(deleted_elem))
elif operation == 'quit':
break실행 결과
enqueue <값> dequeue quit 수행할 연산을 입력하세요 : enqueue 45 enqueue <값> dequeue quit 수행할 연산을 입력하세요 : enqueue 23 enqueue <값> dequeue quit 수행할 연산을 입력하세요 : enqueue 78 enqueue <값> dequeue quit 수행할 연산을 입력하세요 : dequeue 삭제된 요소 : 45 enqueue <값> dequeue quit 수행할 연산을 입력하세요 : quit
코드 설명
Stack_structure 클래스: 내부적으로 빈 리스트(items)를 초기화하며, 스택이 비었는지 확인하는 check_empty, 요소를 추가하는 push_operation, 마지막 요소를 제거하고 반환하는 pop_operation 메서드를 제공합니다.
Queue_structure 클래스: 두 개의 스택 인스턴스(in_val, out_val)를 멤버 변수로 가지며, 이 두 스택을 조합해 큐처럼 동작시킵니다.
check_empty: 두 스택이 모두 비어 있을 때 큐 전체가 비어 있다고 판단합니다.
enqueue_operation: 새로 들어온 데이터를 첫 번째 스택(in_val)에 push합니다.
dequeue_operation: 두 번째 스택(out_val)이 비어 있으면, 첫 번째 스택의 모든 요소를 하나씩 pop하여 두 번째 스택에 push함으로써 순서를 뒤집습니다. 그 후 두 번째 스택에서 pop한 값을 반환합니다.
사용자 인터페이스: 무한 반복문 안에서 enqueue, dequeue, quit 세 가지 명령을 입력받고, 사용자의 선택에 따라 해당 연산을 수행한 뒤 그 결과를 콘솔에 출력합니다.
시간 복잡도
enqueue 연산은 항상 O(1)이며, dequeue 연산은 개별 호출 기준으로 최악의 경우 O(n)입니다. 하지만 각 요소는 최대 한 번만 스택 간에 이동하므로, 여러 번의 연산을 평균 낸 분할상환(amortized) 시간 복잡도는 O(1)입니다.