1. Basic concepts of queues

Like the stack, a queue is also a special linear table. The data elements of a queue and the logical relationship between data elements are exactly the same as that of a linear table. The difference is that a linear table allows insertion and deletion of data elements at any position, while a queue only allows insertion at one end and deletion at the other end.The end of the queue that allows insertion is called the end of the queue, and the end of the queue that allows deletion is called the head. Those indicating the team head are called the team head indicator or pointer, and those indicating the team tail are called the team tail indicator or pointer. The operation of inserting a queue is called enqueuing and the operation of deleting a queue is called dequeuing. According to the definition of the queue, the data element that enters the queue is placed after the original data element at the end of the queue, and each data element that exits the queue is the original data element at the head of the queue, so that the data element that enters the queue first always exits the queue first, so the queue is one kind ofFirst in first outThe structure of the. A diagram of the queue is shown below.

The abstract data type of the queue

2.1 Data Set

Queue data set that can be expressed as a1, a2, ⋅ ⋅ ⋅, the an – 1 a_1 and a_2,…, a_ {}, n – 1 a1, a2, ⋅ ⋅ ⋅, the an – 1, the data type of each data element as the DataType.

2.2 Operation Set

  • Initialize the queue: QueueInitiate(Q)
  • QueueNotEmpty(Q) : Checks whether queue Q is empty. If it is empty, the function returns 0, otherwise returns 1.
  • QueueAppend(Q,x) : Inserts data element X at the end of queue Q.
  • QueueDelete(Q,x) : Removes the header data element of queue Q and returns it with parameter X, returning 1 if the queue is removed successfully and 0 otherwise.
  • QueueGet(Q,x) : Fetches QueueGet(Q,x) : Fetches QueueGet(Q,x) : fetches QueueGet(Q,x) : fetches QueueGet(Q,x) : fetches QueueGet(Q,x), returns 1 if it succeeds, 0 otherwise.

3. Sequential queue

3.1 Structure of sequential queues

Queues represented by sequential storage structures are called sequential queues. The structure of the sequential queue is shown below:

3.2 False overflow of sequential queues

Assume that the maximum storage capacity of A sequential queue is 6, that is, MaxQueueSize=6, and the operations on queue A, B, C, queue A, B, queue D, and queue E are as follows:

If the enqueue operation of F and G is performed at this time, the sequential queue will “overflow” when the data element G is enqueued because the tail pointer crosses the lower boundary of the array. Its status is shown in the figure below:

In this case, the “overflow” is caused by the value of rear pointer exceeding the maximum storage space defined by the sequential queue. However, there are two storage Spaces in the queue at this time, so the “overflow” is not caused by insufficient storage space.An overflow in a sequential queue that has enough storage space but cannot be queued is called a false overflow. Relative to false overflow, oneTrue overflow occurs when the maximum storage space defined by a sequential queue is full and an enqueue operation is required. It is obvious that there is no way to solve the false overflow problem of the sequential queue, and the true overflow problem makes the sequential queue appear useless in the actual development application, so the sequential list is not common in the actual development.

4. Sequential loop queues

4.1. Basic principles of sequential loop queues

False overflow occurs because the values of rear and front cannot be automatically converted from the maximum value of the defined storage space to the minimum value of the defined storage space. Therefore, the solution is to construct the storage space used by the sequential queue into a circular queue that is logically connected end to end. When rear and front reach maxQueuesize-1, the next position forward automatically goes to 0. In this way, there is no false overflow problem where the head of the sequential queue data is empty but the tail pointer of the queue overflows because the data subscript is out of bounds.

4.2. Judgement of queue empty and queue full in sequential circular queue

Sequential loop queues have the problem that the queue empty state and queue full state are the same and cannot be distinguished. If MaxQueueSize=8, front=0, rear=0, front==rear, front==rear, when data elements A, B, C, D, E, F, G, and H are in the queue, the queue is full, front=0, Rear =0, front==rear; When data elements A, B, C, D, E, F, G, and H exit from the queue, the queue is empty in sequence. In this case, front=0 and rear=0 are front and =rear. Obviously in a sequential loop queue we have front==rear whether the queue is full or empty, so programmatically we can’t distinguish between empty and full.

There are usually three methods to solve the problem of queue full and queue empty state judgment of sequential circular queues:

  1. Use one less storage unit. If one less storage space is used, the queue is full when rear+1 equals front, that is, (Rear +1)%MaxQueueSize == front. The empty queue condition is still rear==front.
  2. Sets a flag bit. Set the tag bit (tag=0) to rear==front && tag==0. Set the tag bit (tag=0) to rear==front && tag==0. If the queue is full, rear==front && tag==1.
  3. Set up a counter. Set a counter count (count=0), increment (count= 1) and decrement (count== 1) for each successful dequeue operation. If the queue is full, rear==front && count>0 or count==MaxQueueSize.

Obviously, setting a counter is the simplest and most optimized way to determine whether the queue is empty or full.

4.3 Implementation of sequential loop queue

According to the above analysis of the sequential loop queue, the structure of the sequential loop queue that uses the counter method to solve the problem of judging the empty and full queue states is defined as follows:

typedef struct {
    DataType queue[MaxQueueSize];
    int front;// queue head pointer
    int rear;// end of queue pointer
    int count;/ / counter
} SeqQueue;
Copy the code

4.3.1 Initialize QueueInitiate(SeqQueue *queue)

