스택(Stack) 자료구조를 재귀(Recursion)를 이용해 뒤집어야 하는 경우, 값을 추가하고 삭제하며 스택의 요소를 출력하는 기본 메서드들과 함께 stack_reverse 메서드를 정의하면 손쉽게 구현할 수 있습니다.
아래 예제를 통해 실제 구현 방법을 살펴보겠습니다.
예제 코드
class Stack_structure:
def __init__(self):
self.items = []
def check_empty(self):
return self.items == []
def push_val(self, data):
self.items.append(data)
def pop_val(self):
return self.items.pop()
def print_it(self):
for data in reversed(self.items):
print(data)
def insert_bottom(instance, data):
if instance.check_empty():
instance.push_val(data)
else:
deleted_elem = instance.pop_val()
insert_bottom(instance, data)
instance.push_val(deleted_elem)
def stack_reverse(instance):
if not instance.check_empty():
deleted_elem = instance.pop_val()
stack_reverse(instance)
insert_bottom(instance, deleted_elem)
my_instance = Stack_structure()
data_list = input('Enter the elements to add to the stack: ').split()
for data in data_list:
my_instance.push_val(int(data))
print('The reversed stack is:')
my_instance.print_it()
stack_reverse(my_instance)
print('The stack is:')
my_instance.print_it()실행 결과
Enter the elements to add to the stack: 23 56 73 81 8 9 0 The reversed stack is: 0 9 8 81 73 56 23 The stack is: 23 56 73 81 8 9 0
코드 설명
빈 리스트를 초기화하는 Stack_structure 클래스가 생성됩니다.
check_empty 메서드는 스택이 비어 있는지 여부를 확인합니다.
push_val 메서드는 스택에 새로운 요소를 추가합니다.
pop_val 메서드는 스택에서 요소를 제거하고 반환합니다.
print_it 메서드는 스택의 모든 요소를 콘솔에 출력합니다.
insert_bottom 메서드는 기본 동작처럼 스택의 맨 위에 추가하는 대신, 재귀 호출을 통해 요소를 스택의 맨 아래에 삽입합니다.
stack_reverse 메서드는 주어진 스택 전체를 뒤집는 핵심 역할을 담당합니다.
이후 Stack_structure 클래스의 인스턴스가 하나 생성됩니다.
사용자로부터 스택에 넣을 요소들을 입력받습니다.
입력된 값들을 순회하면서 스택에 차례대로 추가하고, 콘솔에 출력합니다.
그다음 stack_reverse 메서드를 호출하여 스택을 뒤집습니다.
마지막으로 print_it 메서드를 호출해 뒤집힌 결과를 콘솔에 표시합니다.
재귀의 동작 원리
insert_bottom 함수는 스택이 빌 때까지 요소를 하나씩 꺼낸 후(pop), 데이터를 맨 아래에 넣고, 꺼냈던 요소들을 다시 원래 순서대로 쌓아 올립니다(push). stack_reverse 함수는 스택의 모든 요소를 재귀적으로 꺼낸 뒤 각각을 맨 아래에 삽입함으로써 전체 스택의 순서를 뒤집게 됩니다.