[자료구조] Queue 🚌

LEESEUNGYEOL·2022년 1월 19일

큐(Queue)🚌

큐?

버스에 타기 위해 줄을 서는 것을 생각하면 이해하기 좋습니다.

큐(queue) 역시 스택과 마찬가지로 일종의 리스트입니다.

단 데이터의 삽입은 한쪽 끝에서, 삭제는 반대쪽 끝에서만 일어납니다.

FIFO(First in Last Out)

삽입이 일어나는 곳을 후단(rear), 삭제가 일어나는 곳을 전단(front)라고 합니다. 이를 변수화하여 배열의 포인팅에 이용합니다.

CPU 스케줄링, 데이터 버퍼 등에서 활용됩니다.

메서드

IsEmpty()

선형 큐가 비었는지 검사

int is_empty() {
	if (front == rear) {
		return 1;
	}
	return 0;
}

IsFull()

선형 큐가 가득 찼는지 검사

int is_full() {
	if (rear == MAX_QUEUE_SIZE - 1) {
		return 1;
	}
	return 0;
}

addq() 🌟

큐의 rear에 새로운 원소를 삽입하는 연산

void addq(element item) {
	if (!is_full()) {
		queue[++rear] = item;
	}
}

deleteq() 🌟

큐의 front에 있는 원소를 큐로부터 삭제하고 반환하는 연산

element deleteq() {
	if (!is_empty()) {
		return queue[++front];
	}
}

peek()

큐의 front에 있는 원소를 제거하지 않고 반환하는 연산

element peek() {
	if (!is_empty()) {
		return queue[rear];
	}
}

큐 구현하기

스택과 마찬가지로 배열 혹은 연결리스트를 이용하여 구현할 수 있습니다

연결리스트로 구현된 큐

코드가 더 복잡하고 링크 필드 때문에 메모리 공간을 더 많이 사용하지만, 크기가 제한되지 않습니다.

큐의 rear에서는 삽입, front에서는 삭제가 일어나기때문에 연결리스트의 앞쪽을 front, 뒤쪽을 rear로 하는 것이 유리합니다.
-> 연결리스트의 마지막을 삭제하기 위해서는 항상 그전 노드의 주소를 알아야 하기 때문에 번거롭습니다.

삽입을 하기 위해서는 마지막 노드의 주소를 항상 기억해야 합니다.

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

typedef int element; //데이터 타입이 바뀔경우 자유롭게 쓰기 위해 처리
typedef struct { // 연결리스트 이용 위해
	element data;
	struct Node* next;
}Node;
typedef struct {
	Node* front; //queue의 쳣번째 주소
	Node* rear; //queue의 마지막 주소
	int size;
}QueueType; //여러개의 큐를 사용하기 위해 큐의 데이터 타입 포인터를 설정.

//삽입, 리스트의 가장 뒤 즉 rear에서 이루어진다
void addq(QueueType* q, element item) {
	Node* node = (Node*)malloc(sizeof(QueueType));
	node->data = item;
	node->next = NULL;
	//큐의 상태확인
	if (q->front == NULL) {//큐가 비었다면
		q->front = node;
		q->rear = node;
	}
	else { //큐가 비어있지 않다면
		q->rear->next = node;
		q->rear = node;
	}
}
//삭제, 리스트의 가장 앞 즉 front에서 이루어진다.
element deleteq(QueueType* q) {
	Node* temp = q->front;
	element item;
	item = temp->data; //데이터 꺼낸다.
	q->front = q->front->next; //front는 그 다음 노드를 가리키게 한다.
	if (q->front == NULL) {
		q->rear == NULL;
	}
	free(temp);
	return item;
}

배열로 구현된 큐

큐를 사용하는 가장 간단한 방법으로 1차원 배열을 활용합니다.

front와 rear의 값이 계속 증가만 하기 때문에 큐의 크기가 제한되어 있습니다.

#include <stdio.h>
#define MAX_QUEUE_SIZE 100
typedef int element;
element q[MAX_QUEUE_SIZE];
int rear = -1;
int front = -1;

//위 기본 메서드를 사용하여 구현

원형 큐(circural Queue)

배열의 처음과 끝이 연결되어 있다고 생각합니다.

front와 rear의 초기값을 0입니다.

front는 항상 큐의 첫번쨰 요소의 하나 앞을, rear은 마지막 요소를 가리킵니다.

포화 상태와 공백 상태를 구별하기 위해 하나의 자리는 항상 비워둡니다.

front == rear 이면 공백, front가 rear보다 하나 앞에 있으면 포화 상태.

나머지 연산자(mod)를 이용하여 구현합니다.

#include <stdio.h>
#define MAX_QUEUE_SIZE 100
typedef int element;
element q[MAX_QUEUE_SIZE];
int rear = 0;
int front = 0;

int is_empty() {
	return (rear == front);
}
int is_full() {
	return ((rear + 1) % MAX_QUEUE_SIZE == front);
}

void addq(element item) {
	if (!is_full()) {
		rear = (rear + 1) % MAX_QUEUE_SIZE;
		q[rear] = item;
	}
}

element deleteq() {
	if (!is_empty()) {
		front = (front + 1) % MAX_QUEUE_SIZE;
		return q[front];
	}
}