A queue is a widely used data structure in computer science, characterized by the "First In First Out" (FIFO) principle. This feature makes queues play a crucial role in many practical applications, such as task scheduling, buffer management, and message passing. This article will delve into the basic concepts of queues and implement a simple yet efficient queue structure using a linked list.

1. Basic Concepts

1.1 Definition
A queue is a linear data structure that follows the FIFO (First In First Out) principle. Specifically, the element that is inserted first will be removed first. The queue simulates a real-life queuing phenomenon: new arrivals join at the tail of the queue, while the person at the front of the queue leaves one by one.

In the diagram below, the front of the queue is called the "head," and the rear is called the "tail." The operation of adding an element to the tail is called "enqueue," while the operation of removing the element from the head is called "dequeue."

1.2 Basic Operations

The main operations of a queue include:

• Enqueue (Push): Adds an element to the tail of the queue.

• Dequeue (Pop): Removes and returns an element from the head of the queue.

• Front: Returns the front element without removing it.

• Back: Returns the rear element without removing it.

• isEmpty: Checks if the queue is empty.

• Size: Returns the number of valid elements in the queue.

1.3 Characteristics of a Queue
Queues have several notable characteristics:

• FIFO: The first element to enter is the first to exit.

• Operation Restrictions: Elements can only be dequeued from the head and enqueued at the tail.

• Head Element: The head is the element that can be accessed and removed.

• Empty Queue: No dequeue operation can be performed if the queue is empty.

• Dynamic Size: The queue can expand or shrink as needed to meet varying storage requirements.

2. Linked Queue Implementation

1. Defining the List Node
   Before implementing the linked queue, we first define a linked list node structure:

typedef int DataType;
// Define the node structure
typedef struct Node
{
    DataType data; // Data field
    struct Node* next; // Pointer field
} Node;

2. Defining the Queue Structure
   Next, we define the queue structure, which includes pointers to the head and tail of the queue, as well as the queue's size:

// Define the queue structure
typedef struct Queue
{
    Node* phead; // Head of the queue
    Node* ptail; // Tail of the queue
    int size; // Queue size
} QU;

3. Basic Operations
   We will implement some basic operations to better manage the queue:

(1) Initializing the Queue

// Initialize the queue
void QueueInit(QU* p)
{
    assert(p);
    p->phead = p->ptail = NULL; // Initialize head and tail pointers to NULL
    p->size = 0; // Initialize queue size to 0
}

(2) Enqueue

The enqueue operation adds a new element to the tail of the queue. We need to check if the queue is empty to determine how to add the new node.

// Create a new node
Node* CreateNode(DataType x)
{
    Node* newnode = (Node*)malloc(sizeof(Node));
    if (newnode == NULL) {
        perror("malloc fail");
        exit(1); // Exit program if memory allocation fails
    }
    newnode->data = x; // Set node data
    newnode->next = NULL; // Initialize next pointer to NULL
    return newnode; // Return the new node
}
 
// Enqueue operation (insert at the tail)
void QueuePush(QU* p, DataType x)
{
    assert(p);
    Node* newnode = CreateNode(x);
    if (p->phead == NULL) // When the queue is empty
    {
        p->phead = p->ptail = newnode; // Both head and tail pointers point to the new node
    }
    else // When the queue is not empty
    {
        p->ptail->next = newnode; // The next pointer of the tail node points to the new node
        p->ptail = newnode; // Update the tail pointer to the new node
    }
    ++p->size; // Increase the queue size by 1
}

(3) Queue Empty Check

// Check if the queue is empty
bool QueueEmpty(QU* p)
{
    assert(p);
    return p->phead == NULL; // The queue is empty if the head pointer is NULL
}

(4) Dequeue

The dequeue operation removes an element from the head. We need to handle two cases: when the queue is empty or contains only one element.

// Dequeue operation (remove from the head)
void QueuePop(QU* p)
{
    assert(p);
    assert(!QueueEmpty(p)); // Ensure the queue is not empty
    if (p->phead == p->ptail) // When there's only one element
    {
        free(p->phead); // Free the head node
        p->phead = p->ptail = NULL; // Set head and tail pointers to NULL
    }
    else
    {
        Node* del = p->phead; // Save the node to be deleted
        p->phead = p->phead->next; // Update the head pointer to the next node
        free(del); // Free the deleted node
    }
    --p->size; // Decrease the queue size by 1
}

(5) Get Front Element

// Get the data of the front element
DataType QueueFront(QU* p)
{
    assert(p);
    assert(!QueueEmpty(p)); // Ensure the queue is not empty
    return p->phead->data; // Return the data of the head node
}

(6) Get Back Element

// Get the data of the back element
DataType QueueBack(QU* p)
{
    assert(p);
    assert(!QueueEmpty(p)); // Ensure the queue is not empty
    return p->ptail->data; // Return the data of the tail node
}

(7) Get Queue Size

// Get the size of the queue
int QueueSize(QU* p)
{
    assert(p);
    return p->size; // Return the size of the queue
}

(8) Destroy Queue

Finally, we provide a destroy operation to free allocated memory and prevent memory leaks.

// Destroy the queue
void QueueDestroy(QU* p)
{
    assert(p);
    Node* pcur = p->phead;
    while (pcur) // Traverse all nodes and free memory
    {
        Node* next = pcur->next;
        free(pcur);
        pcur = next;
    }
    p->phead = p->ptail = NULL; // Set head and tail pointers to NULL
    p->size = 0; // Set queue size to 0
}

