循环队列详解

2023-04-05

int base rear

概述1.先进先出的线性序列，称为队列，队列也是一种线性表，只不过它是操作受限的线性表，只能在两端操作。一端进，一端出。进的一端称为队尾，出的一端称为队头，队列可以用顺序存储也可以用链式存储。2.队列的顺序存储形式，可以用一段连续的空间存储数据元素，用两个整型变量记录队头和队尾元素的下标。3初始化(1

概述

1.先进先出的线性序列，称为队列，队列也是一种线性表，只不过它是操作受限的线性表，只能在两端操作。一端进，一端出。进的一端称为队尾，出的一端称为队头，队列可以用顺序存储也可以用链式存储。

2.队列的顺序存储形式，可以用一段连续的空间存储数据元素，用两个整型变量记录队头和队尾元素的下标。

3初始化

(1)

base为数组的基地址,front,base分别代表指向队头和队尾的"指针"(数组下标),构造空队列只需要申请一块内存给基地址,并且将队头指针与队尾指针赋值为0.

(2)

因为该队列为循环队列所以


typedef struct SqQueue
{
int* base;
int front, rear;
}SqQueue;
 
//构造空队列
bool InitQueue(SqQueue& Q)
{
Q.base = new int[Maxsize];
if (Q.base == NULL)
{
return false;
}
Q.front = Q.rear = 0;
return true;
}

4入队

(1)将队尾指向的位置赋值,并且赋值后将队尾的位置后移

(2)在入队时难免会出现以下情况

队列的空间未利用完,但是却造成了元素的溢出(又称"假溢出"),所以要利用循环队列,这样就不会有这样的顾虑

入队的操作为

Q.base[Q.rear]=e; 将元素e放入Q.rear指向的空间

Q.rear=(Q.rear+1)%Maxsize rear指针向后移动一个单位

至于为什么要加对(Q.rear+1)取模,这是因为rear指针会一直增加到比队列容量大的数字,对其取模就是为了使其缩小,指向真正的位置例如容量大小为5 队尾指向9 取模队尾指向的是4,说明队尾指正已经走过了一个圈

tips:在入队前要判断队列是否为空怎们办

如图此时队尾指向的是循环队列的最后一个空间,这个空间并没有存放任何数据,判断队列是否为满只要将队尾指针+1看看其是否与队头相等,此处为什么要取模?

例如队列空间大小为10,队尾指向第10个空间,下标为9,对其加1等于10,取模等于0,此时队头也是指向0的所以需要取模

有例如如果一开始队头指向的是1,队尾指向的是0,那么队尾加1,取模后为1,那么此时对也满


//入队
bool Push(SqQueue& Q, int e)
{
if ((Q.rear + 1) % Maxsize == Q.front)
{
cout << "队满" << endl;
return false;
}
 
Q.base[Q.rear] = e;
Q.rear = (Q.rear + 1) % Maxsize;
return true;
}

5出队

出队前判断队列是否为空

当尾指针与头指针指向一起时队空,注意与队满的区别

出队的操作

e=Q.base[Q.front];

Q.front=[Q.front+1]%Maxsize;

将头指针向着元素增长方向移动一个单元,原来的头指针指向的元素并没有真正的删除,只是逻辑上的删除,后序如果要用到这个空间,会用新的元素将其覆盖掉

至于为什么要用取模和上述的入队是一致的


bool Pop(SqQueue& Q, int& e)
{
if (Q.rear == Q.front)
{
cout << "队空" << endl;
return false;
}
e = Q.base[Q.front];
Q.front = (Q.front + 1) % Maxsize;
}

6.获取队头元素

判断队列是否为空

简单的数组取元素而已


int Get_front(SqQueue Q)
{
if (Q.rear == Q.front)
{
cout << "队空" << endl;
return -1;
}
 
return Q.base[Q.front];
}

7.获取队尾元素

判断队列是否为空

因为队尾一直指向最后一个元素的后一个位置,所以要去指正前面的空间,就是队尾元素


int Get_back(SqQueue Q)
{
if (Q.front == Q.rear)
{
cout << "队空" << endl;
return -1;
}
 
return Q.base[Q.rear - 1];
}

8.获取队列元素个数

这两段的代码意思是一样的

因为队尾减队头可能会出现负数,所以需要加上容量大小后取模,这样才会得到真实的容量大小

例如队列大小6,队尾指向1,队头指向2,那么元素个数为(1-2+6)%6=5个

例如队列大小6,队尾指向5,队头指向0,那么元素个数为(5-0+6)%6=5个


int length(SqQueue Q)
{
return (Q.rear - Q.front + MaxSize) % MaxSize;
 
/*if (Q.rear - Q.front >= 0)
{
return Q.rear - Q.front;
}
else
{
return (Q.rear - Q.front + MaxSize);
}*/
}

完整代码如下


#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
using namespace std;
 
const int MaxSize = 100;
 
typedef struct SqQueue
{
int* base;
int front, rear;
}SqQueue;
 
bool InitQueue(SqQueue& Q)
{
Q.base = new int[MaxSize];
if (Q.base == NULL)
{
return false;
}
Q.front = Q.rear = 0;
return true;
}
 
bool Push(SqQueue& Q, int e)
{
if ((Q.rear + 1) % MaxSize == Q.front)
{
return false;
}
 
Q.base[Q.rear] = e;
Q.rear = (Q.rear + 1) % MaxSize;
return true;
 
}
 
bool Pop(SqQueue& Q, int& e)
{
if (Q.rear == Q.front)
{
return false;
}
e = Q.base[Q.front];
Q.front = (Q.front + 1) % MaxSize;
}
 
int Get_front(SqQueue Q)
{
if (Q.front == Q.rear)
{
return -1;
}
 
return Q.base[Q.front];
}
 
int Get_back(SqQueue Q)
{
if (Q.front == Q.rear)
{
return -1;
}
 
return Q.base[Q.rear - 1];
}
 
int length(SqQueue Q)
{
return (Q.rear - Q.front + MaxSize) % MaxSize;
 
/*if (Q.rear - Q.front >= 0)
{
return Q.rear - Q.front;
}
else
{
return (Q.rear - Q.front + MaxSize);
}*/
}
 
int main()
{
 
SqQueue S;
InitQueue(S);
 
int n = 0;
cout << "请输入有多少元素" << endl;
cin >> n;
cout << "依次输入元素" << endl;
while (n--)
{
int e;
cin >> e;
Push(S, e);
}
int L = length(S);
for (int i = 0; i < L; i++)
{
cout << "队尾:"<<Get_back(S) << " "<<"队头:"<<Get_front(S)<<"---";
 
int e = 0;
Pop(S, e);
cout << e <<" ";
cout << endl;
}
//cout << length(S);
cout << endl;
 
 
 
 
system("pause");
return EXIT_SUCCESS;
}