7. 스택(Stack)
스택(Stack)은 한쪽 끝에서만 자료의 삽입과 삭제가 이루어지는 선형 자료구조임.
이러한 특성으로 스택은 후입선출(Last-In-First-Out, LIFO) 구조를 가짐.
스택은 일상 생활에서 쌓여있는 접시나 책을 생각하면 이해하기 쉬운데,
가장 마지막에 쌓인 접시나 책을 먼저 가져오게 되는 것과 같은 원리임.
스택은 보통 "push"와 "pop" 두 가지 기본 연산을 지원함.
"push" 연산은 스택의 가장 위에 원소를 추가하는 작업을 의미하며,
"pop" 연산은 스택의 가장 위에 있는 원소를 제거하고 반환하는 작업을 의미함.
스택의 맨 위에 있는 원소를 확인하는 연산인 "top"이나 "peek"도 지원할 수 있음.
스택은 여러 가지 응용 분야에서 유용하게 활용될 수 있음.
예를 들어, 함수의 호출과 복귀에 사용되는 함수 호출 스택(Call Stack)이 있음.
또한, 수식의 괄호 검사, 웹 브라우저의 방문 기록(뒤로 가기), 텍스트 에디터의 실행 취소/다시 실행 등에도
스택이 활용될 수 있음.
스택은 간단한 구조이지만 다양한 알고리즘과 데이터 구조의 구현에 필수적인 요소로 사용됨.
'재귀적인 구조'를 가진 함수의 예시 # a() 함수가 호출되면, b() 함수를 호출하고, 'end : a'를 출력. def a(): b() print('end : a') # b() 함수가 호출되면, c() 함수를 호출하고, 'end : b'를 출력. def b(): c() print('end : b') # c() 함수가 호출되면, 실행문을 수행하여 'end : c'를 출력. def c(): # 실행문 print('end : c') # 이후 c() 함수가 종료되면, b() 함수의 실행이 이어지고, 'end : b'를 출력. # 마찬가지로 b() 함수가 종료되면, a() 함수의 실행이 이어지고, 'end : a'를 출력. a() 이러한 구조는 함수 호출의 연쇄적인 흐름을 통해 실행되며, a() 함수를 시작으로 b() 함수, c() 함수가 차례대로 호출되고 종료되면서 결과가 출력됨. 이러한 재귀적인 호출 구조는 프로그래밍에서 흔히 사용되는 패턴 중 하나임. |
7-1. ADT(Abstract Data Type)
ADT는 Abstract Data Type(추상 자료형)의 약어임.
ADT는 데이터와 그 데이터를 조작하기 위한 연산들을 논리적으로 정의한 개념이지만,
데이터의 구체적인 구현 방법에 대해서는 언급하지 않으며, 동작에 대한 명세를 제공함.
한마디로, '연산이 가능한 동작을 가정한 것'임.
ADT의 대표적인 예시들로는 List, Stack, Queue가 있음.
스택(Stack) 역시 ADT의 한 예로, 해당 동작을 추상화한 것이며
스택이 가져야 할 데이터와 지원해야 할 연산들을 정의함.
스택(Stack)의 일반적인 정의:
데이터: 일렬로 나열된 원소들을 저장하는 자료구조로, 각 원소는 데이터 요소를 포함할 수 있음.
연산: 스택의 기본적인 동작을 추상화하고 스택을 사용하는 코드에서 일관성 있게 접근하게 함.
Push(item): 스택의 맨 위에 새로운 항목(item)을 추가.
Pop(): 스택의 맨 위에 있는 항목을 제거하고 반환.
Peek(): 스택의 맨 위에 있는 항목을 반환하지만 제거하지는 않음.
IsEmpty(): 스택이 비어 있는지 여부를 확인.
Size(): 스택에 저장된 항목의 수를 반환.
ADT는 프로그래밍 언어나 구현 방법에 따라 구체화될 수 있으며,
스택 ADT의 구체적인 구현은 배열, 연결 리스트 등을 사용하여 구현될 수 있음.
7-2. 구현: 배열
배열(Array)을 사용한 스택 구현:
배열은 연속된 메모리 공간에 원소를 저장하는 자료구조.
배열을 사용하여 스택을 구현할 때는
고정된 크기의 배열을 생성하고, 배열의 인덱스를 이용하여 스택의 상단을 가리키는 top 포인터를 관리함.
배열을 사용한 스택은 인덱스를 통한 원소 접근이 빠르지만,
배열의 크기를 변경하기 어렵고, 고정된 크기를 초과하는 원소를 저장할 수 없음.
7-2-1. 의사 코드
사고 과정을 명확히 하기
추사정 기능과 구체적 코드의 중간 설계
1) 필수요소
stack = [ ] : 스택의 원소들을 저장할 빈 리스트(list)
top: 스택의 가장 상단에 위치한 원소를 가리키는 변수.
배열의 끝(마지막)부분을 의미하며, 스택에 새로운 원소를 추가할 때는 top의 위치를 변경함.
top 변수를 사용하여 스택의 가장 최근에 추가된 원소를 가리킬 수 있음.
스택에 원소를 추가할 때는 top을 하나 증가시키고, 스택에서 원소를 제거할 때는 top을 하나 감소시킴.
따라서 top 변수를 사용하여 스택의 상태를 추적하고 조작할 수 있음.
2) 메서드
.push(x) : 맨 윗부분에 원소 x를 추가
| def push(self, x): self.stack.append(x) |
.top() : 맨 윗부분에 있는 원소를 알려줌
def top(self): if self.is_empty(): return None else: return self.stack[-1] # self.stack[-1]: 스택의 가장 마지막 원소를 가리키는 인덱스. (스택은 후입선출구조이다) |
.pop() : 맨 윗부분에 있는 원소를 삭제하면서 알려줌
def pop(self): return self.stack.pop() |
.is_empty() : 스택이 비어있는지 확인
def is_empty(self) -> bool: # -> bool: is_empty() 메서드가 bool 타입의 값을 반환한다는 의미. return not bool(self.stack) # bool(self.stack): self.stack이 비어있지 않으면 True를 반환하고, 비어있으면 False를 반환. 을 사용하거나, return len(self.stack) == 0 # len(self.stack) == 0: self.stack의 길이가 0인지 확인하는 조건. |
.pop_all() : 스택을 깨끗이 비움
def pop_all(self): self.stack = [ ] |
7-2-2. 실제 코드
class ArrayStack:
def __init__(self):
self.stack = [ ]
def push(self, x):
self.stack.append(x)
def pop(self):
return self.stack.pop()
def top(self):
if self.is_empty():
return None
else:
return self.stack[-1]
def is_empty(self) -> bool:
return not bool(self.stack)
def pop_all(self):
self.stack.clear()
def print_stack(self):
print('위부터 순서대로 : ', end = '')
for i in range(len(self.stack) - 1, -1, -1):
# len(self.stack)-1부터 시작하여 -1까지 반복하며, 증감 값은 -1. 역순으로 원소에 접근하는 방법.
print(self.stack[i], end = ' ')
print()
7-2-3. 테스트
ast = ArrayStack()
print(ast.top()) # 아직 stack에 아무것도 없는 상태이므로 None이 출력.
print(ast.is_empty()) # 따라서 is_empty값도 True.
ast.push(100)
ast.push(200)
print(f'맨 위 : {ast.top()}') # stack에 100과 200을 입력. 마지막 값이 200이므로 top에는 200이 존재.
print(ast.pop()) # 마지막 값인 200을 삭제하여 반환한 결과
ast.push('파이썬')
ast.print_stack() # 다시 '파이썬'이라는 값을 stack에 입력 후 위부터 순서대로 출력
print(ast.is_empty()) # 이제 더이상 stack은 비어있지 않으므로 False가 출력
7-3. 구현: 연결리스트
연결리스트(Linked List)를 사용한 스택 구현:
연결리스트는 노드들이 링크로 연결되어 있는 자료구조.
연결리스트를 사용하여 스택을 구현할 때는 각 노드가 원소와 다음 노드를 가리키는 링크를 가지고 있음.
스택의 상단을 가리키는 top 포인터는 연결리스트의 첫 번째 노드를 가리킴.
연결리스트를 사용한 스택은 동적으로 크기가 조정될 수 있고, 메모리를 효율적으로 사용할 수 있음.
하지만 배열에 비해 포인터 연산이 추가로 필요하므로 약간의 오버헤드가 발생할 수 있음.
7-3-1. 의사 코드
필수요소
Linked_list_stack = LinkedList() : 연결리스트를 사용하여 구현된 스택(Stack)의 객체를 생성하는 부분.
연결리스트 기반 스택을 생성하고, Linked_list_stack 변수가 해당 스택 객체를 참조하도록 함.
top: 스택의 가장 상단에 위치한 원소를 반환하는 기능을 수행하는 메서드. 기능은 배열과 동일.
메서드
.push(x) : 맨 윗부분에 원소를 추가
def push(self, x): self.linked_list_stack.insert(0, x) |
.top() : 맨 윗부분에 있는 원소를 알려줌
def top(self): if self.is_empty(): return None else: return self.linked_list_stack.get(0) # get(0): 연결리스트의 가장 앞에 있는 항목을 가져옴 |
.pop() : 맨 윗부분에 있는 원소를 삭제하면서 알려줌
def pop(self): return self.linked_list_stack.pop(0) # pop(0): 연결리스트의 가장 앞에 있는 항목을 제거하고 반환 |
.is_empty() : 스택이 비어있는지 확인
def is_empty(self): return self.linked_list_stack.is_empty() |
pop_all() : 스택을 깨끗이 비운다.
def pop_all(self): self.linked_list_stack.clear() |
7-3-2. 실제 코드
from 연결리스트 import ListNode, LinkedListBasic
class LinkedStack:
def __init__(self):
self.llist = LinkedListBasic()
def push(self, new_item):
self.llist.insert(0, new_item)
def pop(self):
return self.llist.pop(0)
def top(self):
if self.is_empty():
return None
else:
return self.llist.get(0)
def is_empty(self) -> bool:
return self.llist.is_empty()
def pop_all(self):
self.llist.clear()
def print_stack(self):
print('위부터 순서대로 : ', end = '\n')
for i in range(self.llist.size()): # 스택에 저장된 항목을 위에서부터 순서대로 출력하는 for문
print(self.llist.get(i), end = ' \n')
print()
7-3-3. 테스트
lst = LinkedStack()
print(lst.top())
print(lst.is_empty())
lst.push(100)
lst.push(200)
print(f'맨 위 : {lst.top()}')
print(lst.pop())
lst.push('파이썬')
lst.print_stack()
print(lst.is_empty())
