This is the third day of my participation in the November Gwen Challenge. Check out the details: the last Gwen Challenge 2021

Preface:

Before we finished learning stack, relatively easy, today we learn the sequence queue and circular queue inside the queue, say difficult, say simple is not simple, we need to study carefully, the blogger will try to explain the principle and logic clearly, do not understand the children’s shoes can carefully read several times, the blogger really want to teach you. I hope you read it carefully, and if you have any questions, you can comment on it. I hope you like it.

Once a day to prevent puppy love:

1. What is a queue

A queue is a special kind of linear table, special in that it only allows deletion at the front of the table and insertion at the rear. Like a stack, a queue is a linear table with limited operation. The end that inserts is called the end of the queue, and the end that deletes is called the head of the queue. A queue with no elements is called an empty queue. The data elements of a queue are also called queue elements. Inserting a queue element into a queue is called enqueueing, and removing a queue element from a queue is called enqueueing. Because the queue can only be inserted at one end and deleted at the other end, only the earliest element can be deleted from the queue first, so the queue is also called FIFO – first in first out (FIFO – first in first out) linear table.

1.1 Understand sequential queues and logic

A sequential queue is the sequential storage structure of a queue, which is actually an operation-constrained sequential table. Like a sequential list, a sequential queue uses a vector space to hold the elements of the current queue. Since the positions of the head and tail of the queue change, set the two Pointers front and rear to indicate the position of the head element and the tail element in the vector space respectively. Their initial values should be set to 0 when the queue is initialized. Speak person is (an array, there are two logo, one in head and a tail, head is responsible for the output value, the tail is responsible for the input values of these two value maximum is the MaxSize) is roughly such, in life we learn anything, all need to learn it logic, to understand the meaning of this stuff, facilitate our memory, draw a figure for everyone to understand the simple life

Don’t know you ever drink tea YanYue color, blogger is the college students in changsha, this tea YanYue color, special fire, bloggers have time to go out to play every time point a cup of tea YanYue color, every time they go to a blogger is the next morning, the poor fellow, drink tea YanYue color every time waiting in line, and other bloggers to team head, bloggers will find behind me every nobody, humble, Order a teenager’s latte or an Orchid latte and you’ll find that you have to wait, wait for the milk tea to come out, and then you’ll find that the person before you is also waiting and in line in front of you, hahaha, it’s worth the wait when you get it. (The queue is just like the queue in our life. Those who come first buy first, and those who come later have to wait in line until the leader of the queue finishes buying.) Order queue (sq.front+1)%MaxSize (sq.front+1)%MaxSize (sq.front+1)%MaxSize (sq.front+1)%MaxSize (MaxSize)

1.2 Understand the loop queue and recognize the code we need

In order to make full use of vector space, the method to overcome the phenomenon of “false overflow” is to imagine vector space as a circle connected end to end, and call this vector a circular vector. The queues stored in them are called Circular queues. A circular queue is a circular queue that connects sequential queues end to end and logically treats the table storing queue elements as a ring.

This is equivalent to always rotating in this queue, which is very convenient to save space

Typef struct {int data[MaxSize]; int front,rear; }SqQueue; // The loop queue is of type sq.rear =sq.front = 0; Rear +1)%MaxSize==sq.front (sq.rear+1)%MaxSize==sq.front Rear ==sq. rear==sq.front// sq.rear= (sq.rear+1)%MaxSize; *x =sq.data[(sq.front+1)%MaxSize]; // Out of the team is the same as in teamCopy the code

The above is the core code of the loop queue.

1.3 Initialization of the Loop Queue

typedef struct { int data[MaxSize]; Int front,rear; }SqQueue; void InitQueue(SqQueue &sq) { sq.rear =sq.front = 0; SqQueue sq.rear==sq.front) {return 0; return sq.rear==sq.front; } *x =sq.data[(sq.front+1)%MaxSize]; Return 1; }Copy the code

1.4 Circular Queue Joining

Int EnQueue(SqQueue &sq,int x) {if(sq.rear+1)%MaxSize==sq.front) {return 0; } sq.rear = (sq.rear+1)%MaxSize; Sq.data [sq.rear] = x; sq.data[sq.rear] = x; // write the value to return 1; }Copy the code

1.. 5 Loop queue outgoing

Int DeQueue(SqQueue &sq,int *x) {if(sq.rear==sq.front){return 0; } sq.front = (sq.front+1)%MaxSize; // If *x =sq.data[sq.front]; // If *x =sq.data[sq.front]; return 1; }Copy the code

1.6 Circular queue effect demonstration and overall code

#include <stdio.h> #include <stdlib.h> #define MaxSize 6 typedef struct { int data[MaxSize]; int front,rear; }SqQueue; void InitQueue(SqQueue &sq) { sq.rear =sq.front = 0; } int EnQueue(SqQueue &sq,int x) { if((sq.rear+1)%MaxSize==sq.front) { return 0; } sq.rear = (sq.rear+1)%MaxSize; sq.data[sq.rear] = x; return 1; } int DeQueue(SqQueue &sq,int *x) { if(sq.rear==sq.front){ return 0; } sq.front = (sq.front+1)%MaxSize; *x =sq.data[sq.front]; return 1; } int GetHead(SqQueue sq,int *x) { if(sq.rear==sq.front) { return 0; } *x =sq.data[(sq.front+1)%MaxSize]; return 1; } int QueueEmpty(SqQueue sq) { if(sq.rear==sq.front)return 1; return 0; } int main(int argc, char *argv[]) { SqQueue sq; int e; int i,n,m,num; Printf (" initialize queue \n"); InitQueue(sq); If (QueueEmpty(sq)==1) {printf(" QueueEmpty \n"); } else{printf(" queue not empty \n"); } printf(" Enter the number of queues you need to join (MaXSize: %d)\n", MaXSize); scanf("%d",&n); Printf (" Enter the value of your %d: ",n); for(i=0; i<n; i++) { scanf("%d",&num); If (EnQueue(sq,num)) {printf("%d join queue \n",num); } else{printf("%d is full \n",num); } if(i==4){ DeQueue(sq,&e); Printf (" queue: %3d\n",e); }} GetHead(sq,&e); Printf (" queue completed, queue header value: %d\n",e); Printf (" Input queue number (up to %d)\n",n); scanf("%d",&m); Printf (" queue value: "); for(i=0; i<m; i++) { if(DeQueue(sq,&e)==1) { printf("%3d",e); } else {printf(" queue empty "); } } return 0; }Copy the code

Note: the blogger code does not use Pointers so it will report errors, you need to change to.cpp file, or you can change Pointers and use “->” access

Conclusion:

Queue actually difficult well and stack has the same place, as long as we understand the logic, it is very easy to write, if you know the code means, know code means to use code to write your logic, circular queue is equivalent to the rotation of the memory, like the life of the pipe connection at both ends and then the inside of the water kept turning. Creation is not easy, like, follow, comment, favorites, thank you. Or cry for you to see!!

The last:# Data structure upgrade learning, stack (chain stack)