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

Today, the editor will share with you the relevant knowledge points about how to achieve the C language queue. The content is detailed and the logic is clear. I believe most people still know too much about this knowledge, so share this article for your reference. I hope you can get something after reading this article, let's take a look at it.

The basic concept of queue implementation

Queue: a special linear table that only allows inserting data on one end and deleting data on the other. The queue has first-in, first-out.

FIFO (First In First Out)

Queuing: the end of the insert operation is called the end of the queue: the end of the delete operation is called the head of the queue.

The queue can also be implemented by the structure of array and linked list, and it is better to use the structure of linked list, because if you use the structure of array, it will be less efficient to move the data O (N). The deletion of the header of the linked list structure only needs O (1). Tail insertion defines a tail pointer, which also requires only O (1).

Create a structure

This is a nested structure.

The address of argument Q is passed to the parameter pq. Pq is a pointer to the structure Queue. The head in Queue is the pointer to the head of the queue, and the tail is the pointer to the end of the queue.

Int main () {/ / create the structure variable qmax / the address of Q that needs to be passed. Queue q; return 0;}

Define a tail pointer tail for easy queuing. Head pointer head makes it easy to delete the head when you leave the team.

Typedef int QDataType;// node structure typedef struct QueueNode {QDataType data; struct QueueNode* next;} QNode;// header pointer and tail pointer structure typedef struct Queue {QNode* head; QNode* tail;} Queue; initialization structure

In the beginning, there is no space to create the queue, so you only need to initialize the first structure to ok. The initial state of the queue requires that the head and tail of the queue point to the same position, and both are empty.

Void QueueInit (Queue* pq) {assert (pq); pq- > head = pq- > tail = NULL;} destroy the queue structure

This time I put the destroy structure after the initialization structure because the memory leak is serious, but I often forget to destroy the structure. Creation means destruction, and the two are opposed to each other, so they come after initialization, as a matter of course.

Void QueueDestory (Queue* pq) {assert (pq); QNode* cur = pq- > head; while (cur) {QNode* next = cur- > next; free (cur); cur = next;} pq- > head = pq- > tail = NULL;} join the team

When you join the queue, a new node is created. It is best to initialize the newly opened newnode node. Set his next to empty to facilitate the later calculation of the queue length function and the writing of the loop conditions of the outbound function.

Void QueuePush (Queue* pq, QDataType x) {assert (pq); QNode* newnode = (QNode*) malloc (sizeof (QNode)); assert (newnode); / / the following two initializations are necessary newnode- > data = x; newnode- > next = NULL; if (pq- > tail = = NULL) {assert (pq- > head = = NULL) Pq- > head = pq- > tail = newnode;} else {pq- > tail- > next = newnode; pq- > tail = newnode;}} out of the queue

Because the Queue struct body cannot be empty, you need to assert

You also need to assert that pq- > head and tail are not empty.

Void QueuePop (Queue* pq) {assert (pq); assert (pq- > head & & pq- > tail); if (pq- > head- > next = = NULL) {free (pq- > head); pq- > head = pq- > tail = NULL;} else {QNode* next = pq- > head- > next Free (pq- > head); pq- > head = next;}} to determine whether the queue is empty

Returns true for null and false for false

Bool QueueEmpty (Queue* pq) {assert (pq); return pq- > head = = NULL;} the value of the peer QDataType QueueFront (Queue* pq) {assert (pq); assert (pq- > head); return pq- > head- > data;} the value at the end of the queue QDataType QueueBack (Queue* pq) {assert (pq); assert (pq- > tail); return pq- > tail- > data;} returns the length of the queue

The length cannot be negative, so the return type is size_t

Size_t QueueSize (Queue* pq) {assert (pq); QNode* cur = pq- > head; size_t size = 0; while (cur) {size++; cur = cur- > next;} return size;} Queue.h#pragma once#include # include typedef int QDataType;typedef struct QueueNode {QDataType data; struct QueueNode* next } QNode;typedef struct Queue {QNode* head; QNode* tail; / / size_t size;} Queue;void QueueInit (Queue* pq); void QueueDestory (Queue* pq); void QueuePush (Queue* pq, QDataType x); void QueuePop (Queue* pq); bool QueueEmpty (Queue* pq); size_t QueueSize (Queue* pq); QDataType QueueFront (Queue* pq); QDataType QueueBack (Queue* pq) Queue.c#include "Queue.h" void QueueInit (Queue* pq) {assert (pq); pq- > head = pq- > tail = NULL;} void QueueDestory (Queue* pq) {assert (pq); QNode* cur = pq- > head; while (cur) {QNode* next = cur- > next; free (cur); cur = next } pq- > head = pq- > tail = NULL;} void QueuePush (Queue* pq, QDataType x) {assert (pq); QNode* newnode = (QNode*) malloc (sizeof (QNode)); assert (newnode); newnode- > data = x; newnode- > next = NULL; if (pq- > tail = NULL) {assert (pq- > head = NULL) Pq- > head = pq- > tail = newnode;} else {pq- > tail- > next = newnode; pq- > tail = newnode;}} void QueuePop (Queue* pq) {assert (pq); assert (pq- > head & & pq- > tail) If (pq- > head- > next = = NULL) {free (pq- > head); pq- > head = pq- > tail = NULL;} else {QNode* next = pq- > head- > next; free (pq- > head); pq- > head = next } bool QueueEmpty (Queue* pq) {assert (pq); return pq- > head = = NULL;} size_t QueueSize (Queue* pq) {assert (pq); QNode* cur = pq- > head; size_t size = 0; while (cur) {size++; cur = cur- > next;} return size } QDataType QueueFront (Queue* pq) {assert (pq); assert (pq- > head); return pq- > head- > data;} QDataType QueueBack (Queue* pq) {assert (pq); assert (pq- > tail); return pq- > tail- > data;} Test.cvoid TestQueue () {Queue q; QueueInit (& Q); QueuePush (& Q, 1); QueuePush (& Q, 2) Printf ("% d", QueueFront (& Q)); QueuePop (& Q); QueuePush (& Q, 3); QueuePush (& Q, 4); while (! QueueEmpty (& Q)) {printf ("% d", QueueFront (& Q)); QueuePop (& Q);} printf ("\ n") } int main () {TestQueue (); return 0;} these are all the contents of the article "how to implement the C language queue". Thank you for reading! I believe you will gain a lot after reading this article. The editor will update different knowledge for you every day. If you want to learn more knowledge, please pay attention to the industry information channel.

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.