교재 - 파이썬으로 배우는 자료구조(저자 유석종)
1. 스택이란?
`스택`은 선형리스트(linear list)의 특별한 형태.
책 또는 접시와 같이 한쪽 방향으로 쌓아 놓은 구조를 말함. 예를 들어, 접시를 쌓을 때는 스택 맨 위에 놓게 되고 꺼낼 때는 맨 위의 접시를 먼저 꺼냄. 이처럼 스택은 나중에 들어가는 원소가 먼저 나오는 `후입 선출` (LIFO : Last-In, First-Out) 구조인 것.
--> 함수 호출 관리, 문법 검사(syntax checking), 수식 평가(expression evaluation) 등의 문제를 해결하는데 적합함.
스택S는 다음과 같이 원소들의 리스트로 표현이 가능함.
여기서 a_0은 스택의 맨 처음 추가된 원소이고, a_(n-1)은 마지막으로 추가된 원소임.
S = [a0, a1, a2 .... a_(n-1)]
`top`은 마지막으로 추가된 원소 a_(n-1) 를 가리키는 스택 포인터 변수임.
2. 스택의 구현
`push` : 스택에 원소를 추가하는 연산.
`pop` : 스택에서 원소를 삭제하는 연산.
리스트가 아닌 정적 배열에 스택을 구현하는 경우, posh 함수는 스택에 원소를 추가하기 전에 스택 풀(stack full) 상태인지 아닌지 검사해야 함.
pop 함수는 스택에서 원소를 꺼내기 전에 스택이 빈 상태(empty stack)가 아닌지 검사함.
정적 배열 스택에서는 top변수가 -1이면 빈 스택을 의미.
# 4.1. 스택의 구현
print("4.1. 스택의 구현")
class Stack:
def __init__(self, size):
self.stack = [None]*size # size만큼 빈 공간 만들기
self.top = -1 # top은 스택의 맨 위 인덱스 (-1이면 비어있다는 뜻)
self.size = size
self.view()
def push(self, item): # push: 스택에 넣기
if self.top < self.size-1: # full 스택이 아니면
self.top += 1 # top을 하나 올리고
self.stack[self.top] = item # 해당 위치에 item 저장
def pop(self): # pop: 스택에서 꺼내기
if self.top > -1: # empty 스택이 아니면
item = self.stack[self.top] # 현재 top 위치 값을 꺼냄
self.stack[self.top] = None # 그 자리를 비움
self.top -= 1 # top을 한 칸 내림
return item # 가장 마지막에 넣은 값을 꺼내고 top을 줄이는 함수
else: print("Stack empty") # empty 스택이면 메세지 출력
def view(self): # 스택 상태 출력
print(self.stack, end=' ') # 스택 리스트와
print('(%d)' % (self.top)) # top위치를 같이 출력하는 함수
s = Stack(5) # 크기 5짜리 스택을 만들기
for item in [3, 4, 5, 6, 7, 8]: # 스택이 5칸이라서 8에서 스택 풀(stack full)오류 발생
s.push(item)
s.view()
for i in range(6): # 6번 꺼내려고 하지만 실제로는 5개 밖에 없음 마지막에 스택엠티 메세지.
print(s.pop(), end = ' ')
s.view()
# 출력 결과
[None, None, None, None, None] (-1)
[3, None, None, None, None] (0)
[3, 4, None, None, None] (1)
[3, 4, 5, None, None] (2)
[3, 4, 5, 6, None] (3)
[3, 4, 5, 6, 7] (4)
[3, 4, 5, 6, 7] (4)
7 [3, 4, 5, 6, None] (3)
6 [3, 4, 5, None, None] (2)
5 [3, 4, None, None, None] (1)
4 [3, None, None, None, None] (0)
3 [None, None, None, None, None] (-1)
Stack empty
None [None, None, None, None, None] (-1)
push는 이해가는데 pop이 완전히 이해 안가서 좀더 공부하기.
1번째 pop
top = 4, item = 7
꺼낸 후엔 top = 3, stack = [3, 4, 5, 6, None]
2번째 pop
top = 3, item = 6
꺼낸 후엔 top = 2, stack = [3, 4, 5, None, None]
(생략)
5번째 pop
top = 0, item = 3
꺼낸 후 top = -1, stack = [None, None, None, None, None] --> 이제 비었음!
6번째 pop
top = -1 비었음.
Stack empty 출력.