[자료구조] 02. 큐(Queue)

큐(Queue)

큐는 먼저 입력한 데이터를 먼저 꺼내는 자료구조이다. FIFO(First-In, First-Out) 방식을 사용하는 자료구조라고도 할 수 있다.

이는 만약 우리가 식당에 줄을 서면 먼저 줄을 선 사람이 먼저 입장을 하는 것과 동일하다고 생각하면 될 것 같다.

위의 그림에 주요 용어들이 있는데, 설명하자면 아래와 같다.

• Enqueue : 큐에 값을 넣는 기능
• Dequeue : 큐에서 값을 꺼내는 기능
• head : 큐의 맨 앞 부분, front 라고도 함
• tail : 큐의 맨 뒷 부분, rear 라고도 함

 

큐에 값이 추가된다면, tail 위치에 값이 Enqueue 될 것이다. 그리고 값을 지운다면 head의 값이 Dequeue 될 것이다.

---

Enqueue

위의 그림처럼 큐는 선입선출 구조이고, head와 tail을 알고 있다. 그렇기 때문에 큐에 값을 추가할때 마지막 위치를 이미 알고 있기 때문에 tail에 값을 넣어주면 된다.  그렇기 때문에 추가 시, O(1)의 시간 복잡도를 갖게 된다.

---

Dequeue

삭제도 마찬가지로 선입선출 구조이고, 맨 앞 부분의 위치를 이미 head로 알고 있기 때문에, head를 바로 지우면 된다. 그렇기 때문에 삭제 역시 O(1)의 시간 복잡도를 갖게 된다.

---

시간 복잡도

• 추가, 삭제 : O(1)
• 검색 : O(n)