Queue

Queue란?

Queue는 먼저 들어온 데이터가 먼저 나가는 선입선출(FIFO) 구조이다.

Queue의 구조

데이터를 넣으면 rear 쪽으로 들어가고, 데이터를 꺼낼 때는 front 쪽에서 나온다. 하나가 들어가면 꼬리가 길어진다.

Queue의 Usage

Queue는 FIFO 특성 덕분에 요청을 순서대로 공정하게 처리해야 하는 상황에서 유용하게 사용된다.

• Task scheduling: 요청이 들어온 순서대로 처리해야 공정하고 예측 가능한 시스템이 된다.
• Networking: 라우터나 스위치 등은 패킷이 들어오는 순서대로 전송해야 하므로 순서 보장이 중요하다.
• Customer service: 고객의 요청을 접수한 순서대로 처리하는 것이 공정하다.

 

Queue 구현: array 기반

전역 변수 선언

#define MAX_SIZE 100

int queue[MAX_SIZE];
int front = -1;
int rear = -1;

array를 통해 queue를 구현할 것이므로 queue 연산에 쓰이는 array, front, rear를 전역 변수로 선언해준다.

초기화 함수

void initialize() {
	front = -1;
	rear = -1;
}

front와 rear 모두 아무 index와 관련 없는 -1로 초기화 해준다.

isEmpty: 큐가 비었는지 확인

bool isEmpty() {
	if (front == -1 && rear == -1) {
		return true;
	}
	else {
		return false;
	}
}

front와 raer 모두 -1을 가지고 있으면 queue에는 어떠한 값도 가지고 있지 않음을 의미한다.

isFull: 큐가 가득 찼는지 확인

bool isFull() {
	if (rear == MAX - 1) {
		return true;
	}
	else {
		return false;
	}
}

rear에 값이 들어가게 되므로 rear의 index가 마지막 index를 가리키고 있다면 queue의 memory는 가득 찬 것이다.

enqueue: 데이터 추가 (rear 위치에 삽입)

1. queue에 데이터를 추가하는 작업이므로 queue가 가득 차있는지 먼저 확인한다.
2. 가득 차 있지 않다면 처음 데이터를 넣는 경우 front와 rear 모두 -1로 초기화 되어있으므로 모두 0으로 처음 값을 가리키도록 바꿔준다.
3. 처음 데이터를 넣는 경우가 아니라면 rear의 index를 하나씩 높여 queue에 접근할 수 있도록 한다.

void enquque(int x) {
	if (isFull()) {
		printf("Queue is full\n");
	}
	else if (isEmpty()) {
		front = rear = 0;
		queue[rear] = x;
	}
	else {
		rear++;
		queue[rear] = x;
	}
}

dequeue: 데이터 제거 (front 위치에서 삭제)

1. queue에 데이터를 제거하는 작업이므로 queue에 데이터가 존재하는지 먼저 확인해준다.
2. 데이터가 있는데 하나만 남아서 front와 rear이 같은 값을 가리킨다면 queue가 비어있음을 표시하기 위해 front와 rear 모두 -1로 변경해준다.
3. 하나만 남은 게 아닌 경우 front의 값을 하나씩 높여 queue에 접근하게 한다.

int dequeue() {
	if (isEmpty()) {
		printf("Queue is empty\n");
		return -1;
	}

	int value = queue[front];

	if (front == rear) {
		front = rear = -1;
	}
	else {
		front++;
	}
	return value;
}

 

Queue 구현: linked list 기반

전역 변수 선언

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

typedef struct Node {
    int data;
    struct Node* next;
} Node;

Node* front = NULL, * rear = NULL;

구조체를 선언하여, fornt와 rear를 전역 변수로 선언한다.

enqueue: 데이터 추가 (rear 위치에 삽입)

1. 새로운 노드를 생성한 뒤, 비어있는 queue에 처음 새로운 값이 들어간 경우, front와 rear은 같은 newnode를 가리키도록 설정한다.
2. 이후 값을 넣을 때는 rear->next = newnode 연산을 해준다.

