큐

큐(Queue)란?

스택은 나중에 넣은 데이터가 먼저 나오는 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을 접근할 수가 있다.

원형 큐의 method

큐 구조체

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;
}