[Data Structure] 선형큐 (Linear-Queue)

큐 (Queue)

- FIFO(First in - First out) 선입 선출 구조

- 전단(front) : 삭제가 일어나는 곳

- 후단(rear) : 삽입이 일어나는 곳

 

큐 ADT (추상 자료형)

- 0개 이상의 요소들로 구성된 선형 리스트

void init_queue(queue *q) 

• 큐 초기화

int is_full(queue *q) 

• 포화 상태 검출 함수

int is_empty(queue *q) 

• 공백 상태 검출 함수

void enqueue(queue *q, element item) 

• 큐의 후단(rear)에 item 삽입

element dequeue(queue *q) 

• 큐의 전단(front)에서 item 리턴 후 삭제

element peek(queue *q) 

• 큐의 전단(front)에서 item 선택

 

 

 

선형큐

- 초기화 상태 : front = rear = -1

- enqueue → rear를 하나 증가, 증가시킨 위치에 item 저장

- dequeue → front를 하나 증가, 증가시킨 위치에 있는 item 리턴 후 삭제

- 공백 상태 : front == rear

- 포화 상태 : rear == MAX_QUEUE_SIZE -1

 

1. is_full / is_empty

int is_full(queue* q) {
	// 큐가 가득 차있으면 큐의 후단(rear) == MAX_QUEUE_SIZE -1
	return q->rear == MAX_QUEUE_SIZE - 1;
}

int is_empty(queue* q) {
	// 큐가 비어있으면 큐의 전단(front) = 큐의 후단(rear)
	return q->rear == q->front;
}

- is_full

• 큐가 가득 차있으면 더이상 enqueue(삽입) 불가
• 큐가 가득 차있으면 rear == MAX_QUEUE_SIZE -1

- is_empty

• 큐가 비어있으면 더이상 pop(삭제), peek(선택) 불가
• 큐가 비어있으면 front == rear

 

2. enqueue (int rear)

void enqueue(queue* q, element item) {
	// 큐에 item 추가하려면 rear 이용
	if (is_full(q)) {
		fprintf(stderr, "Error : Queue is full\n");
		return;
	}
	else
		q->queue[++(q->rear)] = item;
}

enqueue를 하려면 삽입관련 변수 rear를 1증가시키고, 증가시킨 위치에 item 삽입

• ++(q->rear)를 통해서 rear를 1증가
• q->queue[++(q->rear)] = item을 통해서 1증가된 rear 위치에 item 삽입

 

 

3. dequeue (int front)

element dequeue(queue* q) {
	// 큐에서 item을 pop시키려면 front 이용
	if (is_empty(q)) {
		fprintf(stderr, "Error : Queue is empty\n");
		return;
	}
	else
		return q->queue[++(q->front)];
}

dequeue를 하려면 삭제관련 변수 front를 1증가시키고, 증가시킨 위치의 item을 리턴 후 큐에서 삭제

• ++(q->front)를 통해서 front를 1증가시켜서 삭제하려는 item에 접근
• q->queue(++(q->front)]를 통해서 1증가시킨 위치에서 item을 리턴 후 큐에서 삭제

 

4. Full Code (Linear Queue With Array)

#include <stdio.h>
#include <stdlib.h>
#define MAX_QUEUE_SIZE 5

typedef int element;

typedef struct {
	int front, rear;
	element queue[MAX_QUEUE_SIZE];
}queue;

void init_queue(queue* q) {
	// 큐 초기화 -> front = rear = -1
	q->front = q->rear = -1;
}

int is_full(queue* q) {
	// 큐가 가득 차있으면 큐의 후단(rear) == MAX_QUEUE_SIZE -1
	return q->rear == MAX_QUEUE_SIZE - 1;
}

int is_empty(queue* q) {
	// 큐가 비어있으면 큐의 전단(front) = 큐의 후단(rear)
	return q->rear == q->front;
}

void enqueue(queue* q, element item) {
	// 큐에 item 추가하려면 rear 이용
	if (is_full(q)) {
		fprintf(stderr, "Error : Queue is full\n");
		return;
	}
	else
		q->queue[++(q->rear)] = item;
}

element dequeue(queue* q) {
	// 큐에서 item을 pop시키려면 front 이용
	if (is_empty(q)) {
		fprintf(stderr, "Error : Queue is empty\n");
		return;
	}
	else
		return q->queue[++(q->front)];
}

element peek(queue* q) {
	// q->front+1 위치의 item을 선택
	if (is_empty(q)) {
		fprintf(stderr, "Error : Queue is empty!!");
		return;
	}
	else
		return q->queue[q->front + 1];
}

void queue_print(queue* q) {
	printf("<- front(삭제) | ");
	for (int i = 0; i < MAX_QUEUE_SIZE; i++) {
		if (i <= q->front || i > q->rear)
			printf("	|	");
		else
			printf("%d	|	", q->queue[i]);
	}
	printf("<- rear(삽입)");
	printf("\n");
}

int main(void) {
	queue q;
	init_queue(&q);

	printf(">>> enqueue 10\n"); enqueue(&q, 10); queue_print(&q);
	printf("\n>>> enqueue 20\n"); enqueue(&q, 20); queue_print(&q);
	printf("\n>>> enqueue 30\n"); enqueue(&q, 30); queue_print(&q);
	printf("\n>>> enqueue 40\n"); enqueue(&q, 40); queue_print(&q);
	printf("\n>>> enqueue 50\n"); enqueue(&q, 50); queue_print(&q);
	printf("\n>>> enqueue 60\n"); enqueue(&q, 60); queue_print(&q);

	printf("\n---------------------------------------------------------
    ----------------------------------------------------");

	printf("\n>>> dequeue\n"); dequeue(&q); queue_print(&q);
	printf("\n>>> dequeue\n"); dequeue(&q); queue_print(&q);
	printf("\n>>> dequeue\n"); dequeue(&q); queue_print(&q);
	printf("\n>>> dequeue\n"); dequeue(&q); queue_print(&q);
	printf("\n>>> dequeue\n"); dequeue(&q); queue_print(&q);
	printf("\n>>> dequeue\n"); dequeue(&q); queue_print(&q);

	return 0;
}

 

 

 

선형큐 문제점

● 가득 차지 않았지만, rear가 마지막 인덱스를 가리키고 있을 경우

    -> euqueue하기 위한 공간을 마련해야 하기 때문에 전체 데이터를 이동

    -> 비효율적인 작업 발생

    -> 해결 : 원형큐 

[Data Structure] 원형큐 (Circle-Queue)