Data structure and algorithm (1) linear table implementation

Data structure and algorithm (2) unidirectional circular linked list creation insert delete implementation

Data structure and algorithm (3) Implementation of bidirectional linked list and bidirectional cyclic linked list

Data structures and algorithms (4) Linked list related interview questions

Data structures and algorithms (5) Stack and queue operation and implementation

Data structures and algorithms (6) The operation and implementation of queues

@[TOC]

1. Data structure and algorithm (6) Queue operation and implementation

The code download

This blog code download:

• Sequential storage operations for queues
• The chain storage operation of a queue

1.1 Introduction to Queues

A queue is a linear First In First Out table, or FIFO. Generally, the end of incoming data is called “queue tail” and the end of outgoing data is called “queue head”. The process of data elements entering the queue is called “queue in” and the process of data elements leaving the queue is called “queue out”.

Unlike the stack structure, both ends of the queue are “open”, requiring data to go in at one end and out at the other, as shown below:

If you are not familiar with the stack structure, please refer to my previous blog: “Data Structures and Algorithms (5) Stack and queue Operation and Implementation.”

Stack and queue do not confuse, stack structure is one end of the seal, is characterized by “advanced after out”; The two ends of the queue are full of openings, characterized by “first in, first out”.

Thus, a linear storage structure with data coming in and out of one end of a table and following a first-in, first-out rule is a queue.

The queue storage structure can be implemented in two ways:

1. Sequential queue: a queue structure implemented on the basis of a sequential table;
2. Linked queue: a queue structure implemented on the basis of linked lists; The difference between the two is only the difference between the sequential list and the linked list, that is, in the actual physical space, the queue for centralized storage is the sequential queue, and the queue for decentralized storage is the chain queue.

In real life, queue applications can be seen everywhere, such as queuing to buy XXX, hospital registration system, etc., all adopt queue structure.

Take the ticket line for example, all the people in a line, first to the front of the line, the last to wait at the end of the line, each person in the line must wait until all the people in front of them have bought tickets and exit the line, before it is their turn to buy tickets. Isn’t that a typical queue structure?

Now that you understand what queues are, let’s start with the basic implementation and considerations of sequential and chain queues.

1.2 Queue Sequential storage

Since the bottom layer of the sequential queue uses arrays, a large enough memory space must be allocated in advance to initialize the sequential queue. In addition, in order to meet the requirements of data entering from the end of the queue and leaving from the head and first in first out in the sequential queue, we need to define two Pointers (TOP and rear) to point to the head element and the tail element in the sequential queue respectively, as shown in the following figure:

top
rear
top
rear

So when we have a data element in the queue, what we do is we store it in the array that rear points to, and then rear+1; When the head element needs to be removed from the queue, only the top+1 operation is required.

Here’s an example:

If we were to implement {1,2,3,4} with sequential queue storage,

The process for element 1 is as follows:

Element 4 Team entry Process:

So what we’re going to do is take the elements 1,2,3,4 out of the team. The team exit process is as follows:

Element 4 team out:

Let’s look at a simple sequential queue operation code:

#include <stdio.h>

 int enQueue(int *a,int rear,int data){
	 a[rear]=data;
	 rear++;
	 return rear;
 }
void deQueue(int *a,int front,int rear){
// If front==rear, queue is empty
	while(front! =rear) {printf("Queue element: %d\n",a[front]); front++; }}int main(a) {
	int a[100];
	int front,rear;
	// Set the queue header pointer and the queue tail pointer. When there are no elements in the queue, the queue header and queue tail point to the same block address
	front=rear=0;
	/ / team
	rear=enQueue(a, rear, 1);
	rear=enQueue(a, rear, 2);
	rear=enQueue(a, rear, 3);
	rear=enQueue(a, rear, 4);
	/ / out of the team
	deQueue(a, front, rear);
	return 0;
 }

Copy the code

Output structure is as follows:

Out element: 1 out element: 2 out element: 3 out element: 4Copy the code

