[자료구조] 큐(Queue)란?

개요

---

큐(Queue)는 선입선출(First-In Firut-Out) 방식의 선형 자료구조이다.

모양은 사람들이 줄을 서있는 모습을 생각하면 이해가 편하다.

---

구조

---

큐의 구조

큐는 위의 모양과 같은 구조를 가진다.

enqueue : 아이템을 삽입한다. 아이템 삽입은 rear큐에서 이루어진다.

dequeue : 데이터를 삭제한다. front큐에서 이루어진다.

 

operation은 2가지가 있다.

front operation은 모든 삭제가 발생하는 큐이다.

rear operation은 삽입이 발생한다.

 

큐는 선형 큐와 원형 큐의 2가지 형태가 있다.

---

선형 큐

---

비어있는 선형 큐

선형큐는 기본적으로 위의 사진으로 표현할 수 있다.

큐가 비어 있을 땐 front와 rear 포인터가 같은 공간을 가르킨다.

선형 큐에는 큰 문제점이 있는데, 이는 이제부터 비어있는 선형 큐에 3, 9, 1이라는 숫자를 enqueue, dequeue하면서 알아보겠다.

선형 큐의 문제점

3, 9, 1을 enqueue, dequeue 해보았다.

마지막에 1를 enqueue하고 나서 앞에 1개의 공간이 있음에도 불구하고 더는 enqueue를 할 수 없다.

이러한 문제점을 해결하기 위해 원형 큐가 존재한다.

---

원형 큐

---

원형 큐

위의 선형 큐를 원형 큐로 바꿔 보았다.

원형 큐는 선형 큐의 문제점을 해결한 모양이다.

해당 모양으로 위의 3, 9, 1을 enqueue dequeue를 했을 땐 rear 큐가 다시 0번째 index로 돌아오게 된다.

원형 큐는 나머지(%)연산자를 이용하여 구현한다.

 

때문에 큐는 선형 자료구조이지만 실제 구현은 원형으로 한다.