02 스택과 큐
- 데이터를 임시 저장하는 기본 자료구조
02-1 스택 (Stack)
: 데이터를 임시 저장할 때 사용하는 자료구조로, 데이터의 입력과 출력 순서는 후입선출(LIFO) 방식이다.
- top: stack의 꼭대기 # 여기에 push, pop한다.
- bottom: stack의 바닥
- push: 데이터 추가
- pop: (꼭대기) 데이터 꺼냄
- 스택 배열: 푸시한 데이터를 저장하는 스택 본체 list형 배열
- 스택 크기(capacity): len(스택 배열)
- 스택 포인터(stack pointer)
: 스택에 쌓여 있는 데이터의 개수를 나타내는 정숫값
- 빈 스택: ptr = 0
- 가득 찬 스택: ptr = capacity
+ 파이썬에서는 List로 스택을 흉내낸다고 한다.
# init stack
stack = []
# capacity
cap = len(stack)
# push
stack.append(a)
# pop
top = stack.pop()
# top - 원소 삭제 없이 가져오기
top = stack[-1]
+ list, deque로 stack을 구현할 수 있다.
02-2 큐 (Queue)
: 스택과 같이 데이터를 임시 저장하는 자료구조이지만, 스택과 달리 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출(FIFO) 구조이다.
- enqueue: (rear) 데이터를 추가
- dequeue: (front) 데이터를 꺼냄