- 큐 역시 연결리스트의 변형으로서, 연결리스트의 한 쪽에서는 삽입연산이 다른 한쪽에서는 삭제연산이 이루어지도록 연산의 제한을 가한 구조로서, 일반적으로 순서를 기다리며 줄을 서는 경우를 예를 들 수 있다.
- 선입선출(FIFO: First In Fiest Out) 구조
- 큐의 응용분야: 컴퓨터의 운영체제에서 여러 작업들의 스케줄링
- 스택과 마찬가지로 큐 역시 컴퓨터 알고리즘에서 많이 사용되는 중요한 기본 자료형
- 큐 또한 자료추상화data abstraction 또는 추상자료형abstraction data type의 한 형태로 볼 수 있다.
- 삽입이 일어나는 쪽을 큐의 리어rear라 하고 삭제가 일어나는 쪽을 프론트front라 한다.
- 삽입연산을 인큐enqueue라 하고 삭제연산을 디큐dequeue라고 부른다.
배열로 구현된 큐
아래의 그림에서 배열을 사용한 큐의 예를 보여준다. 그림에서 F와 R은 각각 큐의 front와 rear를 나타낸다. 큐의 초기화 과정에서 front와 rear는 -1로 설정.
- 1단계에서는 초기화 상태.
- 2단계에서 데이터 값 A가 삽입되는 과정(rear의 값이 1증가한 다음 큐의 용량이 초과되었는지 미리 검사를 해보아야 한다.)
- 3단계에서는 연속해서 4개의 데이터 값이 삽입enqueue된 후의 상태를 보여준다.
- 4단계와 5단계에서 데이터를 큐에서 삭제dequeue연산하는 과정을 보인다. 큐에서는 rear와 front값이 동일한 상태를 큐가 비어있는 상태로 본다.
- 6단계에서는 세 개의 데이터를 큐에서 삭제한 다음의 상태, 이 경우 front와 rear의 값이 모두 4를 갖는다. 따라서 front와 rear가 동일한 값을 가지므로 큐가 비어있는 상태를 나타낸다.
- 큐의 공간 0에서 4까지의 5개는 사용가능하도록 비어있으나 새로운 데이터를 삽입할 수 없는 상태가 된다.
- 이러한 상태를 완화시켜주기 위해 front와 rear값이 동일하게 되면 이 값들을 초기값으로 환원
- 이러한 문제의 해결방법:
- 큐의 데이터값을 왼쪽으로 수평이동시켜 공간을 재배치하는 이동 큐를 구현(역시 비효율을 유발시켜 실용적인 방법이라 할 수 없다.)
- 이에 대한 문제해결은 환형 큐의 사용
- 포인터를 사용한 구현
#include <stdio.h>
#define ON 1
#define OFF 0
#define QUEUE_SIZE 20
void main() {
int data, temp, sw, q[QUEUE_SIZE];
int front= -1, rear= -1;
int dequeue();
char opcode, inp_string[5];
void enqueue();
sw=ON;
while(sw) {
printf("\n Insert Opcode(E:Enqueue, D:Dequeue, P:Print, Q:Quit): ");
scanf("%s", inp_string);
opcode=inp_string[0]; //opcode를 얻는다.
printf("** opcode = %c \n", opcode);
switch(opcode) {
case 'E':
printf("\n Enter a number to insert: ");
scanf("%d", &data);
printf("Inserted Data=%d \n", data);
enqueue(q, data, &rear);
break;
case 'D':
data = dequeue(q, &front, &rear);
printf("dequeue data is %3d \n", data);
break;
case 'P': //front값을 저장, front값을 직접 사용하면 문제발생
temp=front+1;
while(temp <= rear)
printf("%3d \n", q[temp++]);
break;
case 'Q':
sw=OFF;
break;
default:
printf("\n *** Warning: 부적절한 op_code입니다. \n");
break;
}
}
}
void enqueue(int q[], int data, int *rear) {
if(*rear == QUEUE_SIZE-1)
{
printf("Queue is full\n");
return;
}
(*rear)++;
q[*rear]= data;
}
int dequeue(int q[], int *front, int *rear) {
int data;
if(*front == *rear)
{
printf("queue is empty\n");
return;
}
(*front)++;
data= q[*front];
if(*front == *rear) {
*front = -1; //앞으로 이동하여 초기화
*rear= -1;
}
return(data);
}
- 이동 큐: rear가 배열의 끝에 도달하면 모든 큐에 있는 원소들을 배열의 앞쪽으로 이동
void enqueue(int q[], int data, int *rear, int *front) {
int i, j;
if(*rear == QUEUE_SIZE-1)
if(*front == -1)
printf("queue is full\n");
else { //수평이동
for(i=(*front)+1, j=0; i<QUEUE_SIZE; i++, j++)
q[j]=q[i];
*rear = *rear-((*front)+1);
*front=-1;
}
(*rear)++;
q[*rear]= data;
}
couple님거에다가 return; 만 추가
출처 : http://couple.haruschool.com/tc/64
