【数据结构】三、栈和队列：5.顺序队列(循环队列)（初始化，判空判满，入队，出队，实例）

队列Queue

逻辑结构

队列（Queue）是只允许在一端进行插入，另一端进行删除操作的线性表。

重要术语：队头（可以出队（删除）的一段），队尾（放入（入队）的元素的一段），空队列。

• 特点：先进先出（First in First out, FIFO）

物理（存储）结构

1. 顺序队列（顺序存储）
2. 链队列（链式存储）

基本操作

InitQueue(&Q)：初始化队列，构造一个空队列Q。

DestroyQueue(&Q)：销毁队列。销毁并释放队列Q所占用的内存空间。

EnQueue(&Q,x)：入队。若队列Q未满，将x加入，使之成为新的队尾。

DeQueue(&Q,&x)：出队。若队列Q非空，删除队头元素，并用x返回。

GetHead(Q,&x)：读队头元素。若队列Q非空，则将队头元素赋值给x。

1.顺序队列（循环队列）

用顺序存储，连续空间实现队列

循环队列的特点

1. 顺序存储：循环队列使用数组作为底层数据结构，元素按顺序存储在数组中。这样可以简化队列的实现，并且通过使用循环来优化队列的操作。

2. 固定容量：循环队列拥有固定的容量，即队列最多可以存储的元素数量是预先确定的。在使用数组作为底层数据结构时，需要初始化队列的最大容量。

3. 头尾相连：循环队列将队列的头部和尾部连接起来形成一个环状结构，当队列的尾部指针达到数组的最末尾时，它将会绕回到数组的开头。这样可以充分利用数组的存储空间，避免浪费空间。

4. 队空和队满判断：循环队列通过队头指针和队尾指针的位置关系来判断队列的状态。当队头指针和队尾指针相等时，表示队列为空；当队尾指针的下一个位置是队头指针时，表示队列已满。

5. 入队和出队的复杂度：在循环队列中，入队和出队操作的时间复杂度都是O(1)，即常数时间复杂度。这是因为循环队列通过使用固定容量和记录队列元素个数的方式，避免了移动元素的成本。

#define MaxSize 10			//定义队列中元素的最大个数
typedef struct{
    ElemType data[MaxSize];	//用静态数组存放队列元素
    int front,rear;			//front队头指针和rear队尾指针
} SqQueue;			//Sq即sequence：顺序的意思
1
2
3
4
5

1.1初始化

InitQueue(&Q)：初始化队列，构造一个空队列Q。

//初始化队列
void InitQueue(SqQueue &Q){
    //初始时 队头、队尾指针指向0
    Q.rear=Q.front=0;
}
1
2
3
4
5

1.2判空&判满

1.2.1判空

//判断队列是否为空
bool QueueEmpty(SqQueue Q){
    if(Q.rear==Q.front)		//队空条件：队头指针==队尾指针
        return true;
    else 
        return false;
}
1
2
3
4
5
6
7

1.2.2判满

方案一

从队头结点开始插入，一直插入到MaxSize放满。但其实现在并不一定是满队列，因为队头还可以出队元素，这时候rear还在MaxSize，但是front不在data[0]。

队列己满的条件：队尾指针的再下一个位置是队。这里就必须空出一个元素的位置，不能让Q.rear==Q.front，因为这样，就和判空的条件一样了。

//判断队列是否满
bool QueueFull(SqQueue Q){
    if( (Q.rear+1)%MaxSize==Q.front )	//队列将满
        return true;
    else
        return false;
}
1
2
3
4
5
6
7

方案二

如果说不能浪费判满的那一个存储空间，就在定义的时候创建一个size表示队列的长度。

#define MaxSize 10
typedef struct{
    ElemType data[MaxSize];
    int front,rear;
    int size;
} SqQueue;	
1
2
3
4
5
6

这样，初始化的时候，设置size=0。插入成功size++;删除成功size--;。

队满的条件就变成了size==MaxSize。

对空的条件：size==0。

方案三

