Shulou(Shulou.com)06/01 Report--

This article will explain in detail the example analysis of the queue in C language. The editor thinks it is very practical, so I share it for you as a reference. I hope you can get something after reading this article.

1. The concept of Queue 0x00 queue

? Concept:

① queues only allow special linear tables that insert data on one end and delete data on the other.

② is queued, and the end of the insertion operation is called the end of the queue. Out of the queue, the end of the deletion operation is called the queue head.

Elements in the ③ queue follow the first-in-first-out principle, that is, the FIFO principle (First In First Out)

The structure of 0x01 queues

? Structure:

Second, the definition of 0x00 chain queue typedef int QueueDataType; / / queue type typedef struct QueueNode {struct QueueNode* next; / / points to the next node QueueDataType data; / / data} QueueNode; typedef struct Queue {QueueNode* pHead; / / header pointer QueueNode* pTail; / / tail pointer} Queue

Why doesn't ❓ use single linked lists?

? In a single linked list, we only define a pointer to the head, not a tail pointer. Because defining the tail pointer does not solve the problem, such as tail insertion and deletion. So we don't need to define a structure to seal them together. Here we define a head pointer head and a tail pointer tail, these two pointers are meaningful. Because according to the nature of the queue, we will only insert at the end of the queue, not delete it at the end of the queue. So the value of this tail pointer is perfectly reflected, and the actual definition of several pointers depends on your needs.

0x02 interface function

? This requires the implementation of several interface functions:

Void QueueInit (Queue* pQ); / / queue initialization void QueueDestroy (Queue* pQ); / / destroy queue bool QueueIsEmpty (Queue* pQ); / / determine whether the queue is empty void QueuePush (Queue* pQ, QueueDataType x); / / join void QueuePop (Queue* pQ); / / dequeue QueueDataType QueueFront (Queue* pQ) / / return the data at the head of the queue QueueDataType QueueBack (Queue* pQ); / / return the data at the end of the queue int QueueSize (Queue* pQ); / / find the size of the queue. 3. 0x00 queue initialization (QueueInit)

? Queue.h

# pragma once#include # include typedef int QueueDataType; / / queue type typedef struct QueueNode {struct QueueNode* next; / / points to the next node QueueDataType data; / / data} QueueNode; typedef struct Queue {QueueNode* pHead; / / header pointer QueueNode* pTail; / / tail pointer} Queue; void QueueInit (Queue* pQ); / / queue initialization

? Queue.c

/ * queue initialization: set the header and tail pointer to NULL * / void QueueInit (Queue* pQ) {assert (pQ); / / prevent the incoming pQ from being null pQ- > pHead = pQ- > pTail = NULL; / / empty the header and tail pointer}

? Parsing: first use assertions to prevent the incoming pQ from being empty. Initialization only needs to set the head pointer and tail pointer to null.

0x01 destroy queue (QueueDestroy) / * destroy queue: free removes all queue elements and leaves the head and tail empty * / void QueueDestroy (Queue* pQ) {assert (pQ); / / prevents the incoming pQ from being empty QueueNode* cur = pQ- > pHead / / create traversal pointer cur while (cur! = NULL) {/ / cur enter the loop QueueNode* curNext = cur- > next; / / beacon pointer curNext if it is not empty to prevent the next node free (cur) cannot be found after releasing cur; / / release the node cur = curNext that cur is currently pointing to / / move the pointer cur} pQ- > pHead = pQ- > pTail = NULL; / / empty the dry field pointer}

? Interpretation:

① first asserts to prevent incoming pQ from being empty.

② destroy to release all nodes, we create a traversal pointer cur to traverse the entire queue. Since we want to release the node pointed to by cur, in order to prevent it from being unable to move because the next node cannot be found after releasing cur, we create a beacon-like pointer curNext here to record the next node of cur, and then free cur, so that we can move cur.

Finally, in order to prevent wild pointers, ③ also needs to set both the head pointer and tail pointer to null.

0x02 determines whether the queue is empty (HeapIsEmpty)

? Queue.h

Bool QueueIsEmpty (Queue* pQ); / / determine whether the queue is empty

? Interpretation: Boolean value, return true or false

? Queue.c

