[자료구조] 큐 Queue

 

 

---

 

1. 큐

• 큐(Queue)는 선입선출(FIFO, First-In-First-Out) 원칙에 따라 동작하는 선형 자료구조이다.
• 데이터가 삽입된 순서대로 처리되며, 가장 먼저 추가된 요소가 가장 먼저 제거되는 특징을 지닌다.
• 데이터를 삽입하는 리어(rear)와 데이터를 제거하는 프론트(front)로 구성되며, 이 두 지점을 통해 연산이 이루어진다.

 

2. 특징

장점

• 처리 순서의 예측 가능성: 선입선출 원칙에 따라 먼저 들어온 데이터가 항상 먼저 처리된다.
• 구현 용이성: 배열 또는 연결 리스트를 이용한 구현이 비교적 단순하며, 연결 리스트 기반 큐의 경우 동적 크기 조절이 가능하다.

단점

• 제한된 접근성: 특정 위치의 데이터에 직접 접근하려면 모든 선행 요소를 순차적으로 제거해야 하므로 시간 복잡도가 O(n)으로 증가한다
• 메모리  공간 낭비: 데이터 삽입/삭제 과정에서 메모리 공간이 낭비될 수 있으며, 이를 해결하기 위해 원형 큐(Circular Queue)가 고안되었다

 

3. 큐의 종류

선형 큐(Linear Queue)

가장 기본적인 형태로, 배열의 앞부분이 비어 있더라도 리어가 배열 끝에 도달하면 더 이상 삽입이 불가능하다.

원형 큐(Circular Queue)

배열의 끝과 시작을 논리적으로 원형으로 연결하여 공간 활용도를 극대화한다.

데크(Deque)

양방향에서 삽입/삭제가 가능한 확장된 큐 형태이다.