void QueueInitiate(SeqQueue *queue) {
    queue->rear = 0;// Initialize the bottom pointer value of the queue
    queue->front = 0;// Initializes the header pointer subscript value
    queue->count = 0;// Initialize the counter
}
Copy the code

4.3.2 QueueNotEmpty(SeqQueue queue)

Checks whether the queue is empty, returns 1 if not, or 0 otherwise

int QueueNotEmpty(SeqQueue queue) {
    if (queue.count ! =0) {
        return 1;
    }
    return 0;
}
Copy the code

QueueAppend(SeqQueue *queue, DataType x)

Insert the data element X to the end of the sequential loop queue, returning 1 on success and 0 on failure

int QueueAppend(SeqQueue *queue, DataType x) {
    if (queue->count > 0 && queue->rear == queue->front) {
        printf("Queue full, unable to insert data");
        return 0;
    }
    queue->queue[queue->rear] = x;
    queue->rear = (queue->rear + 1) % MaxQueueSize;
    queue->count++;
    return 1;
}
Copy the code

Queue (SeqQueue *queue, DataType *x)

Removes the enemy element of the sequential loop queue and assigns it to x, returning 1 on success, 0 otherwise

int QueueDelete(SeqQueue *queue, DataType *x) {
    if (queue->count == 0) {
        printf(Queue empty);
        return 0;
    }
    *x = queue->queue[queue->front];
    queue->front = (queue->front + 1) % MaxQueueSize;
    queue->count--;
    return 1;
}
Copy the code

QueueGet(SeqQueue queue, DataType *x)

Assign the current queue header data element of the sequential loop queue to X, returning 1 on success, 0 otherwise

int QueueGet(SeqQueue queue, DataType *x) {
    if (queue.count == 0) {
        printf(Queue empty);
        return 0;
    } else {
        *x = queue.queue[queue.front];
        return 1; }}Copy the code

We can see from the above code that there are no loop statements in any operation code of the sequential loop queue, so the time complexity of all operations of the sequential loop queue is O(1).

5. Chain queues

A queue with a chain storage structure is called a chain queue.

5.1 Storage structure of chain queue

The head pointer of a chain queue is at the current head node of the queue, and the tail pointer is at the current tail node of the queue. For a chain queue without a head node, the node indicated by the queue head pointer can be directly deleted when the queue exits, so it is more convenient when the chain queue has no head node. An unheaded node queue has data elements
a 0 . a 1 . ⋅ ⋅ ⋅ . a n – 1 A_0 a_1,…, a_ {}, n – 1 The structure of the chain queue is shown below. Front indicates the head of a chain queue, rear indicates the tail of a chain queue.

The structure of nodes in a chain queue can be defined as follows:

typedef struct qnode {
    DataType data;
    struct qnode *next;
} LQNode;
Copy the code

To facilitate the call of parameters, the front and rear Pointers of the chain queue are also defined as the following structures:

typedef struct {
    LQNode *front;
    LQNode *rear;
} LQueue;
Copy the code

5.2 Implementation of chain queue operation

5.2.1 Initializing QueueInitiate(LQueue *queue)

void QueueInitiate(LQueue *queue) {
    queue->front = NULL;
    queue->rear = NULL;
}
Copy the code

5.2.2 QueueNotEmpty(LQueue queue)

Check whether the chain queue is empty, return 1 if it is not empty, return 0 otherwise

int QueueNotEmpty(LQueue queue) {
    if (queue.front == NULL) {
        return 0;
    }
    return 1;
}
Copy the code

QueueAppend(LQueue *queue, DataType x)

Insert the data element x at the end of the chained queue. Note here that if the queue was originally empty, change the queue header pointer. If the queue was originally non-empty, add a new node at the end of the queue.

void QueueAppend(LQueue *queue, DataType x) {
    LQNode *node = (LQNode *) malloc(sizeof(LQNode));
    node->data = x;
    node->next = NULL;
    if (queue->rear ! =NULL) {// Add a new node to the end of the queue
        queue->rear->next = node;
    }
    queue->rear = node;
    if (queue->front == NULL) {
        queue->front = node;// Change the queue header pointer when the queue was empty}}Copy the code

QueueDelete(LQueue *queue, DataType *x)

Removes the current queue header data element and returns the value by parameter X, returning 1 on success or 0 otherwise. Note that if the last node is deleted, the end pointer should be set to null.

int QueueDelete(LQueue *queue, DataType *x) {
    if (queue->front == NULL) {
        printf("Queue empty no data element out of queue");
        return 0;
    }
    LQNode *node = queue->front;
    *x = queue->front->data;
    queue->front = queue->front->next;// The queue node is disconnected
    if (queue->front == NULL) {
        queue->rear = NULL;// When deleting the last node, the end pointer should be null
    }
    free(node);
    return 1;
}
Copy the code

QueueGet(LQueue queue, DataType *x)

Gets the current queue header data element and returns the value by parameter X, returning 1 on success or 0 otherwise.

int QueueGet(LQueue queue, DataType *x) {
    if (queue.front == NULL) {
        printf("Queue empty no data element out of queue");
        return 0;
    } else {
        *x = queue.front->data;
        return 1; }}Copy the code

5.2.6 Destory(LQueue queue)

void Destory(LQueue queue) {
    LQNode *node = queue.front;
    LQNode *node1;
    while(node ! =NULL) {
        node1 = node;
        node = node->next;
        free(node1); }}Copy the code

It can be seen from the operation code implementation of the chain queue above that the time complexity of the chain queue is O(n) except the cancellation of the dynamic space application function, and the time complexity of other operations is O(1).