[C language data structure 6] — implementation of queues

This is the 25th day of my participation in the August Genwen Challenge.More challenges in August

What is a queue

A queue is also a special kind of linear table, which is not castrated in the same way as a stack. Its insertion is only allowed at the end of the queue and its deletion is only allowed at the head of the queue. So it has a first-in, first-out feature (FIFO).

The queue is similar to our daily queue. Compared to the daily queue, queue-jumping is strictly forbidden. We can understand the queue by looking at the following figure:

The first element of a queue is called the head, and the last element of the queue is called the tail. The two most common operations in queues are queue entry and queue exit, also known as insert and delete operations. In a queue, only the head element can play and the entry element can come after the end of the queue.

Second, queue representation

Queues can also be represented by sequential storage and chained storage.

(1) Sequential storage structure

Since we care about the position of the head and tail of the team, we set the head pointer and tail pointer respectively, so our structure is defined as follows:

#define MAXSIZE 20
typedef int ElemType;
typedef struct{
    ElemType data[MAXSIZE];		// Use static arrays to store queue elements
    int front, rear;		    // Team head and team tail pointer
}SqQueue;
Copy the code

When implementing a queue using a sequential storage structure, we construct a queue that loops logically. More on that later.

(2) Chain storage structure

The queue implemented by the linked storage structure is also a castrated version of the list, so its nodes are defined the same as the list, but the linked queue also defines an additional queue structure:

// Chain queue node structure
typedef struct QNode{
    ElemType data;
    struct QNode *next;
}QNode;
// Chain queue structure
typedef struct{
    // end pointer
    QNode *front, *rear;
}LinkedQueue;
Copy the code

The structure of a chain queue contains a head pointer and a tail pointer.

Three, the implementation of the circular queue

(1) Circular queue

Let’s start by looking at how we could implement a queue using a sequential storage structure without the concept of a circular queue.

In the initial state, we set the head and tail Pointers to 0. During the queue operation, we ensure that the queue head pointer points to the subscript of the queue head and the queue tail pointer points to the next position of the queue tail. With these rules, we can queue 5 times and 5 times for a queue of length 6, as shown in the figure below:

During this operation, the team header pointer points to the location of the team header element except when the team is empty. And the team head pointer is equal to the team tail pointer when the team is empty.

So let’s look at the above operation and see how we can tell if the queue is full. One idea is to determine whether the tail pointer is equal to maxsize-1, but there is an obvious problem with doing so. For a queue with MAXSIZE=6, after 5 entries and 5 exits, our tail pointer is equal to MAXSIZE-1, but our queue is actually empty. To solve this problem, we use the logical structure of the circular queue. As shown:

Physically, we still use a contiguous array for storage. Logically, the end of our array and the beginning of our array are contiguous. For example, the end subscript is 7 and the start subscript is 0. So all we need is a formula that satisfies the following requirements:

Where Max represents the length of the array. For example, if the maximum length is 8, our tail pointer points to subscript 7, and if the queue is not full, we push and the tail pointer points to subscript 0. It’s easy to think of modular operations. So when we move the first and last Pointers, the action should look like this:

Q->rear = (Q->rear + 1) % MAXSIZE;
Q->front = (Q->front + 1) % MAXSIZE;
Copy the code

Now we can start implementing a circular queue.

(2) Queue initialization

To initialize a queue, we simply set the first and last Pointers to 0:

int InitSqQueue(SqQueue *Q){
    // The first and last Pointers point to 0
    Q->front = Q->rear = 0;
    return 1;
}
Copy the code

Therefore, the only way to determine whether the stack is empty is if the first and last Pointers are equal.

(3) Determine whether the queue is empty

We return 1 when the queue is empty and 0 when the queue is not empty:

int EmptySqQueue(SqQueue Q){
    return Q.rear == Q.front ? 1 : 0;
}
Copy the code

(4) Team entry operation

We need to determine whether the queue is full and how to place the input at the end of the queue:

int EnSqQueue(SqQueue *Q, ElemType elem){
    // If the queue is full, 0 is returned
    if((Q->rear + 1) % MAXSIZE == Q->front){
        return 0;
    }
    // Insert the element after the queue
    Q->data[Q->rear] = elem;
    // Move the queue pointer
    Q->rear = (Q->rear + 1) % MAXSIZE;
    return 1;
}
Copy the code

(5) Out of line operation

To check whether the queue is empty, and to operate the queue head pointer:

int DeSqQueue(SqQueue *Q, ElemType *elem){
    // If the queue is empty, return 0
    if(EmptySqQueue(*Q)){
        return 0;
    }
    // Get the header element
    *elem = Q->data[Q->front];
    // Move the header element
    Q->front = (Q->front + 1) % MAXSIZE;
    return 1;
}
Copy the code

Some of the other operations are not implemented here.

Realization of chain queue

A linked queue is very similar to a linked list, so let’s talk about it briefly.

(1) Initialization

Here we choose to use the chain queue with the leading node:

int InitLinkedQueue(LinkedQueue *Q){
    // Create a head node with a pointer to the head node
    Q->front = Q->rear = (QNode*)malloc(sizeof(QNode));
    // If memory is insufficient, 0 is returned
    if(! Q->front){return 0;
    }
    // Initializes the pointer field of the header node
    Q->front->next = NULL;
    return 1;
}
Copy the code

(2) Judge the team empty

When we initialize the queue, we point the pointer to the head node, so when the pointer is the same, the queue is empty:

int EmptyLinkedQueue(LinkedQueue Q){
    return Q.front == Q.rear ? 1 : 0;
}
Copy the code

(3) Team entry operation

The join operation takes place at the end of the queue, so we only need to insert one element at the end of the queue:

int EnLinkedQueue(LinkedQueue *Q, ElemType elem){
    // Create a node
    QNode  *s = (QNode*)malloc(sizeof(QNode));
    // If memory is insufficient, 0 is returned
    if(! s){return 0;
    }
    // Assign to the node
    s->data = elem;
    s->next = NULL;
    // Insert nodes at the end of the queue
    Q->rear->next = s;
    // Move the queue pointer
    Q->rear = s;
    return 1;
}
Copy the code

(4) Out of line operation

There are a few things to note about the queue exit operation:

1. The header pointer points to the header node, so the actual element we want to delete isfront->next
2. When there is only one element left in the queue, we modify the tail pointer

The first point is easy to understand. Let’s go straight to the code:

int DeLinkedQueue(LinkedQueue *Q, ElemType *elem){
    // If the queue is empty, return 0
    if(EmptyLinkedQueue(*Q)){
        return 0;
    }
    // define p to point to the element to be deleted
    QNode *p = Q->front->next;
    // Get the value of the element to be deleted
    *elem = p->data;
    // Move the queue head pointer
    Q->front->next = p->next;
    // If the last element is removed, the tail pointer needs to be modified
    if(Q->rear == p){
        Q->rear == Q->front;
    }
    free(p);
    return 1;
}
Copy the code

If we look at the following figure, there is only one element in the queue.

When we delete the last node, the tail pointer points to a piece of memory that has been destroyed. And if the queue is empty, our first pointer is not the same. So we need to change the end of the queue pointer when we delete the last node.

The criterion to determine whether it is the last node is whether next of the head node (q.front) is the last node.

(5) Destroy the queue

Since we requested the memory using the malloc function, we also need to manually destroy the memory:

int DestroyLinkedQueue(LinkedQueue *Q){
    QNode *p = Q->front, *s;
    // Check whether p moves to next at the end of the queue
    while (p){
        // Save the current node pointer
        s = p;
        //p moves backwards
        p = p->next;
        // Destroy the current node
        free(s);
    }
    return 1;
}
Copy the code

So far we have implemented queues in two ways: sequential storage and chained storage.