The above sequential storage queue has some problems, such as false overflow problem, as shown in the following figure:

• The array storage space before the sequential queue can no longer be used, resulting in space waste; That’s the false overflow.
• In addition, if the space applied for by the sequential table is not large enough, it directly causes the overflow of the array in the program, resulting in overflow errors;

In order to solve the above problem, we have a better solution, which is to use the circular queue to solve the false overflow problem.

Next, circular queues.

1.2.1 Circular queue

A circular queue is one in which the end pointer is moved to the end of the array, and the next time an element enters the queue, the end pointer can be moved back to the front of the array where there are no elements.

The loop queue operation is shown below:

(a) We use q.front == q.ear to indicate that the queue is empty. When we enter three elements a, B and C in sequence, as shown in the figure above (b). Next, we remove element A from the team head, as shown in figure (c). Then, we joined the queue d, E, F, and G in turn, when the queue was actually full, we found that q.front == q.ear, as shown in the figure above (d1). However, q.front == q.ear (a) indicates that the queue is empty, but when the queue is full, q.front == q.ear cannot distinguish whether the queue is empty or full. To solve this problem, we usually sacrifice one storage space. As shown in figure d2, we use q.fold = q.ear + 1 to mean full, which is to sacrifice one storage unit without storing data.

In the circular queue, we judge that the queue is empty and the queue is full under the following conditions:

1. Queue full:MaxSize (Q.r ear + 1) % = = Q.f ront
2. Queue empty:Q.rear==Q.front
3. The number of valid data in the queue:(Q.rear+maxSize-Q.front)%maxSize

1.2.2 cyclic queue code implementation

• The sequential storage structure of a circular queue

/* The sequential storage structure of the loop queue */
typedef struct KQueue
{
    KQueueElementType data[MAXSIZE];
    int front;        /* Header pointer */
    int rear;        /* The end pointer, if the queue is not empty, points to the next element at the end of the queue */
}KQueue;
Copy the code

1.2.2.1 initialization

//1. Initialize a queue
KStatus initQueue(KQueue *Q) {
    Q->front = Q->rear = 0;
    return OK;
}
Copy the code

1.2.2.2 Queue Clearing

//2. Clear the queue
KStatus clearQueue(KQueue *Q) {
    Q->front = Q->rear = 0;
    return OK;
}
Copy the code

1.2.2.3 Queue nulling

//3. Queue nullity
KStatus isEmpty(KQueue Q) {
    return Q.front == Q.rear ;
}
Copy the code

1.2.2.4 Whether the queue is full

// check whether the queue is full
KStatus isFull(KQueue Q) {
    return Q.front == (Q.rear + 1 ) % MAXSIZE;
}

Copy the code

1.2.2.5 Querying the Queue Length

//5. Query the queue length
int getLength(KQueue Q) {
    return (Q.rear - Q.front + MAXSIZE)%MAXSIZE;
}
Copy the code

1.2.2.6 Obtaining the Header element

//6. Get the header element
If the queue is not empty, use e to return the head element of Q, and return OK, otherwise return ERROR;
KStatus getHead(KQueue Q, KQueueElementType *e) {
    // Check whether the queue is empty
    if (isEmpty(Q)) {
        return ERROR;
    }
    // Fetch the element value
    *e = Q.data[Q.front];
    return OK;
}
Copy the code

1.2.2.7 team

/ / 7. Team
// If the queue is not full, insert element e as the last element of the new queue
KStatus enQueue(KQueue *Q, KQueueElementType e) {
    // Check whether the queue is full
    if (isFull(*Q)) {
        return ERROR;
    }
    // Assign the element e to the end of the queue
    Q->data[Q->rear] = e;
    
    // Move the rear pointer back one bit, or back to the array header
    Q->rear = (Q->rear + 1) % MAXSIZE;
    
    return OK;
}
Copy the code

1.2.2.8 out team

