[Data Structure] 자료구조 - 큐(Queue), 원형 큐, 우선순위 큐, 데크

 

🗨 개인적인 공부 기록용으로 정리한 내용입니다. 잘못된 내용에 대한 피드백은 언제나 감사합니다 :)

 

 

 

 

 

⭐ 큐는 가장 먼저 들어온 데이터가 가장 먼저 처리되는 선입선출(FIFO) 구조의 자료구조이다.

 

 

 

 

 

📌 큐의 정의

큐는 선입선출(FIFO: First In, First Out) 구조의 선형 자료구조이다.

즉, 가장 먼저 들어온 요소가 가장 먼저 처리되는 방식이다.

(나중에 들어온 요소가 먼저 처리되는 `스택(Stack)`과는 반대되는 개념이다.)

 

큐는 마트에서 계산을 위해 사람들이 줄을 선 모습과 비슷하며, 순차적으로 처리해야 하는 작업에 사용된다. 

가장 먼저 줄을 선 사람이 가장 먼저 계산을 하게 될 것이다. 

 

 

큐의 구조는 아래 그림과 같다.

큐의 구조

 

뒤에서 새로운 요소가 추가되고 앞에서 요소가 하나씩 삭제되는 구조를 가지고 있다. 즉, 삽입과 삭제가 스택(Stack)과는 다르게 큐에서는 서로 다른 쪽에서 일어난다. (스택은 삽입과 삭제가 모두 맨 위(top)에서 일어나는 특징을 가졌다.)

큐에서 요소를 삽입할 수 있는 위치를 `rear (혹은 tail)`, 요소를 꺼낼 수 있는 위치를 `front`라고 한다.

 

큐가 꽉 차서 요소를 더 이상 넣을 수 없는 경우를 `오버플로우(Overflow)`라고 하며, 반대로 큐가 비어있어 더 이상 꺼낼 요소가 없는 경우를 `언더플로우(Underflow)`라고 한다.

 

 

 

기본적인 큐의 구조는 위와 같지만, 구현 방법에 따라 선형 큐, 원형 큐, 우선순위 큐, 데크(덱, Deque) 등 여러 유형의 큐로 활용할 수 있다.

 

 

 

 

큐의 주요 연산은 다음과 같다.

• `Enqueue`: 큐의 맨 뒤에 요소를 추가한다.
• `Dequeue`: 큐의 맨 앞에 있는 요소를 제거한다.
• `isEmpty`: 큐가 비었다면 1을, 그렇지 않다면 0을 반환한다.
• `Peek`: 큐의 맨 앞에 있는 요소를 반환한다.
  • (C++은 `front()`, C#은 `peek()`)

 

 

 

 

 

📌 큐의 장점

• 삽입과 제거 연산 속도가 빠르다.
  
  • ⏱ 시간 복잡도: $\mathbf{O(1)}$
• 선입선출(FIFO) 방식에 최적화 되어있다.
  • 데이터를 순서대로 처리할 수 있어 순서가 중요한 작업에 효율적으로 사용할 수 있다.
  • 예로, 프린터 작업에서 여러 출력 요청을 차례대로 처리하기 위해 큐가 사용된다.

 

 

 

 

 

📌 큐의 단점

• 중간 데이터에 접근하는 것이 어렵다.
  • 스택과 마찬가지로 특정 위치의 데이터에 직접 접근하는 구조가 아니다.
• 크기가 고정된 큐인 경우, 데이터가 쌓여 큐가 가득 차면 더 이상 데이터를 추가할 수 없다.
  • (이때, 나타나는 에러는 `오버플로우(Overflow)`라고 한다.)
• 배열 기반으로 구현한 `선형 큐`인 경우, 공간이 낭비될 수 있다.
  • 이유는, 데이터가 계속해서 삽입되고 삭제되면, 배열의 앞부분이 비어 있어도 rear가 배열의 끝에 도달하면 더 이상 데이터를 추가할 수 없게 되기 때문이다.
  • 이 문제를 해결하기 위해 `원형 큐(Circular Queue)` 구조가 자주 사용된다.

 

 

 

 

 

📌 큐의 종류 및 사용

큐는 기본적으로 선입선출(FIFO)을 따르지만, 상황에 맞게 확장된 여러 유형이 있다.

 

 

🔖 1) 선형 큐 (Linear Queue)

선입선출(FIFO) 구조를 가진 큐의 가장 기본적인 형태이다.

`배열`이나 `연결 리스트`로 구현할 수 있으며, 데이터를 삽입하는 `rear`와 삭제하는 `front` 포인터가 있다.

• 데이터가 계속 추가되고 삭제되면, 큐의 앞쪽이 비어도 `rear`가 배열의 끝에 도달함과 동시에 데이터를 더 이상 추가할 수 없게 되며, 공간 낭비 문제가 발생한다.

선형 큐의 구조

 

 

