“This is the 12th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

Hello everyone, I’m Fdog. I come from a small city in Inner Mongolia. I’m currently studying in Taizhou. I am very grateful to have such a platform where I can share what I have learned and felt. I like programming, I like code, I like to be a programmer. Study hard, strive for many years later, to give their relatives a better life. QQ/WX: 2506897252 Welcome to exchange.

@[TOC]

1. Introduction

1. Sequential queue

1. A queue is a special type of linear table. It allows only delete operations at the front of the table and insert operations at the rear of the table. The end that inserts is called the end of the queue, and the end that deletes is called the head of the queue. A queue with no elements is called an empty queue. 2. The data elements of a queue are also called queue elements. Inserting a queue element into a queue is called enqueueing, and removing a queue element from a queue is called enqueueing. Because the queue can only be inserted at one end and deleted at the other end, only the earliest element can be deleted from the queue first, so the queue is also called FIFO – first in first out (FIFO – first in first out) linear table.

Similar to the sequential stack, the sequential storage structure of a queue uses a set of storage cells with consecutive addresses to store elements from the head of the queue to the end of the queue, such as a one-dimensional array.

Since the position of the head and tail of the queue changes in real time, two Pointers are needed to follow the head and tail queue at all times. When the queue is empty, the two Pointers, front, rear, point to one position. As data is enqueued, the position of the two Pointers is shown in Figure 1 and Figure 2.

Exit team as shown in Figure 3.

2. Loop queues

It can be seen that as the data is queued out, the space in front of the array is wasted like a static linked list and cannot be reused. Therefore, on the basis of the sequential queue, the sequential circular queue is used. For easy understanding, we connect the end of the array to form a ring, as shown in the figure below:

After the original head out of the queue, the original position can be used by the tail, avoiding memory waste. We are only looking at sequential loop queues, so let’s look at the code implementation.

2. Code implementation

1. Define a queue

#define MAXSIZE 50
typedef struct
{
 char elem[MAXSIZE];
 int front;
 int rear;
}SeqQueue;

Copy the code

2. Initialize the queue

void InitQueue(SeqQueue * Q)
{
 Q->front = Q->rear = 0;
}
Copy the code

3. The team

int EnterQueue(SeqQueue * Q, char x)
{
 if ((Q->rear + 1) % MAXSIZE == Q->front)
 // As you can see, this modulo method causes the last space to be wasted, so when rear equals 49 the queue is considered full. Another method is to increase the number of markers.
 {
  return(false);
 }
 Q->elem[Q->rear] = x;
 Q->rear = (Q->rear + 1) % MAXSIZE;
 return(true);
}
Copy the code

Now, some of you might ask why we do this algorithm, but let me tell you: The array defined above is 50 units, if the rear pointer points to 49, the data continues to queue, and when the rear pointer +1 changes to 49+1 equals 50, because the array index is 49 at most, then the array overflows, so instead of (Rear) 49 adding 1, you reset the rear to 0, To solve the problem, so do not take take membrane algorithm may be used, will be reset to zero, the length of the largest and several other and not get the final result of modulus is the same, just for the sake of convenience, again will take take membrane, 49 (+ 1) % = 0, this method can make the array maximum length automatic Angle under the standard reached 0, save more than we write step 0.

4. Out of the team

int DeleteQueue(SeqQueue * Q, char *x)
{
 if (Q->front == Q->rear)return(false);
 *x = Q->elem[Q->front];
 Q->front = (Q->front + 1) % MAXSIZE;
 return (true);
}
Copy the code

3. Dual-end queues

In addition to stacks and queues, another limiting data structure is a double-ended queue, which is a linear table that limits insert and delete operations to both ends of the table. These two ends are called endpoint 1 and endpoint 2. Or, like a stack, a rail transit network can be used as a metaphor for a two-ended queue. In practice, you can also have two-ended queues with output constraints (that is, one endpoint allows insert and delete, and the other endpoint only allows insert) and two-ended queues with input constraints (that is, one endpoint allows insert and delete, and the other endpoint only allows delete). If you limit a two-ended queue to insert elements from an endpoint that can only be deleted from that endpoint, then the two-ended queue decays into adjacent stacks. This dual-ended queue appears to be more flexible than stacks and queues, but is far less common in practice than stacks and queues and is not discussed.

If there are mistakes, welcome to criticize, welcome to discuss. Be sure that you have never had any regrets in your life which only lasts for a few decades. Laugh or cry as you like, and it’s meaningless to oppress yourself. = =