# I. Introduction

Sequential representation and implementation of queues

Sequential representation of queues - using one-dimensional array base[MAXQSIZE]

```#define MAXQSIZE 100	//Maximum queue length
typedef struct{
Qelem *base;		//Initialized dynamically allocated storage
int front;		//Head pointer, not pointer variable. If the queue is not empty, only the head element is expected
int rear;		//Tail pointer, not pointer variable. If the queue is not empty, it points to the next position of the tail element
}SqQueue;```

Initial:

`front=rear=0;//Team empty` Team entry:

```base[Q.rear]=e;//
rear++;	//Point to the next space``` Team:

```e=base[Q.front];//Team out
front++;
front=rear;//Team empty sign``` Overflow when rear==MAXQSIZE • If front=0,rear=MAXQSIZE, enter the team again - true overflow;
• If front!=0,rear=MAXQSZIE, enter the team again - false overflow

How to solve the problem of false overflow?

1. Move the elements in the team to the opposite direction. The disadvantage is that it wastes time. All elements in the team have to move
2. The team space is assumed to be a circular table, that is, m storage units allocated to the queue can be recycled. When real = = maxqsize, if the start of the vector is empty, the empty space can be used from the beginning. When front= =MAXQSIZE, the same is true.

That is to say, loop queue is introduced
base is connected to base[MAXQSIZE-1], if rear+1MAXQSIZE, then rear=0;
Implementation method: using the module (mod, that is%) = = to calculate the co operation.
Insert element:

```Q.base[Q.rear]=e;	//Assign a value to the space indicated by the tail pointer
Q.rear=(Q.rear+1)%MAXQSIZE；//Tail pointer update, + 1%MAX=0```

Delete element:

```e=Q.base[Q.front];//Assign the element indicated by the head pointer to a variable e

The circular queue is not a circle, but an imaginary one.
So, circular queue: recycles the storage space allocated for the queue.

Judge whether the team is empty or full: use less one element space

• The condition of team empty: q.front = q.rear (the team is full, but it can't be distinguished, so use less one element space)
• Conditions for team full: (rear+1)%MAXQSIZE = Q.front # 2, Basic operation of circular queue

Loop queue initialization

```Status InitQueue(SqQueue &Q){
Q.base=new Qelemtype[MAXQSIZE]	//Allocate array space. base is the first element and the address of the array. Therefore, it is defined as a pointer variable in front. It is easy to use C + + syntax
//C syntax: using malloc function
if(Q.base)
exit(OVERFLOW);		//Storage allocation failed
Q.front=Q.rear=0;		//The head end pointer is set to 0, and the queue is empty
return OK;
}```

Operation of circular queue -- finding the queue length

```int Qlength(SqQueue Q){
return ((Q.rear-Q.front+MAXQSIZE)%MAXQSIZE);``` Loop queue in

```Status EnQueue(SqQueue &Q,int e){
if((Q.rear+1)%MAXQSIZE==Q.front)//Team full
return ERROR;
Q.base[Q.rear]=e; //Assign a value to the space indicated by the tail pointer
Q.rear=(Q.rear+1)%MAXQSIZE；//Tail pointer update, + 1%MAX=0
return OK;```

Loop queue out

```Status DeQueue(SqQueue &Q,int &e){
if(Q.front==Q.rear)	//Team empty
return ERROR;
Q.front=(Q.front+1)%MAXQSIZE;	//Team head pointer + 1
return OK;
}```

```int GetHead(SqQueue Q){
if(Q.front!=Q.rear)	//Queue is not empty
return Q.base[Q.front];	//Returns the value of the queue head pointer element. The queue head pointer does not change```

# 3, Simple implementation of circular queue

```#include<bits/stdc++.h>
using namespace std;
const int MAXQSIZE=10;
typedef struct{
int *base;
int front;
int rear;
}SqQueue;

bool InitQueue(SqQueue &Q){
Q.base=new int[MAXQSIZE];
if(!Q.base)
exit(false);
Q.front=Q.rear=0;
return true;
}

int Qlength(SqQueue Q){
return ((Q.rear-Q.front+MAXQSIZE)%MAXQSIZE);
}

bool EnQueue(SqQueue &Q,int e){
if((Q.rear+1)%MAXQSIZE==Q.front)//Team full
return false;
Q.base[Q.rear]=e; //Assign a value to the space indicated by the tail pointer
Q.rear=(Q.rear+1)%MAXQSIZE;//Tail pointer update, + 1%MAX=0
return true;
}

bool DeQueue(SqQueue &Q,int &e){
if(Q.front==Q.rear) //Team empty
return false;
Q.front=(Q.front+1)%MAXQSIZE; //Team head pointer + 1
return true;
}

if(Q.front!=Q.rear) //Queue is not empty
return Q.base[Q.front]; //Returns the value of the queue head pointer element. The queue head pointer does not change
}

int main()
{
int n;
SqQueue Q;
cout<<"Basic operation of circular queue:"
<<"1,Loop queue initialization\n"
<<"2,Join the team\n"
<<"3,Find queue length\n"
<<"5,Team out\n" ;
while(1){
int k,q,m;
cout<<"Enter operation sequence number:";
cin>>n;
switch(n)
{
case 1: if(InitQueue (Q))
cout<<"Circular queue initialization succeeded"<<endl;
else
cout<<"initialization failed";
break;
case 2:
for(int i=0;i<=10;i++)
EnQueue(Q,i);
cout<<"Team success"<<endl; break;
case 3:
cout<<"Queue length is"<<Qlength(Q)<<endl; break;//The output is 9 because the end of the queue pointer changes to 1 at the beginning
case 4:
case 5:

cout<<"The queue element is:";
for(int i=0;i<10;i++)
{
DeQueue(Q,i);
cout<<i<<" ";
}
cout<<endl;break;
}
}
}```

Content reference: data structure, Yan Weimin  Published 24 original articles, won 45 praises, visited 1208

Tags: less

Posted on Mon, 13 Jan 2020 23:58:10 -0800 by supermerc