큐 (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] |
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차원 배열을 사용하면서 논리적으로 배열의 처음과 끝이 연결되어있다 가정 => 원형 큐
원형 큐
- 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] |
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 사용을 요청한 프로세서들의 순서를 스케줄링하기 위해 큐 사용
'자료구조' 카테고리의 다른 글
[자료구조] 이진 탐색 트리 Binary Search Tree (0) | 2022.01.16 |
---|---|
[자료구조] 수식의 표기법 (Notation) (0) | 2022.01.09 |
[자료구조] 스택 (Stack) (0) | 2022.01.08 |
[자료구조] 이중 연결 리스트 (0) | 2022.01.02 |
[자료구조] 순차 자료구조 (0) | 2022.01.01 |