[C] Queue, 큐

Unlike stacks that have a LIFO structure, a queue is a FIFO(first-input-first-output) structure in which the positions of insertion and deletion of data are opposite. In other words, it is a data structure in which the data entered first appears first also. Because the location to return data and the location to input data is different, the queue uses two indexes. It is mainly used by naming it as front and rear. If the process of inserting data is called enQueue and the process of pulling out data is called deQueue, it corresponds to the process of push and pop in the stack, respectively.

후입선출구조를 가지는 스택과는 다르게 큐는 데이터의 삽입과 삭제의 위치가 반대인 선입선출 구조이다. 즉 먼저 넣었던 데이터가 먼저 나오는 자료구조이다. 데이터를 꺼내오는 위치와 넣는 위치가 다르기 때문에 큐는 2개의 인덱스를 사용한다. 주로 front 와 rear로 명명하여 사용한다. 데이터를 삽입하는 과정을 enQueue 라고 하며, 데이터를 꺼내는 과정을 deQueue라고 한다면 각각 스택에서의 push 와 pop의 과정과 대응된다.

The simplest way to implement a queue is to use an array. If the values of front and rear have the same value after initialization, it means that the queue is empty because all elements have been pulled out. If the index of rear reaches the end of the array, it means that the queue is full.

큐를 구현하는 가장 간단한 방법은 배열을 사용하는 것이다. front 와 rear의 값이 초기화 이후에 같은 값을 가지면 모든 요소를 꺼낸 것이므로 큐가 비었다는 뜻이며, rear의 인덱스가 배열 끝에 다다르면 큐가 다찼다는 것을 의미한다.

#include<stdio.h>
#define q_size 100

int Q[q_size];
int front = -1;
int rear = -1;

int isFull(void){
    if (rear == q_size -1) return 1;
    else return 0;
}

int isEmpty(void){
    if (rear == front) return 1;
    else return 0;
}

void enQueue(int x) {
	if (isFull()) return;
    else Q[++rear] = x;
    return;
}

int deQueue() {
    if (isEmpty()) return -1;
    else return Q[++front];
}

int main() {
	enQueue(1);
    enQueue(2); 
    printf("%d\n", deQueue());
    
    enQueue(3);

    printf("%d\n", deQueue());
    printf("%d\n", deQueue());

    return 0;
}

1
2
3

When putting data into a queue, you need to first determine whether the queue is empty or full. The above example checks the conditions in the form of a function, and it is simply implemented in single problem solving like algorithm problem solving. Looking at the algorithm, you can see that the actual data is not deleted, but rather the index is traversed. The queue index is always incremented, so when the end is reached, it is no longer available. In order to overcome this disadvantage, there is a circular queue that is implemented in a circular shape following the end and the beginning of the queue. A simple queue code is introduced below, followed by a circular queue code.

큐에 데이터를 넣을 때에는 큐가 비었는지 혹은 다 찼는지부터 파악해야한다. 위 예제는 함수형태로 조건들을 확인하며 알고리즘 문제풀이 처럼 단일 문제해결에서는 간단하게 구현한다. 알고리즘을 자세히 보면 실제 데이터가 삭제되는 것이 아니라 인덱스가 훑고 지나가는 것을 알 수 있다. 큐의 인덱스는 항상 증가하기 때문에 마지막에 도달하면 더 이상 사용할 수 없게 된다. 이러한 단점을 극복하기 위해 큐의 끝과 처음을 이어서 원형형태로 구현한 원형 큐가 있다. 아래에 간단한 형태의 큐 코드를 소개하고 이후 원형 큐 코드를 소개한다.

#include<stdio.h>

int Q[100];
int front = -1;
int rear = -1;

int main() {
	Q[++front]=1;
    Q[++front]=2;

    printf("%d\n", Q[++rear]);
    
    Q[++front]=3;

    printf("%d\n", Q[++rear]);
    printf("%d\n", Q[++rear]);

    return 0;
}

1
2
3

#include <stdio.h>
#define q_size 10

int front;
int rear;
int Q[q_size];

int isFull(void){
    if ((rear+1) % q_size == front) return 1;
    else return 0;
}

int isEmpty(void){
    if (rear == front) return 1;
    else return 0;
}

int main() {

    if (isFull());
    else {
        rear = (rear +1 ) % q_size; 
        Q[rear]= 1;
    }

    if (isFull());
    else {
        rear = (rear +1 ) % q_size; 
        Q[rear]= 2;
    }

    front = (front +1) % q_size;
    if (isEmpty());
    else printf("%d\n", Q[front]);
    
    return 0;
}

1