스택 & 큐
- Stack & Queue는 데이터를 임시 저장 하기 위해서 사용하는 자료구조
- 데이터를 입력하고 출력하는 방향이 정해져 있다.

기본 개념
Stack
- 선입선출 (FILO = First In Last Out)
- Python에서 스택을 구현할 땐 별도의 라이브러리 없이 리스트 자료형을 사용한다.
- 삽입 : append()
- 삭제 : pop()
개념 예제 코드
stack = []
stack.append(5)
stack.append(2)
stack.append(3)
stack.append(7)
stack.pop()
stack.append(1)
stack.append(4)
stack.pop()
print(stack)
print(stack[::-1])
print(stack[-1])
Stack 결과
[5, 2, 3, 1]
[1, 3, 2, 5]
1
Queue
- 선입선출(FIFO = First In First Out)
- Python에서 Queue를 구현할 때 사용하는 방법은 3가지가 있다.
1. 리스트
2. Queue 사용
3. dequeue 클래스 사용
사용방법
- 리스트
- 데이터를 넣는 enqueue를 append()
- 데이터를 뺴는 dequeue를 pop()
- 리스트에서 pop()은 O(n)의 시간복잡도를 가지기 때문에 큐를 구현할 땐 더 효율적인 방법을 사용한다.
- Queue 사용
- queue모듈의 Queue는 데이터를 단방향에서 추가하고 제거할 수 있는 자료구조이다.
- 데이터를 넣는 enqueue를 put()
- 데이터를 빼는 dequeue를 get()
- Queue 사용에서 get()은 O(1)의 시간복잡도를 가지기에 효율성이 좋다. ([시간복잡도] 리스트 < Queue 사용)
- deque 클래스 사용
- double - ended queue
- collections 모듈의 deque는 데이터를 양방향에서 추가하고 제거할 수 있는 자료구조이다.
- 양방향이기에 append(), pop() 뿐만 아니라 appendleft(), popleft() 가능 하고 각각 맨 앞에 데이터를 삽입하거나 맨 앞에서 제거가 가능하다.
- appendleft(), popleft()는 각각 O(1)의 시간복잡도를 가지기에 효율성이 좋다.([시간복잡도] 리스트 <= Queue사용, deque 클래스 사용)
개념 예제 코드
from collections import deque
queue = deque()
queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7)
queue.popleft()
queue.pop()
queue.appendleft(10)
queue.append(1)
queue.append(4)
queue.popleft()
print(queue)
Queue 결과
deque ([2, 3, 1, 4])
활용 예시
Stack
- 웹 브라우저 방문기록 (뒤로가기)
- 역순 문자열 만들기
- 후위 표기법 계싼
- 괄호 검사
Queue
- 우선순위가 같은 작업 예약
- 은행업무
- 콜센터 고객 대기시간
- 프로세스 관리
- 너비 우선 탐색(BFS) 구현
- 캐시(Cache) 구현