큐(Queue)

큐(Queue)

스택과 달리 선입선출의 구조를 가지는 자료구조이다.

 

큐의 특징

 - 먼저 집어 넣은 데이터가 먼저 나오는 선입선출(FIFO: First In First Out)의 구조를 가진다.

 - front 부분에서 삭제 연산, rear 부분에서 삽입 연산이 이루어진다.

 

선형 큐와 원형 큐

 

 - 선형 큐: 1차원 배열로 구성된 큐. front는 큐의 첫 번째 요소를 가리키고 rear는 큐의 마지막 요소를 가리킨다.

 - 원형 큐: 선형 큐의 문제점을 보완하기 위한 자료구조. front와 rear의 값이 배열의 끝에 도달하면 다음에 증가되는 값은 0이 된다.

 

큐의 활용

 - 먼저 들어온 순서대로 처리되어야 하는 작업 등 광범위하게 사용

 - 속도나 시간의 차이를 극복하기 위한 임시 기억 장치로 사용 = 버퍼(buffer)

---

큐의 추상 자료형

 

데이터

 

연산

init(): 큐의 초기화

isEmpty(): 큐가 비어있는지 확인

isFull(): 큐가 가득찾는지 확인

Enqueue(): 큐에 데이터를 저장

Dequeue(): 큐의 마지막 원소 삭제

Peek(): 저장 순서가 가장 앞선 데이터 반환 

size(): 요소의 개수 반환

---

c에서 연결 리스트를 기반으로 한 큐의 구현입니다.

#include <stdio.h>
#include <stdlib.h>

typedef int Data;

typedef struct LinkedNode {
	Data data;
	struct LinkedNode* link;
} Node;

Node* front = NULL;
Node* rear = NULL;

void init() {
	front = NULL;
	rear = NULL;
}

int isEmpty() {
	return front == NULL;
}

void Enqueue(Data data) {
	Node* p = (Node*)malloc(sizeof(Node));
	p->data = data;
	p->link = NULL;
	if (isEmpty()) front = rear = p;
	else {
		rear->link = p;
		rear = p;
	}
}

int Dequeue() {
	Node* p;
	Data data;

	p = front;
	data = p->data;
	front = front->link;

	if (front == NULL) rear = NULL;

	free(p);

	return data;
}

int peek() {
	return front->data;
}

int size() {
	Node* p;
	int count = 0;
	for (p = front; p != NULL; p = p->link) count++;

	return count;
}

int main() {
	init();
	printf("isEmpty : %d\n\n", isEmpty());

	for (int i = 0; i < 5; i++) {
		Enqueue(i);
		printf("Enqueue : %d\n", i);
	}

	printf("\nisEmpty : %d\n", isEmpty());
	
	printf("\nsize : %d\n", size());
	printf("peek : %d\n\n", peek());

	for (int i = 0; i < 2; i++) {
		printf("Dequeue : %d\n", Dequeue());
	}

	printf("\nsize : %d\n", size());
	printf("peek : %d\n", peek());

	return 0;
}