큐(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];
	}
}

이미지 출처
http://blog.naver.com/coolten/140057846054
http://blog.naver.com/coolten/140057845842
https://encrypted-tbn0.gstatic.com
https://media.vlpt.us/images/i_meant_to_be/post/a6ede145-e1d7-460e-95e0-
https://velog.io/@i_meant_to_be/Queue-C