큐(Queue)

Goal

• 큐를 구현할 수 있다. (배열, 링크드 리스트로 구현)
• 큐 구조를 그리고 설명할 수 있다
• 큐가 사용되는 예시를 들고, 어떨 때 사용되는지 설명할 수 있다

---

큐(Queue)

• 데이터의 입력은 가장 뒤쪽(back, rear)에서, 출력은 가장 앞쪽(front)에서 이루어지는 형태의 제한적 선형자료구조
• 먼저 입력된 순서대로 출력되는 선입선출(FIFO) 형태의 자료구조

 

큐

특징

• 원소의 추가 O(1)
• 원소의 삭제 O(1)
• 제일 앞쪽(front), 제일 뒤쪽(back) 원소 확인 O(1) => 원칙적으로 중간에 있는 데이터 확인 및 변경 불가능

원형 큐(Circular Queue)

큐를 논리적으로 원형 형태로 설계한 자료구조

원형 큐

원형큐는 큐를 배열로 구현했을 때 발생하는 문제점을 보완하기 위해 고안된 자료구조이다.

 

배열을 사용해서 큐를 구현할 경우 다음과 같은 문제가 있다.

1. 큐의 요소 삽입, 삭제 연산이 이루어짐
2. front, rear 인덱스 증가 (증가만 한다! 문제는 여기서 시작)
3. 큐의 앞쪽 부분을 사용할 수 없음 => 큐의 공간을 다 활용하기 위해 추가 작업 필요(overhead발생)

위와 같은 문제(index가 증가만 하는 문제)로 배열을 이용하여 큐를 구현할 경우 선형 큐 대신 원형 큐로 구현한다. 

구현 방법은 다음과 같다.

• front = (front+1) % MaxSize
• rear = (rear+1) % MaxSize

즉, 인덱스 = '(인덱스+1) % 큐의 배열 최대 크기' 로 front, rear 인덱스를 계산

(인덱스 % (MaxSize-1) 로 하지 않는 이유는 MaxSize가 1일 경우 0이 되기 때문)

 

여기서 환형 큐의 front, rear는 메모리 상에서 배열의 시작과 끝이 아닌, 논리적인 시작과 끝점이다

 

위와같이 구현하면 모든 큐 공간을 활용할 수 있게 된다. (문제 해결)

 

큐의 추상 자료형(ADT)

객체 : FILO(선입 후출)의 접근 방법을 유지하는데 필요한 요소들의 모음
연산

• push(x) : x를 맨 뒤에 추가
• pop() : 맨 앞 요소 삭제
• isEmpty() : 큐가 비어있는지 결과 반환
• front() : 큐의 맨 앞 요소 반환
• back() : 큐의 맨 뒤 요소 반환
• size() : 큐의 요소 개수 반환
• isFull() : 큐가 꽉 찼는지 확인 (배열과 같이 제한된 크기를 가질 때 사용)

큐의 구현

BOJ 큐 구현 문제 : https://www.acmicpc.net/problem/18258

- 배열 큐 - https://github.com/jihyuk124/DataStructure/tree/master/03.Queue%2C%20Deque/ArrayQueue

- 연결 리스트 큐 - https://github.com/jihyuk124/DataStructure/tree/master/03.Queue%2C%20Deque/LinkedListQueue

구현 예시

배열, 링크드 리스트로 스택 구현 (기초 : int를 담는 큐 구현, 심화 : 큐의 템플릿화) 
원형 큐 구현

 

큐의 사용 예시

• 버퍼(buffer)
• 매칭시스템
• 스케줄링
• 메시지 처리