3. Complete Code

Queue.h

This section includes function declarations and header file references.

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

typedef int DataType;

// Define the node structure
typedef struct Node {
    DataType data;  // Data field
    struct Node* next;  // Pointer field
} Node;

// Define the queue structure
typedef struct Queue {
    Node* phead;  // Head of the queue
    Node* ptail;  // Tail of the queue
    int size;  // Queue length
} QU;

// Function declarations
void QueueInit(QU* p);  // Initialize the queue
void QueuePush(QU* p, DataType x);  // Enqueue operation (insert at the tail)
bool QueueEmpty(QU* p);  // Check if the queue is empty
void QueuePop(QU* p);  // Dequeue operation (remove from the head)
DataType QueueFront(QU* p);  // Get the front element
DataType QueueBack(QU* p);  // Get the back element
int QueueSize(QU* p);  // Get the queue size
void QueueDestroy(QU* p);  // Destroy the queue

Queue.c

This section includes function definitions.

#define _CRT_SECURE_NO_WARNINGS
#include"Queue.h"

// Initialize the queue
void QueueInit(QU* p) {
    assert(p);
    p->phead = p->ptail = NULL;  // Initialize head and tail pointers to NULL
    p->size = 0;  // Initialize queue size to 0
}

// Create a new node
Node* CreateNode(DataType x) {
    Node* newnode = (Node*)malloc(sizeof(Node));
    if (newnode == NULL) {
        perror("malloc fail");
        exit(1);  // Exit program if memory allocation fails
    }
    newnode->data = x;  // Set node data
    newnode->next = NULL;  // Initialize next pointer to NULL
    return newnode;  // Return the new node
}

// Enqueue operation (insert at the tail)
void QueuePush(QU* p, DataType x) {
    assert(p);
    Node* newnode = CreateNode(x);
    if (p->phead == NULL) {  // When the queue is empty
        p->phead = p->ptail = newnode;  // Both head and tail point to the new node
    } else {  // When the queue is not empty
        p->ptail->next = newnode;  // The next pointer of the tail points to the new node
        p->ptail = newnode;  // Update the tail pointer to the new node
    }
    ++p->size;  // Increase the queue size by 1
}

// Check if the queue is empty
bool QueueEmpty(QU* p) {
    assert(p);
    return p->phead == NULL;  // Queue is empty if head pointer is NULL
}

// Dequeue operation (remove from the head)
void QueuePop(QU* p) {
    assert(p);
    assert(!QueueEmpty(p));  // Ensure the queue is not empty
    if (p->phead == p->ptail) {  // If there is only one element
        free(p->phead);  // Free the head node
        p->phead = p->ptail = NULL;  // Set both head and tail pointers to NULL
    } else {
        Node* del = p->phead;  // Save the node to be deleted
        p->phead = p->phead->next;  // Update the head pointer to the next node
        free(del);  // Free the deleted node
    }
    --p->size;  // Decrease the queue size by 1
}

// Get the front element
DataType QueueFront(QU* p) {
    assert(p);
    assert(!QueueEmpty(p));  // Ensure the queue is not empty
    return p->phead->data;  // Return the data of the head node
}

// Get the back element
DataType QueueBack(QU* p) {
    assert(p);
    assert(!QueueEmpty(p));  // Ensure the queue is not empty
    return p->ptail->data;  // Return the data of the tail node
}

// Get the queue size
int QueueSize(QU* p) {
    assert(p);
    return p->size;  // Return the size of the queue
}

// Destroy the queue
void QueueDestroy(QU* p) {
    assert(p);
    Node* pcur = p->phead;
    while (pcur) {  // Traverse all nodes and free memory
        Node* next = pcur->next;
        free(pcur);
        pcur = next;
    }
    p->phead = p->ptail = NULL;  // Set both head and tail pointers to NULL
    p->size = 0;  // Set the queue size to 0
}

main.c

#define _CRT_SECURE_NO_WARNINGS
#include"Queue.h"

void test() {
    QU qu;
    QueueInit(&qu);
    QueuePush(&qu, 1);
    QueuePush(&qu, 2);
    QueuePush(&qu, 3);
    QueuePush(&qu, 4);
    QueuePop(&qu);
    printf("head:%d
", QueueFront(&qu));
    printf("back:%d
", QueueBack(&qu));
    printf("size:%d
", QueueSize(&qu));
}

int main() {
    test();
    return 0;
}

V. Summary

In this blog, we implemented a basic queue data structure, covering the following key functionalities:

1. Initialize the Queue: Create an empty queue to prepare for subsequent operations.

2. Enqueue: Implemented the function to add new elements to the tail of the queue, ensuring dynamic expansion.

3. Queue Empty Check: Provided a method to check if the queue is empty, useful for checking the queue's state before operations.

4. Dequeue: Implemented the function to remove elements from the front of the queue, following the FIFO (First In, First Out) principle.

5. Get Front Element: Allows access to the front element without removing it, useful for checking the next element to be processed.

6. Get Back Element: Allows access to the back element, although not commonly used, it has its applications in certain scenarios.

7. Get Queue Size: Implemented the function to retrieve the current number of elements in the queue, aiding in queue management and monitoring.

8. Destroy Queue: Provided a method to clean up resources, preventing memory leaks.

By implementing these basic operations, we demonstrated the essential characteristics and usage of a queue, laying the foundation for understanding its importance in real-world applications. Queues, as a crucial data structure, are widely used in task scheduling, resource management, and many other fields. We hope this blog helps you better understand and utilize queues.