/ / 8. Out of the team
// If the queue is not empty, remove the element in the head of queue Q and return the value e
KStatus deQueue(KQueue *Q, KQueueElementType *e) {
    if (isEmpty(*Q)) return ERROR;
    // Take the element from the queue head and assign it to e
    *e = Q->data[Q->front];
    
    // Move the front pointer back one bit to remove the enemy element
    Q->front = (Q->front + 1) % MAXSIZE;
    
    return OK;
}
Copy the code

1.2.2.9 Traversing the Queue

//9. Traverse the queue
KStatus traverseQueue(KQueue Q) {
    int i = Q.front;
    while((i + Q.front) ! = Q.rear) {// Outputs elements from the top of the queue to the end of the queue. I indicates the number of elements that have been output
        //(i + Q.front) ! = q.ear means we are at the end of the line,
        // Since we can't change the front and rear points, we need a temporary variable to record the current position
        printf("%d ", Q.data[i]);
        i = (i + 1) % MAXSIZE;
    }
    printf("\n");
    
    return OK;
}

Copy the code

1.2.2.10 Unit tests

// unit tests
void test(a) {
    printf("Loop queue operation unit test \n");
    KStatus j;
    int i=0;
    KQueueElementType d;
    KQueue Q;
    initQueue(&Q);
    printf("Is the queue empty after initialization? %u(1: null 0: no)\n",isEmpty(Q));
    
    printf("Team: \ n");
    while (i < 10) {
        enQueue(&Q, i);
        i++;
    }
    traverseQueue(Q);
    printf("Queue length: %d\n",getLength(Q));
    printf("Is the queue empty now? %u(1: null 0: no)\n",isEmpty(Q));
    printf("The team: \ n");
   
   / / out of the team
    deQueue(&Q, &d);
    printf("Out of line elements :%d\n",d);
    traverseQueue(Q);

    // Get the team head
    j=getHead(Q,&d);
    if(j)
        printf("Now the header element is: %d\n",d);
    clearQueue(&Q);
    printf("Is the queue empty after emptying? %u(1: null 0: no)\n",isEmpty(Q));

}
Copy the code

1.2.2.11 Complete code

//
// main.c
// 010_Queue
//
// Created by bog on 2020/4/18
// Copyright © 2020 Apple. All rights reserved
//

#include <stdio.h>
#include "stdlib.h"
#include "math.h"
#include "time.h"

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 /* Initial allocation of storage space */

typedef int KStatus;
typedef int KQueueElementType; /* The KQueueElementType type depends on the actual situation; int */ is assumed here

/* The sequential storage structure of the loop queue */
typedef struct KQueue
{
    KQueueElementType data[MAXSIZE];
    int front;        /* Header pointer */
    int rear;        /* The end pointer, if the queue is not empty, points to the next element at the end of the queue */
}KQueue;

//1. Initialize a queue
KStatus initQueue(KQueue *Q) {
    Q->front = Q->rear = 0;
    return OK;
}

//2. Clear the queue
KStatus clearQueue(KQueue *Q) {
    Q->front = Q->rear = 0;
    return OK;
}

//3. Queue nullity
KStatus isEmpty(KQueue Q) {
    return Q.front == Q.rear ;
}

// check whether the queue is full
KStatus isFull(KQueue Q) {
    return Q.front == (Q.rear + 1 ) % MAXSIZE;
}

//5. Query the queue length
int getLength(KQueue Q) {
    return (Q.rear - Q.front + MAXSIZE)%MAXSIZE;
}

//6. Get the header element
If the queue is not empty, use e to return the head element of Q, and return OK, otherwise return ERROR;
KStatus getHead(KQueue Q, KQueueElementType *e) {
    // Check whether the queue is empty
    if (isEmpty(Q)) {
        return ERROR;
    }
    // Fetch the element value
    *e = Q.data[Q.front];
    return OK;
}

/ / 7. Team
// If the queue is not full, insert element e as the last element of the new queue
KStatus enQueue(KQueue *Q, KQueueElementType e) {
    // Check whether the queue is full
    if (isFull(*Q)) {
        return ERROR;
    }
    // Assign the element e to the end of the queue
    Q->data[Q->rear] = e;
    
    // Move the rear pointer back one bit, or back to the array header
    Q->rear = (Q->rear + 1) % MAXSIZE;
    
    return OK;
}

