# Have you learned the basic operation of circular queue?

2022-04-23 15:03:00

Newcomer Xiaobai's first blog
️ I hope you will pay more attention
It will be updated frequently in the future ~

️ Personal home page ：  Collection and attention , Never get lost ~ ️

# Preface

`Tips： It's a little long , Little Lord, be patient ~`

Programming to achieve the basic operation of circular queue ： Build a queue , Take the team leader element , The team , Out of the team

# One 、 What is a circular queue ？

1️⃣ Let's first introduce the linear table ： The data structure is divided into linear structure and nonlinear structure , Queues and linear tables are linear structures . The linear table is written by n A finite sequence of data elements , The sequence has a unique “ first ” And unique “ the last one ” data elements ; except “ first ” and “ the last one ” outside , Each data element in the queue has only one direct precursor and one direct successor . The insertion and deletion of a linear table can be performed anywhere in the table .

2️⃣ Let's talk about the queue ： A queue is a special kind of linear table , What's special about this is that it's only allowed at the front of the table （front） Delete operation , And at the back end of the table （rear） Insert operation . Like the stack , A queue is a linear table with restricted operations . The end of the insertion operation is called the tail of the queue , The end of the delete operation is called the queue head . When there are no elements in the queue , Called an empty queue .

3️⃣ Related concepts of queue ： The data elements of a queue are called queue elements . Inserting a queue element into a queue is called queuing , Deleting a queue element from a queue is called out of queue . Because queues can only be inserted at one end , Delete... At the other end , So only the first elements to enter the queue can be deleted from the queue first , So the queue is also called first in, first out （FIFO—first in first out） The linear table .

4️⃣ Why do you have a circular queue ： In order to make full use of vector space , Overcome " False spillover " The method of phenomenon is ： Think of a vector space as a ring with its head and tail connected , And call this vector a cyclic vector . The queues stored in it are called circular queues （Circular Queue）. A circular queue is a sequential queue connected end to end , Look at the table that stores the queue elements logically as a ring , It's called a circular queue .

5️⃣ Related characteristics of circular queue ： In the circular queue structure , When the last position of the storage space has been used and it is necessary to enter the queue operation , Only the first location of the storage space is free , You can add the element to the first position , The first location of the storage space will be used as the tail of the team . Circular queues can more easily prevent pseudo overflow , But the queue size is fixed .

# Two 、 Defined function

## 1. Define the storage structure

``````// Storage structure of circular queue
#define MAXQSIZE  100   // Maximum queue length
typedef  struct
{
QElemType *base;       // Used to dynamically allocate storage space
int  front;            // Team leader index
int  rear;             // End of team index
} SqQueue;``````

## 2. initialization

``````// initialization
void InitQueue (SqQueue &Q)
{
// Construct an empty queue
Q.base =new QElemType[MAXQSIZE];
Q.front=Q.rear=0;
}``````

## 3. Destroy queue

``````// Destroy queue
void DestroyQueue(SqQueue &Q)
{
if(Q.base)
free(Q.base);
Q.base = NULL;
Q.front = Q.rear = 0;
}``````

## 4. Clear queue

``````// Clear queue
void ClearQueue(SqQueue &Q)
{
Q.front=Q.rear=0;
}``````

## 5. Find the length

``````// Find the length
int  QueueLength (SqQueue Q)
{
return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;
}``````

## 6. Sentenced to empty

``````// Sentenced to empty
bool QueueEmpty (SqQueue Q)
{
return (Q.front==Q.rear);
}``````

## 7. Find the team head element

``````// Find the team head element
Status GetHead (SqQueue Q, QElemType &e)
{
if(Q.front==Q.rear) return ERROR;
e=Q.base[Q.front];
return OK;
}``````

## 8. Loop queue in

``````// Loop queue in
Status EnQueue(SqQueue &Q,QElemType e)
{
if((Q.rear+1)%MAXQSIZE==Q.front)  return ERROR;
Q.base[Q.rear]=e;
Q.rear = (Q.rear+1) % MAXQSIZE;
return OK;
}``````

## 9. Loop queue out

``````// Loop queue out
Status DeQueue (SqQueue &Q,QElemType &e)
{
if(Q.front==Q.rear) return ERROR;
e=Q.base[Q.front];
Q.front=(Q.front+1) % MAXQSIZE;
return OK;
}``````

## 10. Traversal causes the queue to display

``````// Traversal causes the queue to display
void DisplayQueue(SqQueue Q)
{
int i=Q.front;
while(Q.front!=Q.rear && (i+MAXQSIZE) % MAXQSIZE != Q.rear)
{
cout<<Q.base[i]<<endl;
i++;
}
}``````

# 3、 ... and 、 Define small menus

You can use a small menu to make the interface more beautiful ~

