큐 (Queue)
저번 포스트 요약 — 스택
- 스택은 LIFO(Last In, First Out) 구조 — 마지막에 넣은 것이 먼저 나옴
push()/pop()/top()/empty()/size()pop()은 반환값 없음 → 값이 필요하면top()먼저 호출- 괄호 검사, 연속 중복 제거, DFS 구현에 활용
큐란
FIFO(First In First Out)의 구조를 가지는 자료구조.
줄을 서는 것처럼 먼저 큐에 들어온 원소가 먼저 빠져나간다.
기본 연산
| 함수 | 설명 | 시간복잡도 |
|——|——|———–|
| q.push(x) | 맨 뒤에 x 추가 | O(1) |
| q.pop() | 맨 앞 원소 제거 (반환값 없음) | O(1) |
| q.front() | 맨 앞 원소 반환 (제거 안 함) | O(1) |
| q.back() | 맨 뒤 원소 반환 (제거 안 함) | O(1) |
| q.empty() | 비어있으면 true | O(1) |
| q.size() | 원소 개수 | O(1) |
스택과 비교
- 스택:
top()— 맨 위(마지막에 넣은 것) 조회- 큐:
front()— 맨 앞(가장 먼저 넣은 것) 조회
마치며
뒤에서 삽입, 앞에서 삭제가 가능한 일반 큐와 달리, 앞뒤 양쪽에서 삽입/삭제가 가능한 덱(deque)이라는 자료구조도 있다는 걸 알았다.
인덱스로도 접근이 가능한 걸 보고 벡터와 비슷하다고 생각했다.