定义一个tag，用来存储最近进行了删除和插入的操作，每次删除操作成功时，都令tag=0;每次插入操作成功时，都令tag=1;。

#define MaxSize 10
typedef struct{
    ElemType data[MaxSize];
    int front,rear;
    int tag;
} SqQueue;	
1
2
3
4
5
6

队满的条件就变成了front==raer && tag==1。

对空的条件：front==raer && tag==0。

1.3入队

EnQueue(&Q,x)：入队。若队列Q未满，将x加入，使之成为新的队尾。

//入队
bool EnQueue(SqQueue &Q, ElemType x){
    if（队列已满）
        return false;		//队满则报错
    Q.data [Q.rear]=x;		//将×插入队尾
    Q.rear=(Q.rear+1)%MaxSize;		//队尾指针后移，但不能一直+1会溢出，所以这里需要模运算，取(Q.rear+1)%MaxSize的余数
    return true;
}
1
2
3
4
5
6
7
8

循环队列

如果rear队尾一直+1，那么就会溢出，通过模运算，将无限的整数域映射到有限的整数集合 {0, 1, 2,…, MaxSize} 上，将存储空间在逻辑上变成环状。

如此实现的队列，称为循环队列。

1.4出队

DeQueue(&Q,&x)：出队。若队列Q非空，删除队头元素，并用x返回。

//出队（删除一个队头元素，并用x返回)
bool DeQueue(SqQueue &Q, ElemType &x){ 
    if(Q.rear==Q.front)
        return false;	//队空则报错
    x=Q.data[Q.front];
    Q.front=(Q.front+1)%MaxSize;
    return true;
}
1
2
3
4
5
6
7
8

1.5获取队头元素

GetHead(Q,&x)：读队头元素。若队列Q非空，则将队头元素赋值给x。

//获得队头元素的值，用x返回
bool GetHead(SqQueue Q, ElemType &x){ 
    if(Q.rear==Q.front)
        return false;	//队空则报错
    x=Q.data[Q.front];
    return true;
}
1
2
3
4
5
6
7

返回为元素类型

//取队头元素
QElemType GetHead(SqQueue Q){
	if (!QueueEmpty(Q)) //队列不为空
	{
		return Q.data[Q.front];  //返回队头指针元素
	}
	return false;
}
1
2
3
4
5
6
7
8

1.6获取队列元素个数

length= (Q.rear + MaxSize - Q.front)%MaxSize;

//获取队列元素个数
int QueueLength(SqQueue Q){
	int length=(Q.rear + MaxSize - Q.front)%MaxSize;
	return length;
}
1
2
3
4
5

❗1.7循环队列c++实例

#include<iostream>
using namespace std;

#define MaxSize 50  //最大队列长度
typedef int QElemType;

//循环队列

typedef struct
{
	QElemType* data;	//初始化的动态分配存储空间
	int front;				//头指针，若队列不空，指向队列头元素
	int rear;					//尾指针，若队列不空，指向队列尾元素的下一个位置
}SqQueue;  					//普通类型用 '.' *SqQueue指针类型用 '->'

bool InitQueue(SqQueue& Q);		//循环队列初始化
int  QueueLength(SqQueue Q);	//循环队列长度
bool QueueEmpty(SqQueue Q);			//判断队列是否为空
bool QueueFull(SqQueue Q);			//判断队列是否已满
bool EnQueue(SqQueue& Q, QElemType value);	//循环队列入队
bool DeQueue(SqQueue& Q, QElemType& value);	//循环队列出队
bool QueuePrint(SqQueue Q);			//打印输出队列
QElemType GetHead(SqQueue Q);		//获取队头元素





