[자료구조]3. 큐

큐 이미지. 큐의 형태는 도로에서 일렬로 나란히 선 자동차와 같다.

Queue ADT, 큐 추상자료형

• 큐는 FIFO(First In, First Out), 선입선출 구조이다. 먼저 들어온 원소가 먼저 나간다.
• 원소의 삽입은 큐의 뒤에서 이루어지고, 원소의 삭제는 큐의 앞에서 이루어진다.
• 큐의 주요 기능은 다음과 같다.

1. enqueue(obj) : 큐의 뒤(rear)에 원소를 삽입한다.
2. dequeue(obj) : 큐의 앞(front)에 있는 원소를 꺼낸다.

• 큐의 추가적인 기능은 다음과 같다.

1. front/top : 꺼내지 않고 큐의 맨 앞의 원소를 확인한다.
2. size : 큐에 저장된 원소의 수를 return한다.
3. empty : 큐가 비어있는지 확인한다.

• 예외처리는 QueueEmpty로 큐가 빈 상태인지 확인한다.
• 큐의 구현으로는 배열 혹은 링크드 리스트를 사용할 수 있다.

 

큐 구현 - 배열기반

• 배열 기반 큐는 사이즈가 N인 원형 형태로 사용한다. 
• 이 때 세 개의 변수가 맨 앞(front)와 뒤(rear)를 고려한다.

1. f : 맨 앞에 있는 원소의 인덱스
2. r : 맨 뒤에 있는 원소의 그 다음번 째 인덱스 (구현 방법에 따라 맨 뒤에 있는 원소가 될 수도 있다.)
3. n : 큐에서의 원소의 개수

배열 기반 큐

이 때 이 형태를 유지하기 위해 인덱스를 나타내는 변수 i와 배열의 크기 N이 있을 때,

i Mod N 의 식을 이용해서 배열에 접근한다.

 

Enqueue

1. Q[r]에 삽입
2. r = (r + 1) Mod N
3. n = n + 1

※ enqueue는 O(1) 시간이 소모된다.

 

Dnqueue

1. Q[f]에서 원소를 꺼낸다.
2. f = (f + 1) Mod N
3. n = n - 1

※ dnqueue는 O(1) 시간이 소모된다.

큐의 이미지. 출처 - https://www.tutorialride.com/data-structures/queue-in-data-structure.htm

큐 구현 - 단일 링크드 리스트 기반

• 단일 링크드 리스트에서는 맨 앞에 노드를 head노드라고 했고, 맨 뒤 노드를 tail이라고 했다.
• 따라서 큐를 단일 링크드 리스트로 구현하려면 다음과 같이 해야한다.

1. front : 큐에서 삭제가 일어나는 곳. 따라서 삽입, 삭제가 모두 빠른 head 노드로 정한다.
2. rear : 큐에서 삽입이 일어나는 곳. 따라서 삽입만 빠른 tail 노드로 정한다.

단일 링크드 리스트 기반 큐

성능

• 삽입, 삭제가 O(1) 시간이 소요된다.
• 공간은 O(n)만큼 차지한다.