/ / 8. Out of the team
// If the queue is not empty, remove the element in the head of queue Q and return the value e
KStatus deQueue(KQueue *Q, KQueueElementType *e) {
    if (isEmpty(*Q)) return ERROR;
    // Take the element from the queue head and assign it to e
    *e = Q->data[Q->front];
    
    // Move the front pointer back one bit to remove the enemy element
    Q->front = (Q->front + 1) % MAXSIZE;
    
    return OK;
}

//9. Traverse the queue
KStatus traverseQueue(KQueue Q) {
    int i = Q.front;
    while((i + Q.front) ! = Q.rear) {// Outputs elements from the top of the queue to the end of the queue. I indicates the number of elements that have been output
        //(i + Q.front) ! = q.ear means we are at the end of the line,
        // Since we can't change the front and rear points, we need a temporary variable to record the current position
        printf("%d ", Q.data[i]);
        i = (i + 1) % MAXSIZE;
    }
    printf("\n");
    
    return OK;
}


// unit tests
void test(a) {
    printf("Loop queue operation unit test \n");
    KStatus j;
    int i=0;
    KQueueElementType d;
    KQueue Q;
    initQueue(&Q);
    printf("Is the queue empty after initialization? %u(1: null 0: no)\n",isEmpty(Q));
    
    printf("Team: \ n");
    while (i < 10) {
        enQueue(&Q, i);
        i++;
    }
    traverseQueue(Q);
    printf("Queue length: %d\n",getLength(Q));
    printf("Is the queue empty now? %u(1: null 0: no)\n",isEmpty(Q));
    printf("The team: \ n");
   
   / / out of the team
    deQueue(&Q, &d);
    printf("Out of line elements :%d\n",d);
    traverseQueue(Q);

    // Get the team head
    j=getHead(Q,&d);
    if(j)
        printf("Now the header element is: %d\n",d);
    clearQueue(&Q);
    printf("Is the queue empty after emptying? %u(1: null 0: no)\n",isEmpty(Q));

}

int main(int argc, const char * argv[]) {
    // insert code here...
    printf("Hello, World! \n");
    test();
    return 0;
}

Copy the code

• Unit test, output:

Hello, World! Was the queue empty after the loop queue operation unit test initialized it? 1(1: empty 0: no) Join: 0 1 2 3 4 5 6 7 8 9 Queue length: 10 Now the queue is empty No? 0(1: empty 0: no) Out queue: elements out of the queue :0 1 2 3 4 5 6 7 8 Now the first element in the queue is: 1 After the queue is cleared, is the queue empty? 1(1: empty 0: no) Program ended with exit code: 0Copy the code

1.3 Queue chain storage

The implementation idea of chained queue is similar to that of sequential queue. You only need to create two Pointers (named TOP and Rear) to point to the head element and the tail element of the queue in the linked list, as shown in Figure 1:

Figure 1 shows the initial state of the chained queue, where no data elements are stored in the queue, so both the TOP and rear Pointers point to the head node.

Now let’s take a look at chained queue entry and queue exit operations. Chained queue entry and queue exit operations are basically similar to single linked lists. If you are not familiar with linked lists, please refer to my previous linked list blog:

1. “Data Structures and Algorithms (I) Implementation of linear tables”
2. “Data Structures and Algorithms (II) Implementation of Single and Unidirectional Cyclic Lists”

Basically, to join is to insert an element at the end of the list, and to unjoin is to delete a node at the head of the list.

• Chain queue queuing operation: Figure 2 shows the chain queue queuing in sequence{1，2，3}Three elements:

As shown in the figure above, when a new data element is queued in a chain queue, only the following 3 steps are required:

1. Wrap the data element with a node, such as elem.
2. Establish a logical relationship with the node to which the rear pointer points, that is, rear->next=elem;
3. Finally, move the REAR pointer to the new node, rear=elem;

