Shulou(Shulou.com)05/31 Report--

This article mainly introduces the C language chain queue and circular queue how to achieve the relevant knowledge, the content is detailed and easy to understand, easy to operate, and has a certain reference value. I believe you will gain something after reading this article on how to realize chain queue and circular queue in C language. let's take a look.

Implementation of queues

Queue is a linear first-in-first-out (First in First Out) table, referred to as FIFO. Unlike a stack, a stack is a last-in, first-out (first-in-first-out) linear table. In the queue, the end that is allowed to insert is called the end of the queue, and the end that is allowed to be deleted is called the head of the line. Suppose the queue is Q = (A1 ~ a2, … An), so A1 is the head of the line element and an is the end of the line So we can delete it, always start with A1, and insert it at the end of the column. This is also more in line with our usual habits in life, the first priority, and the last, of course, at the end of the line. Queues are divided into sequential queues and circular queues. Sequential queues can be implemented using arrays or linked lists. Here, we choose to use linked lists to implement sequential queues.

Today, we mainly introduce the queues and circular queues implemented by linked lists.

Chain queue

What are the main basic operations of the queue?

/ / initialize queue void QueueInit (Queue* Q); / / queue tail void QueuePush (Queue* Q, QDataType data); / / queue head out queue void QueuePop (Queue* Q); / / get queue header element QDataType QueueFront (Queue* Q); / / get queue tail element QDataType QueueBack (Queue* Q); / / get the number of valid elements in the queue int QueueSize (Queue* Q) / / check whether the queue is empty, return a non-zero result if it is empty, return 0 bool QueueEmpty (Queue* Q) if it is not empty; / / destroy the queue void QueueDestroy (Queue* Q); define the typedef int QDataType;// chain structure of the chained queue: the structure of the queue typedef struct QListNode {struct QListNode* _ next; QDataType _ data;} QNode;// queue typedef struct Queue {QNode* _ front; QNode* _ rear;} Queue Implementation of chain queue

1. Initialize the queue

Void QueueInit (Queue* Q) {assert (Q); Q-> _ front = NULL; Q-> _ rear = NULL;}

2. Destroy the queue

Void QueueDestroy (Queue* Q) {assert (Q); QNode* cur = Q-> _ front; while (cur! = NULL) {QNode* next = cur- > _ next; free (cur); cur = next;} Q-> _ front = Q-> _ rear = NULL;}

3. Empty queue

Bool QueueEmpty (Queue* Q) {assert (Q); / / if (Q-> _ front = = NULL) / / {/ / return 1; / /} / / else / / {/ / return 0; / /} return Q-> _ front = = NULL;}

4. Join the team operation

Void QueuePush (Queue* Q, QDataType data) {assert (Q); QNode* newnode = (QNode*) malloc (sizeof (QNode)); if (newnode = = NULL) {exit (- 1);} newnode- > _ data = data; newnode- > _ next = NULL; if (Q-> _ front = = NULL) {Q-> _ front = Q-> _ rear = newnode } else {Q-> _ rear- > _ next = newnode; Q-> _ rear = newnode;}}

5. Team operation

Void QueuePop (Queue* Q) {assert (Q); assert (! QueueEmpty (Q)); QNode* next = Q-> _ front- > _ next; free (Q-> _ front); Q-> _ front = next; if (Q-> _ front = = NULL) {Q-> _ rear = NULL;}}

6. Pick-up head element

QDataType QueueFront (Queue* Q) {assert (Q); assert (! QueueEmpty (Q)); return Q-> _ front- > _ data;}

7. Operation at the end of the queue

QDataType QueueBack (Queue* Q) {assert (Q); assert (! QueueEmpty (Q)); return Q-> _ rear- > _ data;}

8. The number of effective elements in the team

Int QueueSize (Queue* Q) {assert (Q); int size = 0; QNode* cur = Q-> _ front; while (cur) {size++; cur = cur- > _ next;} return size;} definition of cyclic queue

A circular queue is to circle the last location of the queue storage space to the first location to form a logical ring space for the queue to recycle. In the cyclic queue structure, when the last location of the storage space has been used and wants to enter the queue operation, only the first location of the storage space is free, the element can be added to the first position, that is, the first location of the storage space is used as the end of the line. Circular queues can more easily prevent pseudo-overflow, but the queue size is fixed. In a circular queue, there is front=rear when the queue is empty, and front=rear when all the queue space is full. In order to distinguish between the two cases, it is stipulated that the circular queue can only have a maximum of MaxSize-1 queue elements, and when there is only one empty storage unit in the circular queue, the queue is full. Therefore, the condition for the queue to be null is front=rear, and the condition for the queue to be full is front= (rear+1)% MaxSize.

The space of circular queue can be reused, which solves the problem of space waste of ordinary queue.

Implementation of the circular queue typedef struct {int* a; int front; int tail; int k;} MyCircularQueue;// declare in advance that the empty queue is full bool myCircularQueueIsEmpty (MyCircularQueue* obj); bool myCircularQueueIsFull (MyCircularQueue* obj); / / create the circular queue MyCircularQueue* myCircularQueueCreate (int k) {MyCircularQueue* cq= (MyCircularQueue*) malloc (sizeof (MyCircularQueue)); cq- > a = (int*) malloc (sizeof (int) * (kryp1)); cq- > front=cq- > tail=0; cq- > KFK Return cq;} / / round robin bool myCircularQueueEnQueue (MyCircularQueue* obj, int value) {if (myCircularQueueIsFull (obj)) {return false;} obj- > a [OBJ-> tail] = value; obj- > tail++; obj- > tail%= (obj- > knot 1); return true;} / / outbound bool myCircularQueueDeQueue (MyCircularQueue* obj) {if (myCircularQueueIsEmpty (obj)) {return false;} obj- > front++ Obj- > front%= (obj- > kryp1); return true;} / / cyclic queue header int myCircularQueueFront (MyCircularQueue* obj) {if (myCircularQueueIsEmpty (obj)) {return-1;} return obj- > a [obj-> front];} / / cyclic queue tail int myCircularQueueRear (MyCircularQueue* obj) {if (myCircularQueueIsEmpty (obj) {return-1;} int I = (obj- > tail+obj- > k)% (obj- > kryp1) Return obj- > a [I];} / Circular queue Null bool myCircularQueueIsEmpty (MyCircularQueue* obj) {return obj- > front==obj- > tail;} / / Loop queue full bool myCircularQueueIsFull (MyCircularQueue* obj) {return (obj- > tail+1)% (obj- > knot 1) = = obj- > front;} / / destroy cyclic queue void myCircularQueueFree (MyCircularQueue* obj) {free (obj- > a); free (obj) } this is the end of the article on "how to implement chain queues and circular queues in C language". Thank you for reading! I believe that everyone has a certain understanding of the knowledge of "C language chain queue and circular queue". If you want to learn more knowledge, you are welcome to follow 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.