void enqueue(int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (!newNode) {
        printf("Heap Overflow!\n");
        return;
    }
    newNode->data = value;
    newNode->next = NULL;
    if (rear == NULL) { // if the element is the first one
        front = rear = newNode;
    }
    else {
        rear->next = newNode;
        rear = newNode;
    }
}

dequeue: 데이터 제거 (front 위치에서 삭제)

1. 현재 front는 temp로 저장해준다. 이는 이후 front는 front->next로 초기화해주며, 기존 front는 삭제해주기 위함이다.
2. 출력하는 value는 temp->data로 해주고, front=front->next로 넘어가준다.
3. 이후 free(temp)

int dequeue() {
    if (front == NULL) {
        printf("Queue Underflow!\n");
        return -1;
    }
    Node* temp = front;
    int value = temp->data;
    front = front->next;
    if (front == NULL) rear = NULL; // if the element is the last one
    free(temp);
    return value;
}

Circular Queue 

Array로 queue를 만들면 앞 공간이 비어있어도 front와 rear가 뒤에 도달하면 더 이상 삽입이 불가하다.

1. queue의 크기가 5인 상태에서 enqueue를 5번 하면 rear = 5, dequeue를 5번 하면 front =5, rear = 5로 queue는 비어있다.
2. 하지만 rear == MAX_SIZE라면 더 이상 넣을 수 없다. 그러나 queue[0~4] 즉, 앞에 공간이 남아있게 된다.

이와 같이 rear이 끝에 도달함으로 인해 삽입이 불가능하여 memory가 낭비되는 것을 방지하기 위해 circular queue를 사용한다. 이는 queue의 끝인 rear이 배열 끝에 도달하면 앞으로 되돌아가도록 설정한다.

• rear = (rear + 1) % MAX_SIZE
• front = (front + 1) % MAX_SIZE

코드

#include <stdio.h>
#include <stdbool.h>  // bool 타입을 사용하려면 필요
#define MAX 5

int queue[MAX];
int front;
int rear;

void initialize() {
    front = -1;
    rear = -1;
}

bool isEmpty() {
    return front == -1;
}

bool isFull() {
    return (rear + 1) % MAX == front;
}

void enqueue(int x) {
    if (isFull()) {
        printf("Queue is full\n");
        return;
    }

    if (isEmpty()) {
        front = rear = 0;
    } else {
        rear = (rear + 1) % MAX;
    }

    queue[rear] = x;
}

int dequeue() {
    if (isEmpty()) {
        printf("Queue is empty\n");
        return -1;
    }

    int value = queue[front];

    if (front == rear) {
        // 큐에 요소가 하나만 있었을 경우
        front = rear = -1;
    } else {
        front = (front + 1) % MAX;
    }

    return value;
}

void print() {
    if (isEmpty()) {
        printf("Queue is empty\n");
        return;
    }

    printf("Queue: ");
    int i = front;
    while (1) {
        printf("%d ", queue[i]);
        if (i == rear)
            break;
        i = (i + 1) % MAX;
    }
    printf("\n");
}

int main() {
    initialize();

    enqueue(2);
    enqueue(3);
    enqueue(4);
    print();

    printf("Dequeued: %d\n", dequeue());
    printf("Dequeued: %d\n", dequeue());
    printf("Dequeued: %d\n", dequeue());

    enqueue(10);
    enqueue(11);
    enqueue(12);
    enqueue(13);
    enqueue(14);
    enqueue(15);  // 이건 삽입되지 않음 (full)

    print();

    printf("Dequeued: %d\n", dequeue());
    printf("Dequeued: %d\n", dequeue());
    printf("Dequeued: %d\n", dequeue());
    printf("Dequeued: %d\n", dequeue());
    printf("Dequeued: %d\n", dequeue());
    printf("Dequeued: %d\n", dequeue());  // 빈 큐

    return 0;
}

• rear이 MAX와 같은 값이 되면 0으로 만들어주는 rear=(rear+1)%MAX
• full은 front와 rear이 같은지, rear이 MAX인지에 따라 다르다.
• enqueue에서는 rear = (rear + 1) % MAX, dequeue에서는 front = (front + 1) % MAX 연산을 진행한다.