• Chain queue dequeuing operation: When data elements in the chain queue need to be dequeued, according to the principle of “first in, first out”, only the node that stores the data and the element nodes that have joined the queue before it need to be dequeued according to the principle. The queuing process is the process of removing the first node from the list head in turn, now we need to add the1, 2,The operation process of the two elements is shown in Figure 3 below:

As shown in Figure 3, we can know that the following three steps are needed to exit the queue of the head element in the chain queue:

1. Find the queue head node directly through the top pointer, and create a new pointer P to point to the node that is about to exit the queue.
2. Remove the p node (the head node of the queue to exit) from the linked list;
3. Release node P and reclaim its occupied memory space;

1.3.2 queue chain storage code implementation

• Structure definition of chain queue

// Node structure
typedef struct KQueueNode{
    KQueueElementType data;
    struct KQueueNode *next;
}KQNode, *KQueuePtr;

// The list structure of queues
typedef struct KLinkQueue {
    KQueuePtr front; / / team head
    KQueuePtr rear;  / / of the
}KLQueue;
Copy the code

1.3.2.1 initialization

// 1. Initialize the queue
KStatus initQueue(KLQueue *Q) {
    //1. Both the queue head pointer and the queue tail pointer need only the newly generated node
    Q->front = Q->rear = (KQueuePtr)malloc(sizeof(KQNode));
    //2. Check whether the node is successfully created
    if(! Q->front)return ERROR;
    //3. The queue header pointer field is null
    Q->front->next = NULL;
    
    return OK;
}
Copy the code

1.3.2.2 Destroying queues

// 2. Destroy the queue
KStatus destoryQueue(KLQueue *Q) {
    // Walk through the queue and destroy every node
    while (Q->front) {
        Q->rear = Q->front->next;
        free(Q->front);
        Q->front = Q->rear;
    }
    return OK;
}
Copy the code

Clearing queues

// 3. Clear the queue
KStatus clearQueue(KLQueue *Q) {
    KQueuePtr p,q;
    Q->rear = Q->front;
    p = Q->front->next;
    Q->front->next = NULL;
    while (p) {
        q = p->next;
        p = p->next;
        free(q);
    }
    return OK;
}
Copy the code

1.3.2.4 Queue nullity

// 4. Queue nullity
KStatus isEmpty(KLQueue Q) {
    return Q.front == Q.rear;
}
Copy the code

1.3.2.5 Get the enemy element

// 6. Get the correct element
KStatus getHead(KLQueue Q, KQueueElementType *e){
    if(Q.front ! = Q.rear) {// Return the value of the header element, unchanged
        *e = Q.front->next->data;
        return TRUE;
    }
    
    return FALSE;
}
Copy the code

1.3.2.6 Obtaining the Queue Length

// 7. Get the queue length
int getLength(KLQueue Q){
    int count = 0;
    KQueuePtr p = Q.front;
    while(Q.rear ! = p) { count++; p = p->next; }return count;
}
Copy the code

1.3.2.7 team

/ / 8. Team
KStatus enQueue(KLQueue *Q, KQueueElementType e) {
    // Allocate node space to join elements with pointer s;
    KQueuePtr s = (KQueuePtr)malloc(sizeof(KQNode));
    if(! s)return ERROR;
    // set the new node s to the data field
    s->data = e;
    s->next = NULL;
    
    // Insert the new node at the end of the queue
    Q->rear->next = s;
    // Change the queue pointer
    Q->rear = s;
    
    return OK;
}
Copy the code

1.3.2.8 out team

/ / 9. Out of the team
KStatus deQueue(KLQueue *Q, KQueueElementType *e) {
    KQueuePtr p;
    // Check whether the queue is empty
    if (isEmpty(*Q)) return ERROR;
    
    // The queue header to be deleted is temporarily stored in p
    p = Q->front->next;
    // Assign the value of the queue header to be deleted to e
    *e = p->data;
    // Assign p->next to the successor of the original queue header
    Q->front->next = p->next;
    
    // If the team head is the team tail, remove rear to the head node.
    if(Q->rear == p) Q->rear = Q->front;
    
    // Release the node
    free(p);
    
    return OK;
}
Copy the code

