[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.

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.

#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