Abstract: This paper mainly introduces the structure, basic principle and operation of queue, involving two kinds of implementation: sequential queue and chain queue.

1. What is a queue?

Let’s take an everyday example: waiting in line to buy food.

People line up in front of the window to buy food on a first come, first served basis. After buying, they walk away and it’s the next person’s turn to buy food. Newcomers line up at the end of the line and can’t jump the queue.

As can be seen, the above “team” is only allowed to enter from one end and leave from the other end.

Such a queue, when placed in a data structure, is called a queue.

First, the queue is a linear table, so it has the basic characteristics of a linear table.

Second, the queue is a limited linear table with limitations that allow entry into the queue from one end and exit from the other.

According to the above characteristics, can draw show intention:

After joining element 1 and joining element 4:

Here are some related terms:

Queue: To queue, that is, to insert elements into the queue
Dequeue: To leave the queue, that is, to remove an element from the queue
Team head: the end of the team that is allowed to leave (delete)
End: The end at which entry is allowed
Header element: The first element in the queue to be pushed
Tail element: The last element in the queue to be pushed

We can directly treat the head element as the head of the team and the tail element as the tail of the team. (These nouns and concepts need not be studied in detail.)

An important feature of a queue is that the operation of joining the queue is carried out at the end of the queue and the operation of leaving the queue is carried out at the head of the queue. Therefore, the order of joining the queue of elements in the figure above is 1, 2 and 3, and the order of leaving the queue is: First In First Out (FIFO) and Last In Last Out (LILO).

To summarize, a queue is a limited first-in, first-out linear table that allows only inserts at one end and deletes at the other.

2. The implementation idea of queue

Like stacks, queues can be implemented in two ways: sequential queues for arrays and linked queues for linked lists.

2.1. Array implementation – Sequential queue

An array of sequential queues is shown below:

As you can see, to implement a sequential queue, we need the following structure:

data-storingAn array of–data[]
Representing a queueThe maximum capacityThe value of the –MAXSIZE
Identify the head of the queueTeam head subscript–front
Identify the end of the lineOf the subscript–rear

Front and rear change with queue entry and queue exit. For convenience, we specify that in a non-empty queue, the tail index is the index of the next element of the tail element.

Now that we know about constructs, we can easily implement them using C constructs:

#define MAXSIZE 5 // The maximum storage capacity of the sequential queue
/* The sequential queue structure */
typedef struct {
    int data[MAXSIZE];
    int front; // queue header subscript
    int rear; // team tail index
} QueueArray;
Copy the code

2.2. Linked list implementation — Chain queue

We use a singly linked list of leading nodes to implement the queue, as shown below:

As you can see, to implement a chain queue, you need the following structure:

The basic element node of a singly linked listQueueNode
- The data domain where the data is stored —data
- Pointer field to the next node —next
A header pointer to the linked listhead
The header pointer that identifies the header end of the team —front
The tail pointer that identifies the tail of the team —rear

Head and front both point to the first node in the list, so this pointer can be combined into one.

In this way, we can use the tail insertion method of the linked list to achieve the queue operation, with the head deletion method of the linked list to achieve the queue operation.

Figure out the structure, using the structure to achieve the following:

/* The structure of the node of a singly linked list */
typedef struct QueueNode {
    int data; / / data domain
    struct QueueNode *next; / / pointer field
} QueueNode;

/* The structure of the chain queue */
typedef struct {
    QueueNode *front; // queue head pointer
    QueueNode *rear; // end of queue pointer
} QueueLink;
Copy the code

3. Queue status

3.1. Sequential Queues (Problem edition)

【 empty queue 】 : There is no element in the empty queue. In this case, the index of the front queue and the index of the rear queue are both 0, i.e. Front = rear = 0:

Non-empty non-full queue: The queue is not empty and has free space:

Front = 0, rear = MAXSIZE: front = 0, rear = MAXSIZE:

As you can see from the figure above, the tail index of a non-empty queue, rear, is always the index of the next element of the tail element.

3.2. False full queue

These are the three states of sequential queues with arrays, but the three queues in the figure above are problematic, and that is the storage problem of queues!

To restate two important features of queues:

Queues can only delete elements at the head of the queue and insert elements at the end
We stipulate that:frontIs the index of the header element,rearIs the index of the element at the end of the queue, which changes with the exit and entry operations

As front is at subscript 0 in the above three pictures, it is not easy to see the problem. Please see the process diagram below:

Simply describe the process below in words:

Figure 1: Empty queue

Figure 2: There are three elements of team entry: 1, 2 and 3

Figure 3: Team out two elements: 1, 2

Figure 4: Two elements of team entry: 4 and 5

So far, so good.

Figure 5: Enqueue one element, but in Figure 4 rear = 5 is out of the maximum range of the array, so enqueue one element in Figure 5 gives an error and the queue cannot insert any more elements.

Is the queue in Figure 5 full? Not full! Can I continue to insert elements? Can’t! Having a spare room and not being able to use it is like having a hotel with a spare room and not letting customers stay. It is bad business.

