개발/CS study
[알고리즘] 스택, 큐
물만난동그리
2023. 6. 23. 23:32
728x90
스택 Stack
- 마지막에 넣은 것이 - 먼저 나온다
- stack의 top: 삽입과 삭제가 일어나는 위치
- s.append(data): top 위치에 새로운 데이터 삽입
- s.pop(): top 위치의 현재 데이터를 삭제하고 확인
- s[-1]: top 위치의 현재 데이터를 단순 확인
- DFS: 깊이 우선 탐색
- 백트래킹 종류
- 재귀 알골과 일맥상통
큐 Queue
- 먼저 들어온 것이 - 먼저 나간다
- 파이썬에서 deque를 이용하여 큐를 구현 (import collections)
- stack의 top과 달리, rear(가장 끝)와 front(가장 앞)가 있음
- s.append(data): rear에 새로운 데이터 삽입
- s.popleft(): front 부분의 데이터를 삭제하고 확인
- s[0]: 큐의 맨 앞(front) 데이터 확인
- BFS: 너비 우선 탐색
- 우선순위 큐: 값이 들어간 순서와 상관 없이 우선순위가 높은 데이터가 먼저 나옴. ⇒ front에 항상 최댓값 또는 최솟값
- 힙(heap)을 이용해 구현.
728x90