Implementing Queues in C: Sequential and Linked Queues

In computer science, a queue is a very important data structure. It follows the “First In, First Out” (FIFO) principle, which means that the earliest added element will be the first to be removed. This article will introduce how to implement a queue in C, including both sequential and linked queue methods.

1. Sequential Queue

1. Definition of Sequential Queue

A sequential queue uses a contiguous block of memory to store data. In this implementation, we use an array to represent the entire queue and two pointers (or indices) to mark the positions of the head and tail.

2. Properties of Sequential Queue

• Capacity: The maximum number of elements that can be accommodated.
• Head Pointer: Points to the first element.
• Tail Pointer: Points to the position after the last element.

3. Basic Operations

A sequential queue typically supports the following basic operations:

1. Enqueue
2. Dequeue
3. Check if empty
4. Get current size
5. Clear queue

4. Implementation Code Example

Below is the implementation of a sequential queue in C:

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100 // Define maximum capacity of the queue

typedef struct {
    int data[MAX_SIZE]; // Array to store data
    int front;          // Front pointer
    int rear;           // Rear pointer
} SeqQueue;

// Initialize the sequential queue
void initSeqQueue(SeqQueue* q) {
    q->front = -1;
    q->rear = -1;
}

// Enqueue operation
int enqueue(SeqQueue* q, int value) {
    if (q->rear == MAX_SIZE - 1) {
        printf("Error: Queue is full!\n");
        return -1;
    } else {
        q->data[++q->rear] = value;
        if (q->front == -1) {
            q->front = 0;
        }
        return 0;
    }
}

// Dequeue operation
int dequeue(SeqQueue* q, int* value) {
    if (q->front == -1 || q->front > q->rear) {
        printf("Error: Queue is empty!\n");
        return -1;
    } else {
        *value = q->data[q->front++];
        return 0;
    }
}

// Check if empty
int isEmpty(SeqQueue* q) {
    return (q->front == -1 || q->front > q->rear);
}

// Get current size
int size(SeqQueue* q) {
    if (isEmpty(q))
        return 0;
    return (q->rear + 1) - q->front;
}

int main() {
    SeqQueue queue;
    initSeqQueue(&queue);
    enqueue(&queue, 10);
    enqueue(&queue, 20);
    enqueue(&queue, 30);
    int dequeuedValue;
    while (!isEmpty(&queue)) {
        dequeue(&queue, &dequeuedValue);
        printf("%d ", dequeuedValue);
    }
    return 0;
}

2. Linked Queue

1. Definition of Linked Queue

A linked queue is a data structure formed by dynamically linking nodes. Compared to traditional arrays, it can flexibly manage memory and dynamically expand.

Each node contains not only the actual data but also a reference to the next node.

2. Definition of Linked List Node

We first need to define a linked list node. The data type generally includes two parts: one for the data value and one for the position of the next node:

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

typedef struct {
    Node* front;
    Node* rear;
} LinkQueue;

Features and Basic Operations

Similar to sequential queues, typical basic methods include…

• Enqueue operation: Insert an item at the <span>rear</span>.
• Dequeue operation: Remove an item from the <span>front</span>.
• Check if empty: If the head node is NULL, it indicates empty.

Linked-list Queue

Value.

Example as follows — —

void enqueue(LinkQueue *l, int data) {
    Node* newNode = malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    if (l->rear != NULL) {
        l->rear->next = newNode;
        l->rear = newNode; // New nodes are not null
    } else {
        l->front = l->rear = newNode;
    }
}
// Ensure proper deletion and memory management...

This concludes all necessary steps for demonstration (and display effects). I hope that through learning this content, you can master sorting with C and value comparison!