队列是特殊的线性表，其所有插入均限定在表的一端，而所有的删除则限定在表的另一端。允许插入的一端称队尾，允许删除的一端称队首

特点：先进先出（FIFO）

在队列的实现中，最常见的就是循环队列，循环队列实质上是顺序存储结构。循环队列是把顺序队列首尾相连，把存储队列元素的表从逻辑上看成一个环，成为循环队列。

当添加一个元素时，rear = (rear + 1) % MAXSIZE;

当删除一个元素时，front = (front + 1) % MAXSIZE;

当 front = rear 时，队列可能满，也可能空

  • 满，当队列添加元素到 rear 的下一个元素是 front 的时候，也就是转圈子要碰头了，我们就认为队列满了，(rear + 1) % MAXSIZE = front
  • 空，当队列删除元素到 front = rear 的时候，我们认为队列空了

​ 

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
#include<iostream>
#include<iomanip>
using namespace std;

//循环列表的类定义
typedef int ElemType;//假设栈元素为整型
const int MAXSIZE = 100;
class CSeQueue {
private:
	ElemType elem[MAXSIZE];
	int front;//头指针指向队列头元素的前一位置
	int rear;//尾指针指向队尾元素
public:
	CSeQueue() { front = 0; rear = 0; }//初始化空队列
	~CSeQueue() {}
	int Empty();//判断循环队列是否为空
	void Display();//输出队列
	void AddlQ(ElemType x);//入队
	ElemType DelQ();//出队
	ElemType GetFront();//取队首元素，不出队
};

//************************************
// Method:    Empty
// FullName:  CSeQueue::Empty
// Access:    public 
// Returns:   int
// Function: 判断循环队列是否为空
//************************************
int CSeQueue::Empty() {
	if (rear == front)
		return 1;
	return 0;
}


//************************************
// Method:    AddlQ
// FullName:  CSeQueue::AddlQ
// Access:    public 
// Returns:   void
// Function: 入队操作
// Parameter: ElemType x
//************************************
void CSeQueue::AddlQ(ElemType x) {
	//判断是否队满
	if ((rear + 1) % MAXSIZE == front)
		cout << "Queue is full" << endl;
	else {
		rear = (rear + 1) % MAXSIZE;//尾指针加1，添加一个元素
		elem[rear] = x;
	}
}


//************************************
// Method:    DelQ
// FullName:  CSeQueue::DelQ
// Access:    public 
// Returns:   ElemType
// Function: 出队操作
//************************************
ElemType CSeQueue::DelQ() {
	if (front == rear) {//判断队列是否为空
		cout << "Queue is empty" << endl;
		return -1;
	}
	else {
		front = (front + 1) % MAXSIZE;//删除一个元素
		return elem[front];
	}
}

void CSeQueue::Display() {
	cout << "PrintOut Data:";
	if (front == rear) {//判断队列是否为空
		cout << "Queue is empty" << endl;
		return ;
	}
	else {
		for (int k = front + 1; k <= rear; k++)
			cout << setw(6) << elem[k];
		cout << endl;
	}
}

//************************************
// Method:    GetFront
// FullName:  CSeQueue::GetFront
// Access:    public 
// Returns:   ElemType
// Function: 取队首元素，不出队
//************************************
ElemType CSeQueue::GetFront() {
	ElemType x;
	if (front == rear) {//判断队列是否为空
		cout << "Queue is empty" << endl;
		x = -1;
	}
	else
		x = elem[(front + 1) % MAXSIZE];
	return x;
}
int main()
{
	ElemType x = 0;
	CSeQueue CQueue;
	CQueue.AddlQ(1);
	CQueue.AddlQ(2);
	CQueue.AddlQ(3);
	CQueue.AddlQ(4);
	CQueue.AddlQ(5);
	x = CQueue.GetFront();
	cout << x << endl;
	CQueue.Display();
	CQueue.DelQ();
	CQueue.DelQ();
	CQueue.DelQ();
	CQueue.DelQ();
	x = CQueue.GetFront();
	cout << x << endl;
	CQueue.Display();
	return 0;
}