/ * determine whether the queue is empty * / bool QueueIsEmpty (Queue* pQ) {assert (pQ); / / prevent the incoming pQ from being empty return pQ- > pHead = = NULL; / / True if it is true, False if not

? Interpretation:

① first asserts to prevent incoming pQ from being empty.

② determines whether the queue is empty or not and can return it directly, cleverly taking advantage of Boolean features. True if pQ- > pHead = = NULL is established, false if true; is not valid, and false is returned.

0x03 enrollment (QueuePush)

? Queue.h

Void QueuePush (Queue* pQ, QueueDataType x); / / join the team

? Queue.c

/ * join the team: enter the data at the end of the team and output the data at the end of the team. If you are the first to join the queue, you should be both head and tail * / void QueuePush (Queue* pQ, QueueDataType x) {assert (pQ); / / prevent the incoming pQ from being empty / * create a new node: create a space of QueueNode size * / QueueNode* new_node = (QueueNode*) malloc (sizeof (QueueNode)) / * check malloc * / if (new_node = = NULL) {printf ("malloc failed!\ n"); exit (- 1);} / * place * / new_node- > data = x; / / data to be inserted new_node- > next = NULL / / default is empty / * join the queue: * [ideas] * case 1: queue is empty: both head and tail * [new_node] * ↑ ↑ * pHead pTail * * case 2: queue is not empty: data at the end of the queue * [ ]-> []-> [new_node] * pHead pTail pTail- > next * ↓ ↑ *-→ pTail (update tail pointer) * / if (pQ -> pHead = = NULL) {/ / case 1: queue is empty pQ- > pHead = pQ- > pTail = new_node / / both head and tail} else {/ / case 2: queue is not empty pQ- > pTail- > next = new_node; / / place new_node pQ- > pTail = new_node; / / Update pTail on the last node of the existing tail to make it point to the new tail}}

? Interpretation:

① first asserts to prevent incoming pQ from being empty.

②, we need to create a new node first. Through malloc dynamic memory to open up a piece of QueueNode-sized space, we have all learned here, we must have formed a good habit of checking malloc, right? Finally, to place the data, the data x to be inserted will be left empty by default to data,next, which is the same as the previous linked list, which will not be overstated here.

After the new ③ node is created, we can start writing to the queue. First of all, it is necessary to understand the nature of the queue: the end of the queue enters the data, and the head of the queue gives the data. Since you are joining the team here, you have to insert it at the back of the tail. Here we also consider that if the queue is empty, we will deliver both the header pointer and the tail pointer to new_node. In order to sort out our thoughts, we can draw a sketch of our ideas to help us better understand:

With this diagram, we can clearly achieve:

If (pQ- > pHead = = NULL) {/ / case 1: queue is empty pQ- > pHead = pQ- > pTail = new_node; / / both head and tail} else {/ / case 2: queue is not empty pQ- > pTail- > next = new_node / / place new_node pQ- > pTail = new_node; / / update pTail on the last node of the existing tail so that it points to the new tail}

When the queue is null, both the head pointer and the tail pointer point to new_node, when the queue is not empty, a node below the tail places the new_node, and then updates the tail pointer to point to the new tail (the location of the new_node).

0x04 out (QueuePop)

? Queue.h

Void QueuePop (Queue* pQ) / / out of the team

? Queue.c

/ * out of the queue: enter the data at the end of the queue, head-to-head data * / void QueuePop (Queue* pQ) {assert (pQ); / / prevent the incoming pQ from being empty assert (! QueueIsEmpty (pQ)) / / prevent the team from being listed as empty / * depart: * [idea Sketch] * [free]-> []-> [] * pHead headNext * ↓ ↑ *-→ pHead (update header pointer) * / QueueNode* headNext = pQ- > pHead- > next / / beacon pointer HeadNext free (pQ- > pHead); pQ- > pHead = headNext; / / update header / * if all the members of the team are deleted, not dealing with pTail will lead to the hidden danger of wild pointer * [idea sketch] * memory that NULL has been dropped by free! * ↑ ↑ (wild pointer warning) * pHead (because HeadNext is NULL) pTail * / if (pQ- > pHead = = NULL) / / if pHead is empty pQ- > pTail = NULL; / / process the tail pointer and set the tail pointer to null}

? Interpretation:

① first asserts to prevent the incoming pQ from being empty. Here, the queue is empty. If the queue is listed as empty and the queue is required to dequeue, there will be a problem, so here we should assert that the QueueIsEmpty is false.

The sketch of the ② idea is as follows:

The data needs to be released, and like destruction, a beacon-like pointer is used to record the next node of the pHead, and then we can boldly release the pHead without having to worry about not finding it. After the free is dropped, update the header so that the header pointer points to headNext.

? Note: one more thing to consider here: if the team is deleted, pHead goes back and points to empty, but pTail still points to the space that has been dropped by free. PTail is a typical wild pointer.

We don't have to worry about pHead, because if there is no data later, it will naturally point to NULL, but we have to focus on pTail here! We need to deal with it manually:

If pHead is empty, we can leave pTail empty as well.

If (pQ- > pHead = = NULL) / / if pHead is empty pQ- > pTail = NULL; / / process the tail pointer and leave the tail pointer empty 0x05 to return the line head data (QueueFront)

? Queue.h

QueueDataType QueueFront (Queue* pQ); / / return the data at the head of the line

? Queue.c

/ * return queue header data * / QueueDataType QueueFront (Queue* pQ) {assert (pQ); / / prevent incoming pQ from being empty assert (! QueueIsEmpty (pQ)); / / prevent queue column from being empty return pQ- > pHead- > data;}

? Interpretation:

① first asserts that the incoming pQ is null, but here we still assert that the QueueIsEmpty is false, because if there is no data in the team, a hammer data is returned.

② here directly return to the data, very simple, there is nothing to talk about.

0x06 returns end-of-queue data (QueueBack)

? Queue.h

QueueDataType QueueBack (Queue* pQ); / / returns the data at the end of the queue

? Queue.c

/ * return data at the end of the queue * / QueueDataType QueueBack (Queue* pQ) {assert (pQ); / / prevent the incoming pQ from being empty assert (! QueueIsEmpty (pQ)); / / prevent the queue from being listed as empty return pQ- > pTail- > data;}

? Interpretation:

① first asserts that the incoming pQ is empty and asserts that QueueIsEmpty is false.

②, you can return the data at the end of the queue directly here.

0x07 calculates the queue size (QueueSize)

? Queue.h

Int QueueSize (Queue* pQ); / / calculate the queue size

? Queue.c

/ * calculate the queue size: counter method * / int QueueSize (Queue* pQ) {assert (pQ); / / prevent incoming pQ from being null int count = 0; / / counter QueueNode* cur = pQ- > pHead; / / create traversal pointer cur while (cur! = NULL) {+ + count; / / count + 1 cur = cur- > next / / move the pointer cur} return count;}

? Interpretation: here we use the counter method to find the size, one call is O (N), there is nothing wrong with it.

① first asserts to prevent incoming pQ from being empty.

② creates a counter variable and traverses the pointer cur, traverses the entire queue and counts it, and finally returns the result of the count.

0x08 complete code

? Queue.h

# pragma once#include # include typedef int QueueDataType; / / queue type typedef struct QueueNode {struct QueueNode* next; / / points to the next node QueueDataType data; / / data} QueueNode; typedef struct Queue {QueueNode* pHead; / / header pointer QueueNode* pTail; / / tail pointer} Queue; void QueueInit (Queue* pQ); / / queue initialization void QueueDestroy (Queue* pQ) / / destroy queue bool QueueIsEmpty (Queue* pQ); / / determine whether the queue is empty void QueuePush (Queue* pQ, QueueDataType x); / / join queue void QueuePop (Queue* pQ); / / dequeue QueueDataType QueueFront (Queue* pQ); / / return queue head data QueueDataType QueueBack (Queue* pQ); / / return queue end data int QueueSize (Queue* pQ) / / calculate the queue size

? Queue.c

# include / * queue initialization: set the header and tail pointer to NULL * / void QueueInit (Queue* pQ) {assert (pQ); / / prevent the incoming pQ from being null pQ- > pHead = pQ- > pTail = NULL; / / leave the header and tail pointer empty} / * destroy the queue: free all queue elements and leave the header and tail empty * / void QueueDestroy (Queue* pQ) {assert (pQ) / / prevent the incoming pQ from being null QueueNode* cur = pQ- > pHead; / / create a traversal pointer cur while (cur! = NULL) {/ / cur is not null and enter the loop QueueNode* curNext = cur- > next; / / beacon pointer curNext to prevent the next node free (cur) from being found after the cur is released / / release the node currently pointed to by cur cur = curNext; / / move pointer} pQ- > pHead = pQ- > pTail = NULL; / / empty dry field pointer} / * determine whether the queue is empty * / bool QueueIfEmpty (Queue* pQ) {assert (pQ) / / prevent the incoming pQ from being empty return pQ- > pHead = = NULL; / / True if it is true, False} / * join the queue: enter the data at the end of the queue and exit the data head to head. If you are the first to join the queue, you should be both head and tail * / void QueuePush (Queue* pQ, QueueDataType x) {assert (pQ); / / prevent the incoming pQ from being empty / * create a new node: create a space of QueueNode size * / QueueNode* new_node = (QueueNode*) malloc (sizeof (QueueNode)) / * check malloc * / if (new_node = = NULL) {printf ("malloc failed!\ n"); exit (- 1);} / * place * / new_node- > data = x; / / data to be inserted new_node- > next = NULL / / default is empty / * join the queue: * [ideas] * case 1: queue is empty: both head and tail * [new_node] * ↑ ↑ * pHead pTail * * case 2: queue is not empty: data at the end of the queue * [ ]-> []-> [new_node] * pHead pTail pTail- > next * ↓ ↑ *-→ pTail (update tail pointer) * / if (pQ -> pHead = = NULL) {/ / case 1: queue is empty pQ- > pHead = pQ- > pTail = new_node / / both head and tail} else {/ / case 2: queue is not empty pQ- > pTail- > next = new_node; / / place new_node pQ- > pTail = new_node on the last node of the existing tail / / Update pTail to point to the new tail}} / * dequeue: enter the data at the end of the queue, head-to-head data * / void QueuePop (Queue* pQ) {assert (pQ); / / prevent the incoming pQ from being empty assert (! QueueIsEmpty (pQ)) / / prevent the team from being listed as empty / * depart: * [idea Sketch] * [free]-> []-> [] * pHead headNext * ↓ ↑ *-→ pHead (update header pointer) * / QueueNode* headNext = pQ- > pHead- > next / / beacon pointer HeadNext to prevent the next node free (pQ- > pHead) cannot be found after pHead is released; pQ- > pHead = headNext; / / update header / * if all the members of the team are deleted, not dealing with pTail will lead to the hidden danger of wild pointers * [idea Sketch] * Space where NULL has been dropped by free! * ↑ ↑ (wild pointer) * pHead (because HeadNext is NULL) pTail * / if (pQ- > pHead = = NULL) / / if pHead is empty pQ- > pTail = NULL / / process the tail pointer and leave the tail pointer empty} / * return the head of the line data * / QueueDataType QueueFront (Queue* pQ) {assert (pQ); / / prevent the incoming pQ from being empty assert (! QueueIsEmpty (pQ)); / / prevent the queue from listing as empty return pQ- > pHead- > data } / * return queue end data * / QueueDataType QueueBack (Queue* pQ) {assert (pQ); / / prevent the incoming pQ from being empty assert (! QueueIsEmpty (pQ)); / / prevent the queue from listing empty return pQ- > pTail- > data;} / * calculate the queue size: counter method * / int QueueSize (Queue* pQ) {assert (pQ) / / prevent incoming pQ from being null int count = 0; / / counter QueueNode* cur = pQ- > pHead; / / create traversal pointer cur while (cur! = NULL) {+ + count; / / count + 1 cur = cur- > next; / / move pointer cur} return count;}

? Test.c

# include "Queue.h" void TestQueue1 () {Queue q; QueueInit (& Q); QueuePush (& Q, 1); QueuePush (& Q, 2); QueuePush (& Q, 3); QueuePush (& Q, 4); QueuePop (& Q); / / QueuePop (& Q); QueueDestroy (& Q);} void TestQueue2 () {Queue Q QueueInit (& Q); QueuePush (& Q, 1); QueuePush (& Q, 2); QueuePush (& Q, 3); QueuePush (& Q, 4); / / if you enter 12 first, let 1 come out, and then continue to enter, its order will not change. / / always keep the first-in-first-out, whether it is two in and out, then in and out, or all in and out again, it will not change. This is the nature of the queue while (! QueueIsEmpty (& Q)) {QueueDataType front = QueueFront (& Q); printf ("% d", front); QueuePop (& Q); / / pop minus the next} printf ("\ n"); QueueDestroy (& Q);} int main (void) {TestQueue2 (); return 0 } this is the end of the article on "sample Analysis of queues in C language". I hope the above content can be helpful to you, so that you can learn more knowledge. if you think the article is good, please share it for more people to see.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.