스택과 큐

1. 스택

- LIFO (Last in,First Out)
  - 마지막에 들어간 데이터가 가장 먼저 나오는 구조
- push - 삽입
- pop - 삭제

stack=[]
stack.append(1)
stack.append(2)
stack.append(3)
stack.pop(3)

 2. 큐(Queue)

- FIFO(First In, First Out)
  - 먼저 들어간 데이터가 나옴
  - Enqueue: 큐의 맨 뒤에 데이터 삽입
  - Deque : 큐의 맨 앞에 데이터 삭제

from collections import deque

queue=deque()
queue.append(1)
queue.popleft() #1제거

 

3. 어떨때 큐를 쓰고 스택을 써야하는가?

 

큐(Queue)를 사용하는 경우

- FIFO(First In, First Out) : 먼저 들어온 것이 먼저 나감

- 대표적인 문제 유형 : BFS(최단 거리 탐색 문제 - 미로 찾기, 숨바꼭질 문제), 그래프에서 특정 레벨의 노드들을 순서대로 방문해야하는 경우, 시뮬레이션 (프로세스 스케줄링, 은행 대기줄, 데이터가 순서대로 처리되어야하는 경우), 슬라이딩 윈도우 최댓값 문제(특정 범위 내에서 특정 최댓값을 찾아야할때)

 

스택(Stack)을 사용하는 경우

- LIFO(Last In,First Out) : 나중에 들어온 것이 먼저 나감

- 대표적인 문제 유형: DFS(깊이 우선 탐색), 괄호 문제