저는 현재 이 교재를 참고하여 공부 중이며, 이지스 퍼블리싱의 '자료구조와 함께 배우는 알고리즘 입문' 책도 함께 참고 중입니다.
스택의 기본
스택(Stack)은 기본적으로 데이터를 임시 저장하는 기본 자료구조라고 합니다. 교재에선 이를 아이스크림 콘으로 설명합니다.🍦
위 이미지처럼 아이스크림 아저씨가 아이스크림을 쌓으려면 '딸기->바닐라->카라멜' 맛으로 쌓아야 합니다. 하지만 딸기 맛을 먹으려면 '카라멜->바닐라->딸기' 맛 순서대로 먹어야 합니다.
구조가 마치 프링글스 통 같다고 생각하면 된다고 하네요. 입구와 출구가 하나인 구조, 그래서 이를 데이터의 입력과 출력으로 비교한다면 데이터의 입력과 출력 순서가 반대여서 LIFO라고 한다고 합니다. Last In First Out으로 후입선출 구조입니다.
스택의 원리
스택은 한쪽만 뚫려있는 구조라서 삽입과 추출이 한쪽에서만 진행됩니다.
스택에 데이터를 넣는 작업을 푸시(push)라고 하고, 스택에서 데이터를 꺼내는 작업을 팝(pop)이라고 합니다. 제일 윗부분은 top이 되고, 가장 아랫부분은 bottom이라고 합니다.
데이터 삽입: push
스택 5칸이 모두 빈 상태가 있습니다. 그러면 top은 값이 비어있으므로 -1로 지정해줍니다.
데이터를 하나 push하면 top은 1이 증가합니다. 그리고 2단계에서 증가시킨 top의 위치인 0번에 데이터를 삽입합니다.
데이터 추출: pop
스택에서 데이터를 pop하는 것은 맨 위에 있는 데이터를 꺼내는 과정입니다. 중간에 있는 데이터나 가장 아래에 있는 데이터를 먼저 꺼낼 수는 없습니다.
그래서 위에서부터 하나씩 추출하는 방식 뿐인데요. top이 가리키는 위치의 데이터를 꺼내고 top을 1씩 감소 시키는 방법이 있습니다.
스택의 간단 구현
5칸 짜리의 빈 스택 만들기
stack = [None, None, None, None, None] # 크기가 5칸인 빈 상태의 스택 생성
top = -1 # top은 아직 데이터가 없으므로 -1로 초기화(빈 상태)데이터 삽입: push
# 2. 데이터 삽입: push
# 생성한 스택에 데이터를 넣으려면 top을 1 증가시킨 후 데이터를 넣는다.
## 크기가 5칸인 스택의 생성과 데이터 3개 입력 ##
stack = [None, None, None, None, None]
top = -1
top += 1
stack[top] = '커피'
top += 1
stack[top] = '녹차'
top += 1
stack[top] = '꿀물' # top을 1씩 증가시키고, 해당 위치에 데이터를 삽입하는 과정
print('------스택 상태------')
for i in range(len(stack)-1, -1, -1):
print(stack[i])
# len(stack)-1은 스택의 맨 위쪽부터 -1씩 감소하면서 출력한다
# 즉, 4,3,2,1,0번째 데이터가 출력된다.데이터 추출: pop
# 3. 데이터 추출: pop
# 데이터가 3개 있는 스택에서 데이터를 추출하려면 top 위치의 데이터를 밖으로 추출한 후, top의 위치 데이터는 None으로 만들고 top을 1씩 감소시킨다.
## 스택에서 데이터 3개 추출 ##
stack = ['커피', '녹차', '꿀물', None, None]
top = 2
print('------스택 상태------')
for i in range(len(stack)-1, -1, -1):
print(stack[i])
print('---------------------')
data = stack[top] # 현재 top 위치의 데이터를 추출
stack[top] = None # top 위치에 None을 대입해서 데이터 삭제
top -= -1 # top을 1 감소 시킴
print('pop--->', data) # 추출한 데이터를 출력
data = stack[top]
stack[top] = None
top -= -1
print('pop--->', data)
data = stack[top]
stack[top] = None
top -= -1
print('pop--->', data)
print('---------------------')
print('------스택 상태------')
for i in range(len(stack)-1, -1, -1):
print(stack[i])결괏값
------스택 상태------
None
None
꿀물
녹차
커피
---------------------
pop---> 꿀물
pop---> None
pop---> None
---------------------
------스택 상태------
None
None
None
녹차
커피여기까지 스택의 기본 개념, 구조를 살펴 보았고 코드로 간단하게 구현까지 해보았습니다!
