A queue of data structures

What is a queue

A queue is a special kind of linear table, special in that it only allows deletion at the front of the table and insertion at the rear. Like a stack, a queue is a linear table with limited operation. The end that inserts is called the end of the queue, and the end that deletes is called the head of the queue. The characteristics of queues are summarized as: first in, first out. This feature is similar to queuing in everyday life, first come, first served!

Implementation of queues

We implement queues using linked lists, with a head node and a node representing the head and tail of the queue. The time complexity of the outbound and inbound queues is O(1). The space complexity is order n.

One-way queue

A queue is a linear table that only allows insertion on one end and deletion on the other. Queues do not allow insertion in the middle

Circular queue

In order to make full use of vector space, the method to overcome the phenomenon of “false overflow” is to imagine vector space as a circle connected end to end, and call this vector a circular vector. The queues stored in them are called circular queues. A circular queue is a circular queue that connects sequential queues end to end and logically treats the table storing queue elements as a ring.

The bidirectional queue

A double-ended queue is a linear structure in which elements can be deleted and appended at both ends. A two-ended queue is more flexible than a normal queue. A two-ended queue can be implemented using a bidirectional linked list.

Unidirectional queue implementation:

Node definition

#include <stdio.h>
#include <stdlib.h>

typedef struct Node
{
    // Node value
    int val;
    // The node is in a node
    struct Node *next;
} Node;

typedef struct Queue
{
    /* data */
    // The head node of the queue
    Node *head;
    // The last node of the queue
    Node *tail;
    // Number of elements in the queue
    int len;
} Queue;

// Initialize the queue
Queue *init(a)
{
    // Request space
    Queue *q = malloc(sizeof(Queue));
    // Initializes member attributes
    q->head = q->tail = NULL;
    q->len = 0;
    return q;
}
Copy the code

The operation of entrance

// The element is queued
void push(Queue *q, int val)
{
    // Request space
    Node *node = malloc(sizeof(Node));
    node->val = val;
    node->next = NULL;
    // Check whether the queue is empty
    if (q->len == 0)
    {
        // Assign directly
        q->head = q->tail = node;
    }
    else
    {
        // Add the element to the end of the queue
        q->tail->next = node;
        q->tail = node;
    }
    // Length + 1
    q->len++;
}
Copy the code

The team operation

// The element exits the queue
int pop(Queue *q)
{
    if (q->len > 0)
    {
        // Get the value of the head node
        Node *h = q->head;
        int val = h->val;
        // No other elements are reset to NULL
        if (h->next == NULL)
        {
            q->head = q->tail = NULL;
        }
        else
        {
            q->head = h->next;
        }
        // Free up node space
        free(h);
        q->len--;
        return val;
    }
    return 0xFFFFFF;
}
Copy the code

Other operating

Return the length of the queue
int size(Queue *q)
{
    if (q == NULL)
    {
        return - 1;
    }
    return q->len;
}

void printQueue(Queue *q)
{
    if(q ! =NULL)
    {
        Node *h = q->head;
        while(h ! =NULL)
        {
            printf("%d->", h->val);
            h = h->next;
        }
        printf("\n"); }}// Destroy the queue
void destory(Queue *q)
{
    if(q ! =NULL)
    {
        // Release node elements one by one
        Node *h = q->tail;
        while(h ! =NULL)
        {
            free(h);
            h = h->next;
        }
        // Release the queue
        free(q); }}Copy the code

The test results

int main(a)
{
    Queue *queue = init();
    push(queue.10);
    push(queue.11);
    push(queue.12);
    push(queue.13);
    push(queue.14);
    printQueue(queue);
    printf("%d\n", size(queue));
    printf("%d\n", pop(queue));
    printf("%d\n", size(queue));
    printQueue(queue);
    destory(queue);
    return 0;
}
/ * 10 - > 11-12-13-14 - > > > > 5 10 4 11-12-13-14 - > > > > * /
Copy the code

Application of queues

As we can see from the nature of queues, queues are mainly used in first-come, first-served scenarios. Related to life is the waiting ticket of 12306 and some queuing scenes, this idea of sequential service is also reflected in some message queues.

I have uploaded the relevant code to gitlab: gitlab.com/BitLegend/c…

I will upload the data structure codes in this warehouse. If you need them, you can download them by yourself

Thank you for being here, and welcome to follow my VX official account: Yuan Yang Jie ZZ to learn more! See you next time!