스택은 나중에 넣은 데이터가 먼저 나오는 FIFO(First In First Out)형식의 자료구조였다면,
큐는 먼저 넣은 데이터가 먼저 나오는 LIFO(Last In First Out)형식의 자료구조이다.
큐를 구현할 때 연결리스트를 사용할 수도 있고 배열을 사용할 수도 있다.
배열을 사용할 경우 선형배열을 사용하면 비효율적이다. 선형배열로 사용하게 되면 한번 사용한 메모리들을 다시 접근할 수 없어 메모리 낭비가 되기 때문이다.
따라서 큐가 배열의 끝에 도달한 경우 인덱스의 처음으로 돌아와 빈 공간을 사용할 수 있게
원형
으로 구현하는 것이 효율적이다.
여기서 원형배열은 메모리 구조는 직선이지만 코드를 원형으로 구현하면
이렇게 원형 형태로 사용할 수 있다는 것이다.
그림과 같이 데이터가 저장된 형태를 보면 데이터가 저장된 첫 번째 위치를 f(front)가, 데이터의 마지막 위치를 r(rear)이 가리키고 있는 것을 볼 수 있다.
선형배열 자료구조에서는 rear과 front의 값을 1 증가시키기만 하였다면 원형 배열에서는 rear과 front의 값을 1 증가시킨 뒤 항상 size로 나눠줘야한다. 예를들어 rear값이 7인 상태에서 데이터를 삽입할 경우 (rear + 1) % size를 해야 원형배열에서 7의 다음 인덱스인 0을 접근할 수가 있다.
큐 구조체
typedef struct queue {
int arr[1000];
int front;
int rear;
int size;
}queue;
큐의 구조체 안에는 데이터를 저장할 arr배열, 첫 번째 데이터를 가리키는 front, 마지막 데이터를 가리키는 rear, queue의 max size를 저장할 size가 있다.
큐 초기화
void queue_init(queue* q, int size) {
q->front = 0;
q->rear = size - 1;
q->size = size;
}
front = 0, r = size - 1로 초기화를 해준다.
이 때 빈 상태는 r = f이고 큐가 가득 찬 상태는 (r + 1) % N = f이다.
큐 삽입
void enqueue(queue* q, int data) {
if ((q->rear + 1) % q->size == q->front) {
printf("overflow");
return;
}
q->rear = (q->rear + 1) % q->size;
q->arr[q->rear] = data;
}
위에서 설명했듯이 (r + 1) % N = f인 포화상태라면 overflow를 발생시키고 그렇지 않다면 rear을 1증가시킨 곳에 데이터 값을 삽입하여 준다.
큐 삭제
int dequeue(queue* q) {
if (q->front == q->rear) {
printf("underflow");
return 0;
}
q->front = (q->front + 1) % q->size;
int temp = q->arr[q->front];
q->arr[q->front] = 0;
return temp;
}
삭제는 r = f (빈 상태)라면 underflow를 발생시키고 그렇지 않다면 front를 1 증가시킨다.
그리고 삭제한 원소를 반환한다.
#include<stdio.h>
#include<stdlib.h>
#pragma warning(disable:4996)
typedef struct queue {
int* arr;
int front;
int rear;
int size;
}queue;
void queue_init(queue* q, int size) {
q->arr = (int*)malloc(sizeof(int) * size);
q->size = size;
for (int i = 0; i < q->size; i++)
q->arr[i] = 0;
q->front = q->rear = 0;
}
void print(queue* q) {
for (int i = 0; i < q->size; i++)
printf(" %d", q->arr[i]);
puts("");
}
int enqueue(queue* q, int data) {
if ((q->rear + 1) % q->size == q->front) {
printf("overflow");
print(q);
return 0;
}
q->rear = (q->rear + 1) % q->size;
q->arr[q->rear] = data;
return 1;
}
int dequeue(queue* q) {
if (q->front == q->rear) {
printf("underflow");
return 0;
}
q->front = (q->front + 1) % q->size;
q->arr[q->front] = 0;
return 1;
}
int main() {
int size, n;
queue q;
scanf("%d", &size);
queue_init(&q, size);
scanf("%d", &n);
getchar();
while (n--) {
char command;
scanf("%c", &command);
getchar();
if (command == 'I') {
int data;
scanf("%d", &data);
getchar();
if (enqueue(&q, data) == 0)
return 0;
}
else if (command == 'D') {
if (dequeue(&q) == 0)
return 0;
}
else {
print(&q);
}
}
free(q.arr);
return 0;
}