스택
1. 스택의 개념
-
일반적인 의미: 물건이 쌓여있는 더미(Stack)
-
자료구조에서의 의미: 자료 더미 + LIFO 방식(동적인 특징)
-
LIFO(Last-In-First-Out): 후입선출 방식을 말한다.
- Top: 가장 최근에 저장한 원소
- 연산(동작 명령)에 따라 Top에서 변화가 일어난다
2. 스택 추상 자료형
추상 자료형
- 자료구조에서 인터페이스(자료의 특징, 연산)를 제공하는 것
스택 추상 자료형
스택 생성: 스택을 생성한다.- 스택의 크기 n 필요 (배열로 스택을 구현하는 경우)
push: 새로운 자료를 추가하는 연산- 스택이 가득 차 있는지 여부를 확인해야 한다.
- (넘침(Overflow) 현상을 주의해야 한다.)
스택오버플로우(Stack Overflow): 용량 제한으로 더 이상 원소를 추가하지 못할 때 발생한다.
pop: 가장 늦게 들어온 자료(최상위 자료)를 제거하는 연산- 스택이 비어있는지 여부를 확인해야 한다.
- (부족(Underflow) 현상을 조심해야 한다.)
- 부족 현상: 스택에 더 이상 저장된 원소가 없을 때 발생한다.
peek: 가장 늦게 들어온 자료(최상위 자료)를 읽은 후 이를 반환하는 연산 (제거 x)- 스택이 비어있는지 여부를 확인해야 한다.
- (부족(Underflow) 현상을 조심해야 한다.)
스택 삭제: 스택을 제거한다.
3. 사용 예
- 수식 계산 알고리즘
- 괄호 짝 맞추는 문제
- 역순 문자열
- 미로 알고리즘
- 실행 취소
- DFS (깊이 우선 탐색) 알고리즘
4. 파이썬 리스트로 스택 구현
구현
# 파이썬의 리스트(list)를 이용하여 스택을 구현
class Stack:
# 빈 리스트로 스택 생성
def __init__(self):
self.data = []
# 스택 크기 반환
def __len__(self):
return len(self.data)
# 스택의 내부 자료를 문자열로 변환하여 반환
def __str__(self):
return str(self.data[::1])
# 스택이 비어있는지 체크
def is_empty(self):
return len(self.data) == 0
# 스택에 새로운 자료 추가
def push(self, item):
self.data.append(item)
# 스택의 최상위 자료 제거
def pop(self):
# 스택이 비어있는지 반드시 체크
if self.is_empty():
print("Stack Underflow")
exit()
# 비어있지 않으면 최상위 자료를 제거 후 반환
return self.data.pop(-1)
# 스택의 최상위 자료 읽기(제거 x)
def peek(self):
# 스택이 비어있는지 반드시 체크
if self.is_empty():
print("Stack Underflow")
exit()
# 비어있지 않으면 최상위 자료를 읽은 후 반환
return self.data[-1]
# 스택에 자료가 포함되어 있는지 여부 반환
def contains(self, item):
return item in self.data
# 스택 클리어
def clear(self):
self.data = []
실행
# 스택 생성
stack = Stack()
# 스택 크기 출력
# 0
print(len(stack))
# 스택 비어있는지 여부 출력
# True
print(stack.is_empty())
# 스택에 자료 추가
stack.push(1)
stack.push(2)
# 스택 출력
# [1, 2]
print(stack)
# 스택에 자료 포함되어 있는지 여부 출력
# True
print(stack.contains(1))
# 최상위 자료 제거
stack.pop()
# 스택 출력
# [1]
print(stack)
# 최상위 자료 읽기
# 1
print(stack.peek())
# 스택 클리어
stack.clear()
# 스택 비어있는지 여부 한 번 더 확인
# True
print(stack.is_empty())5. 스택과 큐 구현 비교
| 자료구조 | 동작 | 코드 | 설명 |
|---|---|---|---|
| 스택 | 초기화 | stack = [] | 빈 리스트를 만듦 |
| 자료 추가(push) | stack.append(data) | 리스트의 맨 뒤에 자료를 추가 | |
| 자료 삭제(pop) | data = stack.pop() | 리스트의 맨 뒤에서 자료를 꺼냄 | |
| 큐 | 초기화 | queue = [] | 빈 리스트를 만듦 |
| 자료 추가(enqueue) | queue.append(data) | 리스트의 맨 뒤에 자료를 추가 | |
| 자료 삭제(dequeue) | data = queue.pop(0) | 리스트의 맨 앞(0번 위치)에서 자료를 꺼냄 |