🔎 연결 리스트로 구현한 큐: `링크드 큐(Linked Queue)`

 

연결 리스트로 구현한 큐는 링크드 큐(Linked Queue) 라고 한다.

`배열 기반`의 선형 큐는 고정된 크기 때문에 큐가 꽉 차면 더 이상 데이터를 추가할 수 없지만, `링크드 큐`는 동적 메모리 할당을 사용하여 크기 제한 없이 데이터를 추가할 수 있다.

하지만, 각 노드가 포인터를 추가로 저장하므로 약간의 메모리 오버헤드가 있다.

 

 

 

선형 큐 | 사용 예시

• 프린터 작업 대기열
  • 인쇄 작업이 순서대로 수행되도록 대기열을 관리할 때 큐가 활용된다.
• 프로세스 스케쥴링
  • 운영체제에서 프로세스가 CPU에 순차적으로 할당될 때 큐가 활용된다.

 

 

 

🔖 2) 원형 큐 (Circular Queue)

원형 큐는 선형 큐의 문제점인 공간 낭비를 줄이기 위해 만들어졌다.

큐의 끝에 도달하면 다시 처음으로 돌아가서 빈 공간을 재활용하도록 설계되어 있다.

• 배열이 원형으로 연결된 것처럼 작동하며, `front`와 `rear`는 배열을 순환하며 이동한다.
  • 즉, `front`와 `rear`가 배열의 끝에 도달하면, 다시 배열의 처음으로 돌아간다.
• 큐가 꽉 찬 상태인지 비어 있는 상태인지를 판단하기 위해 `front`와 `rear`의 위치를 추가적으로 검사해야 한다.

 

 

원형 큐의 구조

 

 

 

원형 큐 | 사용 예시

• 네트워크 라우터 패킷 관리
  • 패킷이 대기열에 순서대로 들어오고 전송될 때, 메모리 재사용이 필요하여 원형 큐가 사용된다.
• 라운드 로빈(Round Robin) 스케줄링
  • 각 프로세스가 순환하며 자원을 배정받아야 하는 상황에서, 원형 큐가 활용된다.

 

 

 

🔖 3) 우선순위 큐 (Priority Queue)

우선순위 큐는 우선순위가 높은 요소가 먼저 처리되는 큐이다.

기본적인 큐와 달리 FIFO 순서가 아닌, 각 요소의 우선순위에 따라 순서가 결정된다.

• 일반적으로 `힙(heap)` 자료구조를 사용하여 구현된다.
  • 가장 큰 값 우선은 `최대 힙`, 가장 작은 값 우선은 `최소 힙`이라 한다.

 

📚 언어별 구현

`C#`은 `PriorityQueue` 클래스를,

`C++`은 `priority_queue` 라이브러리를 이용하면 쉽게 구현이 가능하다.

 

 

 

우선순위 큐 | 사용 예시

• 운영체제의 작업 스케줄링
  • 긴급하게 처리해야 할 프로세스는 높은 우선순위를 부여하여 먼저 처리한다.
• 네트워크 트래픽 관리
  • 특정 패킷이 더 높은 우선순위를 가지고 빠르게 전송되어야 할 때 우선순위 큐가 활용된다.

 

 

 

🔖 4) 데크 (Deque, Double-Ended Queue)

데크(덱)는 양쪽 끝에서 삽입과 삭제가 모두 가능한 큐이다. 

FIFO뿐 아니라 LIFO 구조로도 활용이 가능해 유연한 자료 관리가 가능하다.

• 앞쪽(front)과 뒤쪽(back)에서 데이터를 삽입하고 제거할 수 있다.
• 스택과 큐의 특성을 모두 가지고 있어, 필요에 따라 양방향에서 데이터를 처리할 수 있다.

 

데크의 구조

 

 

 

데크 | 사용 예시

• 웹 브라우저의 앞으로 가기/뒤로 가기 기능
  • 양방향에서 삽입/삭제가 가능한 데크로 구현할 수 있다.
• 슬라이딩 윈도우 문제
  • 데이터의 구간합, 최솟값/최댓값을 관리할 때 주로 사용된다.

 

 

 

 

 

⭐ 요약

큐 종류	특징	사용 예시
선형 큐	FIFO 방식, 고정된 크기, 공간 낭비 문제 있음	프린터 대기열, 프로세스 스케줄링
원형 큐	공간 재사용 가능, front와 rear가 배열 끝에서 순환함	네트워크 패킷 관리, 라운드 로빈 스케줄링
우선순위 큐	우선순위 높은 요소가 먼저 처리됨, 일반적으로 힙 구조 사용	프로세스 스케줄링, 네트워크 트래픽 관리
데크	양쪽 끝에서 삽입/삭제 가능, FIFO/LIFO 모두 가능	웹 브라우저 탐색, 슬라이딩 윈도우 문제