두 개의 큐(Queue)를 사용해 스택(Stack)을 구현하려면 'Stack_structure' 클래스와 'Queue_structure' 클래스가 필요합니다. 각 클래스 안에는 스택과 큐에 값을 추가하거나 삭제하는 메서드들이 정의됩니다.
아래 예제를 통해 실제 구현 과정을 살펴보겠습니다.
예제 코드
class Stack_structure:
def __init__(self):
self.queue_1 = Queue_structure()
self.queue_2 = Queue_structure()
def check_empty(self):
return self.queue_2.check_empty()
def push_val(self, data):
self.queue_1.enqueue_operation(data)
while not self.queue_2.check_empty():
x = self.queue_2.dequeue_operation()
self.queue_1.enqueue_operation(x)
self.queue_1, self.queue_2 = self.queue_2, self.queue_1
def pop_val(self):
return self.queue_2.dequeue_operation()
class Queue_structure:
def __init__(self):
self.items = []
self.size = 0
def check_empty(self):
return self.items == []
def enqueue_operation(self, data):
self.size += 1
self.items.append(data)
def dequeue_operation(self):
self.size -= 1
return self.items.pop(0)
def size_calculate(self):
return self.size
my_instance = Stack_structure()
print('Menu')
print('push <value>')
print('pop')
print('quit')
while True:
my_input = input('What operation would you like to perform ? ').split()
operation = my_input[0].strip().lower()
if operation == 'push':
my_instance.push_val(int(my_input[1]))
elif operation == 'pop':
if my_instance.check_empty():
print('Stack is empty.')
else:
print('The deleted value is: ', my_instance.pop_val())
elif operation == 'quit':
break실행 결과
Menu push <value> pop quit What operation would you like to perform ? push 56 What operation would you like to perform ? push 34 What operation would you like to perform ? push 78 What operation would you like to perform ? push 90 What operation would you like to perform ? pop The deleted value is: 90 What operation would you like to perform ? quit
동작 원리
이 구현의 핵심은 push 연산 시마다 두 큐의 역할을 교환하는 것입니다. 새로운 값은 항상 queue_1에 삽입되고, queue_2에 남아 있던 기존 요소들은 순서대로 queue_1 뒤로 이동합니다. 이후 두 큐의 참조를 서로 바꾸면, queue_2의 맨 앞에는 항상 가장 최근에 push된 값이 위치하게 됩니다. 그 결과 pop 연산은 큐에서 앞쪽 요소 하나만 제거하면 되므로 매우 효율적으로 처리됩니다.
즉, 이 방식은 push 비용이 O(n), pop 비용이 O(1)인 전형적인 두 큐 기반 스택 구현 패턴입니다.
코드 설명
'Stack_structure' 클래스: 생성 시 내부적으로 두 개의 빈 큐 인스턴스를 초기화합니다.
'check_empty' 메서드: 스택이 비어 있는지 여부를 확인합니다.
'push_val' 메서드: 새 요소를 스택에 추가(push)합니다.
'pop_val' 메서드: 스택에서 요소를 제거(pop)하고 반환합니다.
'Queue_structure' 클래스: 빈 리스트를 초기화하고 크기(size)를 0으로 설정합니다.
'check_empty' 메서드: 큐가 비어 있는지 확인합니다.
'enqueue_operation' 메서드: 큐의 뒤쪽에 요소를 추가합니다.
'dequeue_operation' 메서드: 큐의 앞쪽에서 요소를 제거하고 반환합니다.
'size_calculate' 메서드: 현재 큐에 저장된 요소의 개수를 반환합니다.
두 개의 큐 인스턴스: 'Queue_structure' 객체 두 개가 생성되어 스택의 내부 저장소로 사용됩니다.
사용자 인터페이스: 메뉴, push, pop, quit 네 가지 옵션을 제공합니다.
연산 처리: 사용자가 입력한 명령에 따라 스택 요소에 대한 연산이 수행됩니다.
결과 출력: 연산 결과가 콘솔 화면에 표시됩니다.