A full queue is a queue that runs out of space and cannot insert any more elements. Although the queue in Figure 5 cannot insert any more elements, it still has space left, so such a queue is not called a full queue, but a false full queue.

The reason the fake full queue is a problem is because the space in the sequential queue is finite, and after a few queueing operations, our rear “runs” out of the array and out of bounds.

One element is stored, but the entire queue cannot be stored because it is false. Such a queue is certainly not a valid data structure.

How do you solve it? The error is that Rear is out of bounds, and most of the front of the queue is idle, so when Rear is out of bounds, can we move it to index 0?

Obviously it can, and that creates a loop, which we call a loop where front and rear can be recycled.

3.3. Circular queues

To highlight the word “loop”, we draw the sequential queue as a circle:

The rear and front of a circular queue can rotate around and around in a queue, like the hour and minute hands of a clock. No more unusable space.

As the form of the sequential queue changes from “straight” to this loopable, the judgment of state changes.

Empty queue: There are no elements in the queue, as shown in the figure above.

Note that the condition for an empty queue is not front = rear = 0, for example, an empty queue is still empty after three enqueues and three dequeues:

So, if the loop queue is empty, the condition should be front = rear

Full queue: No free space in the queue

The figure above shows an empty queue with a maximum capacity of 8. After 7 elements join the queue, there is still 1 free position left in the queue. If we join another element at this time:

There’s no free space in the queue, but notice that the queue satisfies rear = front, but shouldn’t the queue that satisfies rear = front be empty?

This leads to a misunderstanding.

How about we clear the air by taking a step back and using one less element. The following figure specifies that this is a full queue.

We say, when front is next in rear, the queue is full.

For example, in the full queue above, front = 3 is next to rear = 2.

So the condition for a full queue is rear + 1 = front, but that’s not accurate.

Because front and rear in a circular queue are used in a circular way, like the hour hand of a clock, it is not reasonable to judge the position only by the size of the subscript. Rear + 1 = front; rear + 1 = front

Just as the hour hand of a clock returns to zero when it reaches 12, front and rear should return to zero when it reaches a certain number, which is MAXSIZE.

So if we had rear = 7, if we did the usual thing, the next step would be rear = 8, but in this case, we’re setting it to zero, so the next step would be rear = 0.

The mathematical formula for this zeroing is rear % MAXSIZE

So the full queue should be judged as :(rear + 1) % MAXSIZE = front.

** [non-empty/non-full queue] ** It is easy to understand and will not be repeated.

3.4. Chain queue

We use a single linked list of leading nodes to implement a linked queue.

Empty queue: an empty linked list, in which the queue head pointer (and the queue head pointer) and the queue tail pointer point to the head node.

[Non-empty queue] : Unlike the sequential queue, the space of the chain queue is unlimited (as long as your memory is large enough), so there is no concept of “full queue” or “circular queue”.

4. The initialization

Before performing operations on a queue, it should be initialized, that is, an empty queue should be initialized.

4.1. Sequential queues

Set the head and tail subscripts of the queue to 0.

/** * Initialize the sequential queue: set the head and tail indices to 0 * queue: pointer to the queue */
void init(QueueArray *queue)
{
    queue->front = 0;
    queue->rear = 0;
}
Copy the code

4.2. Chain queue

Create the head node and point both the head and tail Pointers to the head node.

/** * initializes the queue: place the queue head pointer and the queue tail pointer to the head node */
void init(QueueLink *queue)
{
    // Create a header
    QueueNode *head_node = create_node(0);
    // The queue header pointer points to the header node
    queue->front = head_node;
    queue->rear = head_node;
}
Copy the code

5. Join the team

The join operation only allows elements to enter from the back of the queue.

5.1. Sequential queues

Previously, we specified that the tail of the queue is the next element of the tail element, so we directly put the element to join the queue at the tail index, and then the tail index “plus one”. (Note: increments in the loop queue are modulo to MAXSIZE)

/** * queue: pointer to queue * elem: data to queue * return: 0 failed, 1 succeeded */
int en_queue(QueueArray *queue.int elem)
{
    // Check whether the queue is full
    if ((queue->rear + 1) % MAXSIZE == queue->front) {
        printf("The queue was full and no further entry was possible. \n");
        return 0;
    }
    // The element joins the team
    queue->data[queue->rear] = elem;
    // add one to the end of the queue
    queue->rear = (queue->rear + 1) % MAXSIZE;
    return 1;
}
Copy the code

5.2. Chain queue

The queuing operation of a linked queue is essentially the tail insertion method of a single linked list:

/** * queue: pointer to queue * elem: queue data */
void en_queue(QueueLink *queue.int elem)
{
    // Create new nodes
    QueueNode *new = create_node(elem);
    // Join the queue
    queue->rear->next = new;
    queue->rear = new;
}
Copy the code

6. Out of line operation

The exit operation only allows elements to exit from the head of the queue.

6.1. Sequential queues

Take the element at the header subscript out of the queue, then add one to the header subscript (modulo MAXSIZE).