1.3.2.9 Traversing the Queue

// 10. Traverse the queue
KStatus traverseQueue(KLQueue Q) {
    KQueuePtr p = Q.front->next;
    while (p) {
        printf("%d ",p->data);
        p = p->next;
    }
    printf("\n");
    
    return OK;
}
Copy the code

1.3.2.10 Unit Tests

// unit tests
void test(a) {
    printf("Chain queue representation and operation! \n");
    
    KStatus iStatus;
    KQueueElementType d;
    KLQueue q;
    
    //1. Initialize queue Q
    iStatus = initQueue(&q);
    
    //2. Check whether the vm is successfully created
    if (iStatus) {
        printf("Successfully constructed an empty queue \n");
    }
    
    //3. Check whether the queue is empty
    printf("Is the queue empty? %d (1: yes 0: no)\n",isEmpty(q));
    
    //4. Get the queue length
    printf("Queue length is %d\n",getLength(q));
    
    //5. Insert the element into the queue
    enQueue(&q, - 3);
    enQueue(&q, 6);
    enQueue(&q, 12);
    
    printf("Queue length is %d\n",getLength(q));
    printf("Is the queue empty? %d (1: yes 0: no)\n",isEmpty(q));
    
    //6. Traverse the queue
    printf("The elements in the queue are as follows :\n");
    traverseQueue(q);

    //7. Get the queue header element
    iStatus = getHead(q, &d);
    if (iStatus == OK) {
        printf("The header element is :%d\n",d);
    }
    
    // delete the header element
    iStatus = deQueue(&q, &d);
    if (iStatus == OK) {
        printf("Deleted header element is :%d\n",d);
    }
    
    //9. Get the header element
    iStatus = getHead(q, &d);
    if (iStatus == OK) {
        printf("New header element is :%d\n",d);
    }
    
    // clear the queue
    clearQueue(&q);
    
    //11. Destroy queues
    destoryQueue(&q);
}
Copy the code

• Unit test, output:

Hello, World! Chain queue representation and operation! Is an empty queue successfully constructed? 1 (1: yes 0: no) The queue length is 0. The queue length is 3. Is the queue empty? 0 (1: yes 0: no) The elements in the queue are as follows :-3 6 12 The header elements are :-3 The deleted header elements are :-3 The new header elements are :6 Program ended with exit code: 0Copy the code

1.3.2.11 Complete code

//
// main.c
// 011_LinkQueue
//
// Created by bog on 2020/4/18
// Copyright © 2020 Apple. All rights reserved
//

/* The basic operation of the chain queue is implemented */

#include <stdio.h>
#include "stdlib.h"
#include "math.h"
#include "time.h"

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20

typedef int KStatus;
typedef int KQueueElementType;

// Node structure
typedef struct KQueueNode{
    KQueueElementType data;
    struct KQueueNode *next;
}KQNode, *KQueuePtr;

// The list structure of queues
typedef struct KLinkQueue {
    KQueuePtr front; / / team head
    KQueuePtr rear;  / / of the
}KLQueue;

// 1. Initialize the queue
KStatus initQueue(KLQueue *Q) {
    //1. Both the queue head pointer and the queue tail pointer need only the newly generated node
    Q->front = Q->rear = (KQueuePtr)malloc(sizeof(KQNode));
    //2. Check whether the node is successfully created
    if(! Q->front)return ERROR;
    //3. The queue header pointer field is null
    Q->front->next = NULL;
    
    return OK;
}

// 2. Destroy the queue
KStatus destoryQueue(KLQueue *Q) {
    // Walk through the queue and destroy every node
    while (Q->front) {
        Q->rear = Q->front->next;
        free(Q->front);
        Q->front = Q->rear;
    }
    return OK;
}

