[알고리즘] 스택, 큐

스택 Stack

1. 마지막에 넣은 것이 - 먼저 나온다
2. stack의 top: 삽입과 삭제가 일어나는 위치
3. s.append(data): top 위치에 새로운 데이터 삽입
4. s.pop(): top 위치의 현재 데이터를 삭제하고 확인
5. s[-1]: top 위치의 현재 데이터를 단순 확인

• DFS: 깊이 우선 탐색
• 백트래킹 종류
• 재귀 알골과 일맥상통

 

큐 Queue

1. 먼저 들어온 것이 - 먼저 나간다
2. 파이썬에서 deque를 이용하여 큐를 구현 (import collections)
3. stack의 top과 달리, rear(가장 끝)와 front(가장 앞)가 있음
4. s.append(data): rear에 새로운 데이터 삽입
5. s.popleft(): front 부분의 데이터를 삭제하고 확인
6. s[0]: 큐의 맨 앞(front) 데이터 확인

• BFS: 너비 우선 탐색
• 우선순위 큐: 값이 들어간 순서와 상관 없이 우선순위가 높은 데이터가 먼저 나옴. ⇒ front에 항상 최댓값 또는 최솟값
  • 힙(heap)을 이용해 구현.

https://youtu.be/JwOFYxirPPU