int main()
{
	SqQueue Q;  //创建循环队列Q
	InitQueue(Q); //队列初始化
	QElemType value = -1;
	
	int number = 0; //入队的元素个数
	cout<<"请输入要入队的元素个数："<<" ";
	cin>>number;

	int num = 0; //入队的数据元素
	while( (number--) > 0){
		EnQueue(Q, num); 	//将num入队
		num++;
	}
	cout << "队列输出顺序：";
	QueuePrint(Q); //遍历输出队列元素

	cout << "队头元素为：" << GetHead(Q) << endl;
	cout << "队列长度为：" << QueueLength(Q) << endl;

	cout << "---出队一个元素后---" << endl;
	DeQueue(Q, value);
	cout << "出队元素为：" << value << endl;
	QueuePrint(Q);
	cout << "出队后队头元素为：" << GetHead(Q) << endl;
	cout << "出队后队列长度为：" << QueueLength(Q) << endl;

	delete[] Q.data; //释放存储空间
	system("pause");
	return 0;
}










//初始化队列，构造一个空队列Q。
bool InitQueue(SqQueue& Q){
	Q.data = new QElemType[MaxSize]; //分配数组空间
	//Q.data = (QElemType*)MaxSize * sizeof(QElemType);  C语言语法
	if (!Q.data){
		return false;  //存储分配失败
	}
	Q.front = Q.rear = 0; //头指针尾指针置为0， 队列为空
	return true; 
}

//求循环队列的长度/元素个数
int QueueLength(SqQueue Q){
	//若rear指向大于队列长度后重新转一圈指向队头，假如rear=3，front= 4, 3-4=-1不合法。则通过（3-4+6)%6 = 5个元素
	return ((Q.rear - Q.front + MaxSize) % MaxSize);
}

//判断队列是否为空。队空条件：队头指针==队尾指针
bool QueueEmpty(SqQueue Q){
	return (Q.front == Q.rear);
}

//判断队列是否已满
bool QueueFull(SqQueue Q){
	return (Q.rear + 1) % MaxSize == Q.front;  //队列满
}

//入队：若循环队列Q未满，将value加入，使之成为新的队尾。
bool EnQueue(SqQueue& Q, QElemType value){
	if (!QueueFull(Q)){   		//如果队列没满
		Q.data[Q.rear] = value; //将入队元素放入Q.rear所指向的空间中
		Q.rear = (Q.rear + 1) % MaxSize;	//队尾指针+1
		return true;
	}
	return false; 	//队列已满，入队失败
}

//出队：若循环队列Q非空，删除队头元素，并用value返回。
bool DeQueue(SqQueue& Q, QElemType &value){
	if (!QueueEmpty(Q)){  			//如果队列非空
		value = Q.data[Q.front];	//将出栈元素保存到value中
		Q.front = (Q.front + 1) % MaxSize; //队头指针+1
		return true; 
	}
	return false; //队列为空，出队失败
}

//取队头元素
QElemType GetHead(SqQueue Q){
	if (!QueueEmpty(Q)){ 			//队列不为空
		return Q.data[Q.front];  //返回队头指针元素
	}
	return false;
}

//遍历打印队列元素
bool QueuePrint(SqQueue Q) {
	//这里注意！！！ 如果要用这种方法，参数列表一定不能用'SqQueue &value'引用，
	//因为使用&会修改真正的Q.front和Q.rear空间地址,影响原函数的指针位置，和后面的函数调用。
	if (Q.front == Q.rear)		//空队列
		return false;

	while (Q.front != Q.rear){
		cout << Q.data[Q.front] << "  ";
		Q.front = (Q.front + 1) % MaxSize;
	}
	cout<<endl;
	return true;

	//方案二，由于额外创建了临时变量用来遍历队列，不管用不用'&Q'都不会影响原队列中front与rear的位置
	//if (!QueueEmpty(Q))   //队列非空
	//{
	//	QElemType temp = Q.front; //创建临时变量，位置与队头相同
	//	while (temp != Q.rear)
	//	{
	//		cout << Q.data[temp] << " ";  //输出temp所处位置的元素
	//		temp = (temp + 1) % MaxSize; //temp位置上移加 1 
	//	}
	//	cout << endl;
	//	return true;
	//}
	//return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153

请输入要入队的元素个数： 5
队列输出顺序：0 1 2 3 4
队头元素为：0
队列长度为：5
—出队一个元素后—
出队元素为：0
1 2 3 4
出队后队头元素为：1
出队后队列长度为：4
Press any key to continue . . .