// 3. Clear the queue
KStatus clearQueue(KLQueue *Q) {
    KQueuePtr p,q;
    Q->rear = Q->front;
    p = Q->front->next;
    Q->front->next = NULL;
    while (p) {
        q = p->next;
        p = p->next;
        free(q);
    }
    return OK;
}

// 4. Queue nullity
KStatus isEmpty(KLQueue Q) {
    return Q.front == Q.rear;
}


// 6. Get the correct element
KStatus getHead(KLQueue Q, KQueueElementType *e){
    if(Q.front ! = Q.rear) {// Return the value of the header element, unchanged
        *e = Q.front->next->data;
        return TRUE;
    }
    
    return FALSE;
}

// 7. Get the queue length
int getLength(KLQueue Q){
    int count = 0;
    KQueuePtr p = Q.front;
    while(Q.rear ! = p) { count++; p = p->next; }return count;
}


/ / 8. Team
KStatus enQueue(KLQueue *Q, KQueueElementType e) {
    // Allocate node space to join elements with pointer s;
    KQueuePtr s = (KQueuePtr)malloc(sizeof(KQNode));
    if(! s)return ERROR;
    // set the new node s to the data field
    s->data = e;
    s->next = NULL;
    
    // Insert the new node at the end of the queue
    Q->rear->next = s;
    // Change the queue pointer
    Q->rear = s;
    
    return OK;
}

/ / 9. Out of the team
KStatus deQueue(KLQueue *Q, KQueueElementType *e) {
    KQueuePtr p;
    // Check whether the queue is empty
    if (isEmpty(*Q)) return ERROR;
    
    // The queue header to be deleted is temporarily stored in p
    p = Q->front->next;
    // Assign the value of the queue header to be deleted to e
    *e = p->data;
    // Assign p->next to the successor of the original queue header
    Q->front->next = p->next;
    
    // If the team head is the team tail, remove rear to the head node.
    if(Q->rear == p) Q->rear = Q->front;
    
    // Release the node
    free(p);
    
    return OK;
}


// 10. Traverse the queue
KStatus traverseQueue(KLQueue Q) {
    KQueuePtr p = Q.front->next;
    while (p) {
        printf("%d ",p->data);
        p = p->next;
    }
    printf("\n");
    
    return OK;
}

// unit tests
void test(a) {
    printf("Chain queue representation and operation! \n");
    
    KStatus iStatus;
    KQueueElementType d;
    KLQueue q;
    
    //1. Initialize queue Q
    iStatus = initQueue(&q);
    
    //2. Check whether the vm is successfully created
    if (iStatus) {
        printf("Successfully constructed an empty queue \n");
    }
    
    //3. Check whether the queue is empty
    printf("Is the queue empty? %d (1: yes 0: no)\n",isEmpty(q));
    
    //4. Get the queue length
    printf("Queue length is %d\n",getLength(q));
    
    //5. Insert the element into the queue
    enQueue(&q, - 3);
    enQueue(&q, 6);
    enQueue(&q, 12);
    
    printf("Queue length is %d\n",getLength(q));
    printf("Is the queue empty? %d (1: yes 0: no)\n",isEmpty(q));
    
    //6. Traverse the queue
    printf("The elements in the queue are as follows :\n");
    traverseQueue(q);

    //7. Get the queue header element
    iStatus = getHead(q, &d);
    if (iStatus == OK) {
        printf("The header element is :%d\n",d);
    }
    
    // delete the header element
    iStatus = deQueue(&q, &d);
    if (iStatus == OK) {
        printf("Deleted header element is :%d\n",d);
    }
    
    //9. Get the header element
    iStatus = getHead(q, &d);
    if (iStatus == OK) {
        printf("New header element is :%d\n",d);
    }
    
    // clear the queue
    clearQueue(&q);
    
    //11. Destroy queues
    destoryQueue(&q);
}

int main(int argc, const char * argv[]) {
    // insert code here...
    printf("Hello, World! \n");
    test();
    return 0;
}

Copy the code