Link to original blog post

Common linear structure applications are stacks and queues, but this time I’m going to talk about queues. Queue is a first-in, first-out data structure, similar to 🌰🌰 : queuing for tickets, those at the front buy first, those at the back buy last (not to mention queue-jumping).

In software development, queue knowledge is applied, such as task queues, event queues, message queues, and time-related things have queue effects.

Queues are divided into two types, chain queue and static queue, the former is composed of a linked list, the latter is composed of an array; The circular queues in question are static queues, and it must be said that static queues must be circular queues.

Why do static queues have to be circular queues?

For an array with a certain length, the storage space is confirmed, and the storage space in the array needs to be repeatedly used in the process of queue entry and queue exit. Therefore, the “continuous reuse” here needs to be recycled, otherwise there will be a waste of space. For circular queues, you only need two arguments: front, which represents the index of the first element of the queue, and rear, which represents the index of the next element of the last valid element of the queue.

Take a look at the process of leaving and joining the team below:

Pictures from the Internet

With the above, we can know the team exit and team entry algorithm as follows:

Queue entry algorithm: Rear = (Rear +1)% Array length

Queue queue algorithm: front = (front+1)% array length

In the understanding of the queue, queue algorithm after the basic you can create and maintain a cycle queue!

C language loop queue implementation

First let’s get ready for initialization:

Int len = 6; int len = 6; typedef struct Queue { int *pArray; // array pFront; // int pRear; }Queue; // Queue initialization void initQueue(Queue * q); Bool inputQueue(Queue * q, int value) // outputQueue(Queue * q, int value) Int *value) // Traversal void traverseQueue(Queue * q) // FullQueue bool isFullQueue(Queue * q) // EmptyQueue bool isEmptyQueue(Queue * q)Copy the code

We need these basic functions to make the queue work. The following is the implementation of the function

Void initQueue(Queue * q){// Dynamically allocate memory q->pArray = (int *)malloc(sizeof(int)*len); q->pFront = 0; q->pRear = 0; Bool isFullQueue(Queue * q){if((q->pRear+1)/len == q->pFront) return true; return false; Bool isEmptyQueue(Queue * q){if(q->pRear == q->pFront) return true; return false; } // join bool inputQueue(Queue * q, Int value){if(isFullQueue(q)) return false else q->pArray[(q->qRear+1)%len] = value q->qRear = (q->qRear+1)%len  bool outputQueue(Queue * q, int *value){ if(isFullQueue(q)) return false else *value = q->pArray[q->qFront] q->qFront = (q->qFront+1)%len } void TraverseQueue (Queue * q){printf(" Walk through the Queue \n"); int front = q->qFront while(index ! = q->qRear){ printf("%d\n", q->PArrry[front]); front = (q->qFront+1)%len; }}Copy the code

Create a linked list in main:

Int main (int arg c, const char * argv []) {printf (" -- -- -- -- -- -- -- -- -- circular queue build -- -- -- -- -- -- -- -- -- \ n "); Queue q; int value; initQueue(&q); // inputQueue(&q, 12); inputQueue(&q, 4556); / / traverse traverseQueue (& q); // outputQueue(&q, &value); Printf (" queue value: %d\n", value); traverseQueue(&q); return 0; }Copy the code

Code example: C to create a loop queue

Reference:

Hao Bin data structure video

See more blog posts:

Personal gold digging more articles link jump;

GitHub blog project links to more articles jump;