How to implement an array-based queue using C language

In programming, queue is a commonly used data structure. Many programming languages ​​have their own queue implementations, such as Queue in Java and deque in Python. However, in C language, there is no ready-made queue implementation. Therefore, in C language, we need to implement the queue by defining an array and using pointers and other tricks.

In this article, we will introduce how to implement an array-based queue using C language.

1. Define a queue structure

We can implement queue operations by defining a queue structure. This queue structure includes information such as the size of the queue, head and tail pointers, element data, etc.

#define MAX_SIZE 100

typedef struct queue {
    int size;
    int front;
    int rear;
    int data[MAX_SIZE];
} Queue;

In the above code, we define a MAX_SIZE constant to represent the maximum size of the queue, and declare a queue named Queue by defining a structure.

Among them, size represents the size of the queue, front represents the queue head pointer, rear represents the queue tail pointer, and data is an array storing elements.

2. Queue initialization operation

In the implementation of the queue, the queue initialization operation needs to be performed first to ensure the correct use of the queue.

void init(Queue *q) {
    q->size = 0;
    q->front = 0;
    q->rear = -1;
}

In the above code, we define an initialization function init, which accepts the pointer q pointing to the queue structure as a parameter, and sets the size of the queue to 0, the head pointer to 0, and the tail pointer to 0. The pointer is set to -1, indicating that the queue is empty.

3. Element enqueuing operation

The enqueuing operation of the queue is to place an element at the end of the queue. The implementation here is to add the element to the end of the array data , and update the position of the rear pointer.

int enqueue(Queue *q, int value) {
    if(q->size == MAX_SIZE) {
        return 0;
    }
    q->rear++;
    q->data[q->rear] = value;
    q->size++;
    return 1;
}

In the above code, first determine whether the queue is full. If it is full, it returns 0 to indicate that the insertion failed. Otherwise, the rear pointer is moved backward by one position and the element value is assigned to the data array. tail, and add 1 to the queue size, and finally return 1 to indicate successful insertion.

4. Element dequeuing operation

The dequeuing operation of the queue is to take out the element at the head of the queue and update the position of the front pointer. The idea implemented here is to return the element value at the front position in data, move the front pointer backward one bit, and update the size of the queue at the same time.

int dequeue(Queue *q) {
    if(q->size == 0) {
        return -1;
    }
    int value = q->data[q->front];
    q->front++;
    q->size--;
    return value;
}

In the above code, first determine whether the queue is empty. If it is empty, return -1 to indicate that the queue is empty. Otherwise, return the element value at the front position in the data and move the front pointer backward. One bit, decrements the queue size by 1, and returns the element value.

5. Implementation of test queue

Now that we have implemented various operations of the queue, let’s test it:

#include <stdio.h>

int main() {
    Queue myQueue;
    init(&myQueue);
    enqueue(&myQueue, 1);
    enqueue(&myQueue, 2);
    enqueue(&myQueue, 3);
    printf("%d\n", dequeue(&myQueue));
    printf("%d\n", dequeue(&myQueue));
    printf("%d\n", dequeue(&myQueue));
    return 0;
}

The above test In the code, we first define a queue named myQueue and initialize it using the init function. Then we use the enqueue function to insert the numbers 1, 2, and 3 into the queue, and use the dequeue function to remove elements from the queue and output them to the screen.

The output here should be:

1
2
3

6. Summary

In this article, we learned how to use C language to implement an array-based queue. By defining a queue structure and related operation functions, we can easily add, delete and access elements in the queue. Although it is troublesome to use pointers to implement queues, this method can help us better understand the principles of queues and is of great help in learning data structures and algorithms.

The above is the detailed content of How to implement an array-based queue using C language. For more information, please follow other related articles on the PHP Chinese website!