스택(Stack)은 LIFO(Last In, First Out, 나중에 들어온 것이 먼저 나감) 방식으로 동작하는 자료구조이고, 큐(Queue)는 FIFO(First In, First Out, 먼저 들어온 것이 먼저 나감) 방식으로 동작합니다. 두 자료구조의 성질이 정반대이기 때문에, 큐 하나만으로 스택을 구현하려면 약간의 트릭이 필요합니다. 핵심 아이디어는 push할 때는 그대로 큐에 삽입하고, pop할 때는 큐의 원소들을 한 바퀴 회전시켜 가장 마지막에 들어온 원소를 맨 앞으로 보낸 뒤 제거하는 것입니다.
아래 예제에서는 'Stack_structure' 클래스와 'Queue_structure' 클래스를 정의하고, 각각 스택과 큐에 값을 추가·삭제하는 메서드를 구현했습니다.
예제 코드
class Stack_structure:
def __init__(self):
self.q = Queue_structure()
def check_empty(self):
return self.q.check_empty()
def push_val(self, data):
self.q.enqueue_operation(data)
def pop_val(self):
for _ in range(self.q.size_calculate() - 1):
dequeued = self.q.dequeue_operation()
self.q.enqueue_operation(dequeued)
return self.q.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('The 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 89
What operation would you like to perform ? push 43
What operation would you like to perform ? push 76
What operation would you like to perform ? push 56
What operation would you like to perform ? pop
The deleted value is : 56
What operation would you like to perform ? quit
코드 설명
'Stack_structure' 클래스가 생성되며, 내부에 비어 있는 Queue_structure 객체를 초기화합니다.
'check_empty' 메서드는 스택이 비어 있는지 여부를 확인합니다.
'push_val' 메서드는 스택에 요소를 추가(push)합니다.
'pop_val' 메서드는 스택에서 요소를 삭제(pop)합니다. 내부적으로는 큐 크기보다 하나 적은 횟수만큼 dequeue 후 다시 enqueue를 반복해 마지막 원소를 맨 앞으로 이동시킨 뒤 제거하므로, 시간 복잡도는 O(n)입니다.
'Queue_structure' 클래스는 빈 리스트와 함께 size 변수를 0으로 초기화합니다.
'check_empty' 메서드는 큐가 비어 있는지 여부를 확인합니다.
'enqueue_operation' 메서드는 큐에 요소를 추가하고 size를 1 증가시킵니다.
'dequeue_operation' 메서드는 큐의 맨 앞 요소를 제거해 반환하며, size를 1 감소시킵니다.
'size_calculate' 메서드는 현재 큐의 크기를 반환합니다.
'Stack_structure' 클래스의 인스턴스가 생성됩니다.
사용자에게 push, pop, quit 메뉴 옵션이 제공됩니다.
사용자가 입력한 명령에 따라 스택 연산이 수행되고, 그 결과가 콘솔에 출력됩니다.