[자료구조] 큐(Queue)

큐 (Queue)

 - 스택과 마찬가지로 삽입과 삭제의 위치가 제한된 유한 순서 리스트

 - 선입선출 구조(FIFO, First-In-First-Out) : 삽입 순으로 나열되어 가장 먼저 삽입한 원소가 가장 먼저 삭제된다.

삭제 ←

front

rear

삽입 ←

---

큐의 연산 과정

 - 삽입 : enQueue

① 공백 큐 생성 : 큐가 생성되지 않은 최초 상태에서만 실행

Q	[0]	[1]	[2]
↑ front == rear == -1 ↑

② 원소 A삽입 : enQueue(Q, A);

Q	[0]	[1]	[2]
	A
↑ front == -1 ↑	↑ rear == 0 ↑

③ 원소 B삽입 : enQueue(Q, B);

Q	[0]	[1]	[2]
	A	B
↑ front == -1 ↑		↑ rear == 1 ↑

 

 - 삭제 : deQueue

초기 상태

Q	[0]	[1]	[2]
	A	B
↑ front == -1 ↑		↑ rear == 1 ↑

① 원소 삭제 : deQueue(Q);

Q	[0]	[1]	[2]
	A	B
	↑ front == 0 ↑	↑ rear == 1 ↑

 

 - 스택(stack)과 큐(queue)의 연산 비교

항목 자료구조	삽입		삭제
	연산자	삽입 위치	연산자	삭제 위치
스택 (stack)	push	top	pop	top
큐 (queue)	enQueue	rear	deQueue	front

---

선형 큐

 - 1차원 배열을 이용한 큐

    ㄴ 큐의 크기 = 배열의 크기

    ㄴ 변수 front : 저장된 첫 번째 원소의 인덱스

    ㄴ 변수 rear : 저장된 마지막 원소의 인덱스

 - 상태 표현

    ㄴ 초기 : front == rear == -1

    ㄴ 공백 : front == rear

    ㄴ 포화 : rear == n-1 (n : 배열의 크기, n-1 : 배열의 마지막 인덱스)

 - 선형 큐의 문제점 : 선형 큐의 잘못된 포화상태 인식

선형 큐에서 삽입과 삭제의 반복 시 front가 뒤로 계속 밀리면서 자리가 있음에도 불구, 포화상태로 인식하고 더 이상 삽입을 수행하지 않는다. (다음과 같은 상태)

[0]	[1]	[2]	[3]
		front	rear

 - 해결 방법 1 : 저장된 원소들을 삭제 연산 이후 앞으로 당긴다. (but, 순차 자료에서 이동 작업은 연산이 복잡하여 효율성이 낮음)

 - 해결 방법 2 : 1차원 배열을 사용하면서 논리적으로 배열의 처음과 끝이 연결되어있다 가정 => 원형 큐

원형 큐의 논리적 구조 (출처: IT COOKBOOK)

---

원형 큐

 - 1차원 배열을 사용하면서 논리적으로 배열의 처음과 끝이 연결되어있다 가정한다

 - 초기 공백 상태 : front == rear == 0

 - front와 rear의 위치가 배열의 마지막 인덱스(n-1)에서 논리적인 다음 자리인 인덱스 0번으로 이동하기 위해 나머지 연산자(mod) 사용

 - 공백 상태와 포화 상태 구분을 쉽게 하기 위해 front자리는 사용하지 않고 항상 빈자리로 유지한다

 

원형 큐의 연산

 - 삽입 : enQueue

EX )
(① 공백 큐 생성) : 큐가 생성되지 않은 최초 상태에서만 실행
② 원소 A삽입
③ 원소 B삽입

(① 공백 큐 생성)

[1]	[2]
[0]	[3]
↑ front == rear == 0 ↑

② 원소 A삽입 : enQueue(cQ, A);

↓ rear == 1 ↓
[1]               A	[2]
[0]	[3]
↑ front == 0 ↑

③ 원소 B삽입 : enQueue(cQ, B);

	↓ rear == 1 ↓
[1]              A	B               [2]
[0]	[3]
↑ front == 0 ↑

 - 삭제 : deQueue

EX )
① 원소 삭제

① 원소 삭제 : deQueue(cQ);

↓ front == 0 ↓	↓ rear == 1 ↓
[1]              A	B               [2]
[0]	[3]

---

연결 큐

 - 단순 연결 리스트를 이용한 큐

    ㄴ 큐의 원소 : 단순 연결 리스트의 노드

    ㄴ 큐의 원소의 순서 : 노드의 링크 포인터로 연결

    ㄴ 변수 front : 첫 번째 노드를 가리키는 포인터 변수

    ㄴ 변수 rear : 마지막 노드를 가리키는 포인터 변수

 - 상태 표현

    ㄴ 초기 상태와 공백 상태 : front == rear == null

 - 연결 큐의 구조

100번지			200번지			300번지
A	● 200	→	B	● 300	→	C	null
↑						↑
● 100						● 400
front						rear

 

연결 큐의 연산

 - 삽입

① 연결 큐를 생성한다. (최초 1회)
② (연결 큐가 생성되어 있을 시) 연결 큐가 공백인지 확인한다.
    -1 공백인 경우, 삽입할 새 노드에 front 포인터와 rear포인터를 가리킨다.
    -2 공백이 아닌 경우, 현재 큐의 마지막 노드 뒤에 새 노드를 삽입하고 rear 포인터가 가리키도록 한다.

① 연결 큐를 생성한다. (최초 1회)

new		100번지			front	rear
● 100	→	item	null		null	null

② (연결 큐가 생성되어 있을 시) 연결 큐가 공백인지 확인한다.

    -1 공백인 경우, 삽입할 새 노드에 front 포인터와 rear포인터를 가리킨다.

100번지
A		null
↑	↑
● 100	● 100
front	rear

    -2 공백이 아닌 경우, 현재 큐의 마지막 노드 뒤에 새 노드를 삽입하고 rear 포인터가 가리키도록 한다.

100번지			200번지
A	● 200	→	B	null
↑			↑
● 100			● 200
front			rear

 - 삭제

① front 포인터가 front 노드가 가리키던 노드를 가리키게 한다.
② 이번 연산이 끝나고 큐가 공백이 되는 경우, front 포인터와 rear 포인터를 null로 재설정한다.

① front 포인터가 front 노드가 가리키던 노드를 가리키게 한다.

100번지			200번지
A	● 200	→	B		null
			↑	↑
			● 200	● 200
			front	rear

② 이번 연산이 끝나고 큐가 공백이 되는 경우, front 포인터와 rear 포인터를 null로 재설정한다.

front		rear
null		null

---

운영체제의 작업 큐

 - 프린터 버퍼 큐

    ㄴ CPU에서 프린터로 보낸 데이터 순서대로(선입선출, FIFO) 프린터에서 출력하기 위해 큐 사용

 - 스케줄링 큐

    ㄴ CPU 사용을 요청한 프로세서들의 순서를 스케줄링하기 위해 큐 사용