스택이란?
나중에 들어간 데이터가 먼저 나오는 후입선출(Last In First Out; LIFO)의 자료구조이다. 동전을 쌓고 뺄때는 무너지지 않게 위에서 부터 뺀다고 생각하면 쉽다. 일반적으로 저장소의 끝 부분(맨 위)을 탑(Top) 이라고 하고, 데이터를 추가하는 push 연산, 데이터를 꺼내는 pop 연산이 있다.
++함수의 호출도 스택을 기반으로 실행되므로 나중에 DFS(Depth First Search)를 구현할 때 따로 스택을 안쓰고 함수를 재귀적으로(recursion)만들어서 구현할 수 있다.
동작 과정
스택이 동작하는 과정을 간단히 보면 다음과 같다.
첫 번째 그림은 스택이 빈 상태이다.
두 번째 그림은 5를 push한 그림이다. 세 번째 그림은 1을, 네 번째 그림은 6을 push한 그림이다.
push 연산을 하면 이런식으로 위에 차곡차곡 쌓이게 된다.
top은 맨 위에 있는 값으로, 두 번째 그림의 top은 5, 세 번째 그림은 1, 네 번째 그림은 6이다.
다섯 번째 그림은 pop 연산을 한 결과인데, 맨 위에 있는(top) 값을 빼준다. 이 그림에서는 top이었던 6을 빼 준뒤, 1이 가장 위에 있으므로 top은 1이 된다.
코드
코드로 구현해보면 다음과 같다.
#python list 이용
class Stack:
def __init__(self): #Stack class 호출시 초기화
self.stack = []
def push(self, value=None): #push()할 value값이 있으면 stack에 추가
if value == None:
return False
else:
self.stack.append(value)
def pop(self): #stack의 길이가 0이면 False(에러)
if len(self.stack) == 0:
return False
else:
return self.stack.pop() #아니면 맨 뒤의 데이터 빼주고 리턴
def top(self):
if len(self.stack) == 0:
return False
else:
return self.stack[-1] #top()이니까 맨 뒤(맨 위)의 원소 리턴
def clear(self):
self.stack = [] #지우기, stack list 초기화
def draw(self):
for x in self.stack: #그리기, stack list에 있는 데이터들 출력
print(x,end=' ')
print()
#test
s = Stack()
s.push(5)
s.draw()
s.push(1)
s.draw()
s.push(6)
s.draw()
s.pop()
s.draw()