``````void show_help()
{
cout<<"******* Data Structure ******"<<endl;
cout<<"1---- Empty the circular queue "<<endl;
cout<<"2---- Determine whether the circular queue is empty "<<endl;
cout<<"3---- Find the length of the loop queue "<<endl;
cout<<"4---- Take the team leader element "<<endl;
cout<<"5---- The team "<<endl;
cout<<"6---- Out of the team "<<endl;
cout<<"7---- Show queue "<<endl;
cout<<"      sign out , Input 0"<<endl;
}``````

# Four 、 Complete code

️️️

``````#include <iostream>
using namespace std;
#define ERROR -1
#define OK 1
typedef int QElemType;
typedef int Status;
// Storage structure of circular queue
#define MAXQSIZE  100   // Maximum queue length
typedef  struct
{
QElemType *base;       // Used to dynamically allocate storage space
int  front;            // Team leader index
int  rear;             // End of team index
} SqQueue;
// initialization
void InitQueue (SqQueue &Q)
{
// Construct an empty queue
Q.base =new QElemType[MAXQSIZE];
Q.front=Q.rear=0;
}
// Destroy queue
void DestroyQueue(SqQueue &Q)
{
if(Q.base)
free(Q.base);
Q.base = NULL;
Q.front = Q.rear = 0;
}
// Clear queue
void ClearQueue(SqQueue &Q)
{
Q.front=Q.rear=0;
}
// Find the length
int  QueueLength (SqQueue Q)
{
return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;
}
// Sentenced to empty
bool QueueEmpty (SqQueue Q)
{
return (Q.front==Q.rear);
}
// Find the team head element
Status GetHead (SqQueue Q, QElemType &e)
{
if(Q.front==Q.rear) return ERROR;
e=Q.base[Q.front];
return OK;
}
// Loop queue in
Status EnQueue(SqQueue &Q,QElemType e)
{
if((Q.rear+1)%MAXQSIZE==Q.front)  return ERROR;
Q.base[Q.rear]=e;
Q.rear = (Q.rear+1) % MAXQSIZE;
return OK;
}
// Loop queue out
Status DeQueue (SqQueue &Q,QElemType &e)
{
if(Q.front==Q.rear) return ERROR;
e=Q.base[Q.front];
Q.front=(Q.front+1) % MAXQSIZE;
return OK;
}
// Traversal causes the queue to display
void DisplayQueue(SqQueue Q)
{
int i=Q.front;
while(Q.front!=Q.rear && (i+MAXQSIZE) % MAXQSIZE != Q.rear)
{
cout<<Q.base[i]<<endl;
i++;
}
}
void show_help()
{
cout<<"******* Data Structure ******"<<endl;
cout<<"1---- Empty the circular queue "<<endl;
cout<<"2---- Determine whether the circular queue is empty "<<endl;
cout<<"3---- Find the length of the loop queue "<<endl;
cout<<"4---- Take the team leader element "<<endl;
cout<<"5---- The team "<<endl;
cout<<"6---- Out of the team "<<endl;
cout<<"7---- Show queue "<<endl;
cout<<"      sign out , Input 0"<<endl;
}
int main()
{
char operate_code;
show_help();
SqQueue Q;
InitQueue(Q);
QElemType e;
int i;
while(1)
{
cout<<" Please enter the operation code :";
cin>>operate_code;
if(operate_code=='1')
{
cout<<"The queue has been cleared."<<endl;
ClearQueue(Q);
}
else if (operate_code=='2')
{
if(QueueEmpty(Q))
cout<<"The queue is empty."<<endl;
else
cout<<"The queue is not empty."<<endl;
}
else if (operate_code=='3')
{
cout<<"The length of queue is:"<<QueueLength(Q)<<endl;
}
else if (operate_code=='4')
{
cout<<" The team leader element is ："<<endl;
if(GetHead(Q,e) == 1) cout<<e<<endl;
else cout <<"error"<<endl;
}
else if (operate_code=='5')
{
cout<<" Please enter the number of you want to join the team ："<<endl;
cin>>e;
EnQueue(Q,e);
}
else if (operate_code=='6')
{
cout<<" The outgoing element is ："<<endl;
if(DeQueue(Q,e)) cout<<e<<endl;
}
else if (operate_code=='7')
{
cout<<"The contents of the queue are:"<<endl;
DisplayQueue(Q);
}
else if (operate_code=='0')
{
break;
}
else
{
cout<<"\n Opcode error ！！！"<<endl;
show_help();
}
}
// Call the destroy stack function
DestroyQueue(Q);
return 0;
}``````

# summary

This paper is used to introduce the code implementation process and running result example of circular queue in data structure . The initialization of the circular queue is displayed in menu style 、 Empty 、 The destruction 、 Find the length , Find the team head element 、 Sentenced to empty 、 The team , Out of the team , And traversing the queue to make it display .

https://yzsam.com/2022/04/202204231410400560.html