[실전 알고리즘] 큐

정의와 성질

저번에 정리한 스택이랑 이번에 배울 큐랑 비슷한게 많다.

 

큐는 한쪽 끝에서 원소를 넣고 반대쪽 끝에서 원소를 뺄 수 있는 자료구조이다. 스택에서는 먼저 들어간 원소가 나중에 나왔는데

큐에서는 먼저 들어간 원소가 먼저 나오게 된다. 

스택을 FILO(First In Last Out)이라고 한 것과 비슷하게 큐를 FIFO(First In First Out)이라고 하기도 한다.

---

큐의 성질

1. 원소의 추가가 O(1)
2. 원소의 제거가 O(1)
3. 제일 앞/뒤의 원소 확인이 O(1)
4. 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능

스택에서는 보통 원소가 추가되고 제거되는 곳을 top이라고 부르고, 원소가 위 아래로 배치된 것으로 생각을 많이 하는데 큐에서

추가되는 곳을 rear, 즉 뒤 쪽이라고 하고 제거되는 쪽을 front 라고 한다.

 

4번 성질은 스택과 비슷한 맥락으로 큐라는 자료구조에서는 인덱스를 가지고 원소에 접근하는 기능이 없지만, 배열을 가지고 직접만들 땐 해당 기능이 가능하도록 구현을 할 수 있다 정도로 요약이 가능하다. (단, STL queue에는 인덱스로 내부 원소를 접근하는 기능이 없다.)