Basic operation and simple implementation of circular queue

Article directory

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[0] 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
Q.front=(Q.front+1)%MAXQSIZE;//Change of head pointer position

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;
e=Q.base[Q.front];	//Save team header element	
Q.front=(Q.front+1)%MAXQSIZE;	//Team head pointer + 1
return OK;
}

Loop queue fetch header element

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;
e=Q.base[Q.front]; //Save team header element 
Q.front=(Q.front+1)%MAXQSIZE; //Team head pointer + 1
return true;
}

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
}

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"
	   <<"4,Team leader element\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:
	     cout<<" Team leader elements are:"<<GetHead(Q)<<endl;break; 
	   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
Private letter follow

Tags: less

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