2.1 큐(queue)란?
스택의 경우, 나중에 들어온 데이터가 먼저 나가는 구조인데 반하여 큐(queue)는 먼저 들어온 데이터가 먼저 나가는 구조로 이러한 특성을 선입선출(FIFO : First In First Out)이라고 한다. 큐의 예로는 매표소에서 표를 사기 위하여 늘어선 줄을 들 수 있겠다. 줄에 있는 사람들 중 가장 앞에 있는 사람(즉, 가장 먼저 온 사람)이 가장 먼저 표를 사게 될 것이다. 나중에 온 사람들은 줄의 맨 뒤에 서야 할 것이다.
큐는 뒤에서 새로운 데이터가 추가되고 앞에서 데이터가 하나씩 삭제되는 구조를 가지고 있다. 구조상으로 큐가 스택과 다른 점은 스택의 경우, 삽입과 삭제가 같은 쪽에서 일어나지만 큐에서는 삽입과 삭제가 다른 쪽에서 일어난다는 것이다.
위의 그림과 같이, 큐에서 삽입이 일어나는 곳을 후단(Rear)라고 하고 삭제가 일어나는 곳을 전단(front)라고 한다.
2.2 큐의 추상 자료형
추상 자료형 큐의 연산들은 추상 자료형 스택과 아주 유사하다.
| 연산 | 기능 |
| init() | 큐를 초기화 |
| is_empty() | 큐가 비어있는지 검사 |
| is_full() | 큐가 가득 찼는지 검사 |
| enqueue() | 큐의 맨 뒤에 새로운 요소를 추가 |
| dequeue() | 큐의 맨 앞에 있는 요소를 꺼내 외부로 반환 |
| peek(s) | 스택의 맨 위 요소를 삭제하지 않고 반환 |
is_empty() 연산은 큐가 비어있으면 TRUE를 반환하고 그렇지 않으면 FALSE를 반환한다. is_full() 연산은 큐가 가득 찼으면 TRUE를, 그렇지 않으면 FALSE를 반환한다.
가장 중요한 연산은 삽입과 삭제 연산인 enqueue 와 dequeue이다. enqueue 연산은 큐에 요소를 추가하는 연산으로서 큐의 맨 뒤에 새로운 요소를 추가한다. dequeue 연산은 큐의 맨 앞에 있는 요소를 꺼내서 외부로 반환한다.
그림2는 enqueue, dequeue 연산을 설명한 것이다. 데이터들이 삽입된 순서대로 나가는 것을 확인할 수 있다.
스택과는 달리 삽입, 삭제가 큐의 양끝에서 일어나기 때문에 양단을 잘 살펴보아야 함을 주의해야한다.
스택에서는 삽입, 삭제와 관련하여 top이라 불리는 변수가 1개만 존재하는데 비해 큐에서는 두 개의 변수가 사용된다. 삽입과 관련된 변수를 rear라고 하고 삭제와 관련된 변수를 front라고한다.
2.3 선형큐
큐도 스택과 마찬가지로 구현하는 방법이 여러 가지이나 여기서는 가장 간단한 방법, 즉 1차원 배열을 쓰는 방법을 먼저 살펴보자. 정수를 저장할 수 있는 큐를 만들어 보자. 먼저 정수의 1차원 배열을 정의하고 삽입, 삭제를 위한 변수인 front와 rear를 만든다. front는 큐의 첫 번째 요소를 가리키고 rear는 큐의 마지막 요소를 가리킨다.
front와 rear의 초기값은 -1 이다. 데이터가 증가되면 rear를 하나 증가하고 그 위치에 데이터가 저장된다. 삭제할 때도 front가 가리키는 위치에 있는 데이터를 삭제한다. 위와 같은 큐를 선형큐(Linear queue)라고 한다.
2.3.1 선형큐 구현
아래는 선형큐를 간단히 구현한 예시이다.
//선형 큐 구현 프로그램
#include<stdio.h>
#include<stdlib.h>
#define MAX_QUEUE_SIZE 5
typedef int element;
typedef struct QueueType {
int front;
int rear;
element data[MAX_QUEUE_SIZE];
}QueueType;
//큐 초기화 함수
void init_queue(QueueType* q) {
q->rear = -1;
q->front = -1;
}
//큐 포화상태 검출
int is_full(QueueType* q) {
if (q->rear == MAX_QUEUE_SIZE - 1) //이렇게 되면 큐의 포화상태
return 1;
else
return 0;
}
//큐 공백상태 검출
int is_empty(QueueType* q) {
if (q->front == q->rear) //front와rear가 같으면 큐가 공백상태
return 1;
else
return 0;
}
//큐 삽입함수
void enqueue(QueueType* q, int item) {
if (is_full(q)) {
fprintf(stderr, "Queue is full:(\n");
exit(1);
}
q->data[++(q->rear)] = item;
}
//큐 삭제함수
int dequeue(QueueType* q) {
if (is_empty(q)) {
fprintf(stderr, "Queue is empty:(\n");
exit(1);
}
int item = q->data[++(q->front)];
return item;
}
int main(void) {
int item = 0;
QueueType q;
init_queue(&q);
enqueue(&q, 10);
enqueue(&q, 20);
enqueue(&q, 30);
enqueue(&q, 40);
printf("%d\n", dequeue(&q));
printf("%d\n", dequeue(&q));
printf("%d\n", dequeue(&q));
return 0;
}
선형큐의 경우 이해하기 쉽고 구현도 간단하다는 장점이 있지만, 문제점이 있다. 큐에 데이터가 가득 차면 더 이상 데이터를 삽입할 수 없는 문제가 생긴다. 이로인해 큐 오버플로우가 발생하고 또한 큐에서 데이터를 dequeue 한 후에도 배열의 앞쪽에서부터 데이터를 채우기 때문에, 배열의 첫부분이 비었음에도 불구하고 더 이상 데이터를 삽입할 수 없는 문제가 생긴다. 물론 모든 요소들을 왼쪽으로 이동시켜서 해결하는 방법이 있지만 매번 이동시키려면 상당한 시간이 걸리고 또한 프로그램 코딩 또한 복잡해진다.
2.4 원형큐
앞서 언급했던 문제는 배열을 선형으로 생각하지 말고 원형으로 생각하면 쉽게 해결된다. 즉 front와rear의 값이 배열의 끝인 (MAX_QUEUE_SIZE-1)에 도달하면 다음에 증가되는 값은 0이 되도록 하는 것이다. 즉 다음과 같이 배열이 원형으로 처음과 끝이 연결되어 있다고 생각하는 것이다.
(※물론 실제로 배열이 원형으로 변화되는 것은 아니고, 그냥 개념상으로 원형으로 배열의 인덱스를 변화시켜주는 것이다.)
원형큐에서는 front와 rear의 개념이 약간 변경된다. 먼저 초기값은 -1이 아닌 0이다. 또 front는 항상 큐의 첫 번째 요소의 하나 앞을, rear는 마지막 요소를 가리킨다. 아래의 [그림 5]는 원형큐에서 데이터가 삽입, 삭제될 때에 front와 rear가 어떻게 변화되는지를 보인다.
처음에 front, rear는 모두 0이고 삽입 시에는 rear가 먼저 증가되고, 증가된 위치에 새로운 데이터가 삽입된다. 또 삭제 시에도 front가 먼저 증가된 다음, 증가된 위치에서 데이터를 삭제한다. 이런식으로 생각하면 된다.
front와 rear의 값이 같으면 원형 큐가 비어 있음을 나타낸다. 원형큐에서는 하나의 자리는 항상 비워둔다. 왜냐하면 포화 상태와 공백 상태를 구별하기 위해서이다. 만약 한 자리를 비워두지 않는다면 아래의 [그림 6] 처럼 공백상태와 포화 상태를 구분할 수 없을 것이다. 따라서 원형 큐에서 만약 front == rear 이면 공백 상태가 되고 만약 front가 rear 보다 하나 앞에 있으면 포화 상태가 된다.
2.4.1 원형큐의 삽입, 삭제 알고리즘
원형큐의 삽입, 삭제 알고리즘은 먼저 삽입이나 삭제를 하기 전에 front 와 rear를 원형 회전시켜서 하나 증가시키고 증가된 위치에 데이터를 삽입 또는 삭제한다. 원형큐의 구현에 있어서 중요한 것은 front와 rear를 원형으로 회전시켜야 한다는 것이다. 이는 나머지 연산자 %를 이용하여 쉽게 구현할 수 있다.
front <- (frnot + 1) % MAX_QUEUE_SIZE;
rear <- (raer + 1) % MAX_QUEUE_SIZE;
위의 식에 의하여 front와 rear의 값은 (MAX_QUEUE_SIZE - 1)에서 하나 증가되면 0으로 된다. 즉, 만약 MAX_QUEUE_SIZE 를 5로 정의하면, front 와 rear값은 1,2,3,4,0 과 같이 변화된다.
1.원형큐에서의 삽입 알고리즘
enqueue(Q, x) :
rear <- (rear + 1) % MAX_QUEUE_SIZE;
Q[rear] < -x;
2.원형큐에서의 삭제 알고리즘
dequeue(Q) :
front <- (front + 1) % MAX_QUEUE_SIZE
return Q[front];
2.4.2 원형큐의 구현
#include<stdio.h>
#include<stdlib.h>
//=====원형큐 코드 시작=====
#define MAX_QUEUE_SIZE 5
typedef int element;
typedef struct QueueType {
element data[MAX_QUEUE_SIZE];
int front, rear;
}QueueType;
//큐 초기화 함수
void init_queue(QueueType* q) {
q->front = q->rear = 0;
}
//공백 상태 검출 함수
int is_empty(QueueType* q) {
return (q->front == q->rear);
}
//포화 상태 검출 함수
int is_full(QueueType* q) {
return ((q->rear + 1) & MAX_QUEUE_SIZE == q->front);
}
//삽입 함수
void enqueue(QueueType* q, element item) {
if (is_full(q)) {
fprintf(stderr, "Queue is full:(\n");
exit(1);
}
q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
q->data[q->rear] = item;
}
//삭제 함수
element dequeue(QueueType* q) {
if (is_empty(q)) {
fprintf(stderr, "Queue is empty:(\n");
exit(1);
}
q->front = (q->front + 1) % MAX_QUEUE_SIZE;
return q->data[q->front];
}
element peek(QueueType* q) {
if (is_empty(q)) {
fprintf(stderr, "Queue is empty:(\n");
exit(1);
}
return q->data[(q->front + 1) % MAX_QUEUE_SIZE];
}
참고자료 : C언어로 쉽게 풀어쓴 자료구조
'자료구조&알고리즘' 카테고리의 다른 글
| 3. tree(트리) [자료구조 & 알고리즘] (2) | 2024.05.24 |
|---|---|
| 1. 스택(Stack)[자료구조 & 알고리즘] (2) | 2024.03.22 |