/** * queue: pointer to queue * elem: variable to save queue data * return: 0 failed, 1 succeeded */
int de_queue(QueueArray *queue.int *elem)
{
    // check whether the queue is empty
    if (queue->front == queue->rear) {
        printf("Queue empty, no element to exit. \n");
        return 0;
    }
    // Element out of the queue
    *elem = queue->data[queue->front];
    // Team head index + 1
    queue->front = (queue->front + 1) % MAXSIZE;
    return 1;
}
Copy the code

6.2. Chain queue

The queuing operation of linked queue is essentially the head deletion method of single linked list. Note that if the last element in the queue exits, the end pointer needs to be redirected to the head node after the queue exits to re-form the empty queue.

/** * queue: pointer to queue * elem: pointer to save variable * return: 0 failed, 1 succeeded */
int de_queue(QueueLink *queue.int *elem)
{
    // check whether the queue is empty
    if (queue->front == queue->rear) {
        printf("Queue empty, no element to exit. \n");
        return 0;
    }
    QueueNode *front_node = queue->front->next; // Team head element
    // Save data
    *elem = front_node->data;
    // The header element is deleted.
    queue->front->next = front_node->next;
    // If the element is finished, the end pointer points back to the head node
    if (front_node == queue->rear)
        queue->rear = queue->front;
    free(front_node);
}
Copy the code

7. Traversal operations

This section uses printing the entire queue as an example to describe how to traverse a queue.

Sequential queue has head index and tail index, chain queue has head index and tail index, what we need to do is to use a temporary variable, from the head index to the tail index.

7.1. Sequential queues

With the aid of temporary variable I, increment one by one from the head index until the end of the tail index.

The start flag is: I = front

I = (I + 1) % MAXSIZE

The end flag is I % MAXSIZE = rear

/** * prints the queue */
void output(QueueArray queue)
{
    int i = queue.front;
    while(i % MAXSIZE ! =queue.rear) {
        printf("%d ".queue.data[i]);
        i = (i + 1) % MAXSIZE;
    }
    printf("\n");
}
Copy the code

How do I calculate the length of the sequential queue? Of course, you can iterate through the queue and store the length by counting variables, which is a little bit more cumbersome. Since the sequential queue is implemented using arrays, the length of the sequential queue can be calculated directly from the subscripts.

If it’s a non-cyclic queue, it’s easy, just rear-front is the length of the queue.

But you can’t just subtract the loop queue like that, because the relationship between rear and front is uncertain.

On the left, rear < front, we can view the length as two parts:

The subscript 0 torear, the length ofrear - 0
The subscriptMAXSIZE - 1 到 rear, the length ofMAXSIZE - front

So the length is rear-front plus MAXSIZE

In order to satisfy the case of rear > front on the right, the MAXSIZE is added, so it needs to mod MAXIZE.

So the length of the loop queue is (rear-front + MAXSIZE) % MAXSIZE (even if it is empty).

7.2. Chain queue

Use the pointer P to traverse from the top element to the bottom element.

/** * prints the queue */
void output(QueueLink *queue)
{
    QueueNode *p = queue->front->next; //p points to the team head element
    while(p ! =NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}
Copy the code

That is the basic principle and operation of queues.

Complete code please visit lot | Gitee acquisition

Please correct me if there are any mistakes.

If you think it’s good, you can follow it. More data structures and algorithms will follow.

【 Recommended reading 】

【 Data structure 】 Figure out “stack” with detailed graphics (Principles)
Use diagrams and code to make sense of sequential structure linear tables
How to master C language a big weapon – pointer?
Rounding | finish the article I finally understand the list

mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.

Learning queues, just read this one!

1. What is a queue?

2. The implementation idea of queue

2.1. Array implementation – Sequential queue

2.2. Linked list implementation — Chain queue

3. Queue status

3.1. Sequential Queues (Problem edition)

3.2. False full queue

3.3. Circular queues

3.4. Chain queue

4. The initialization

4.1. Sequential queues

4.2. Chain queue

5. Join the team

5.1. Sequential queues

5.2. Chain queue

6. Out of line operation

6.1. Sequential queues

6.2. Chain queue

7. Traversal operations

7.1. Sequential queues

7.2. Chain queue

Learning queues, just read this one!

1. What is a queue?

2. The implementation idea of queue

2.1. Array implementation – Sequential queue

2.2. Linked list implementation — Chain queue

3. Queue status

3.1. Sequential Queues (Problem edition)

3.2. False full queue

3.3. Circular queues

3.4. Chain queue

4. The initialization

4.1. Sequential queues

4.2. Chain queue

5. Join the team

5.1. Sequential queues

5.2. Chain queue

6. Out of line operation

6.1. Sequential queues

6.2. Chain queue

7. Traversal operations

7.1. Sequential queues

7.2. Chain queue

Related Posts

Java | stack data structure and algorithm analysis

Talk about rocketmq RemotingTooMuchRequestException

SpringBoot + SpringCloud pit climbing tour