C++数据结构之队列详解_c++队列

1.队列的简述

队列也是一种收限制的线性表，其特点是在一端进行插入的时，再另一端进行出队列的操作（删除操作）。把允许插
入操作的一端叫做队尾，允许删除操作的一端叫做队头。队列就像超市排队结账的人群，排在收银台一端的优先结账
离开，后面的依次排队并一直收银台前进，每出队列一个，向前走一步。
向队列插入元素称为入队，从队列中删除元素称为出队。不包含任何数据的队列称为空队列，队列也被称为先进先出
（First In First Out：FIFO）的线性表，换句话说，插入数据只能在队尾进行，删除操作只能在队头进行。
（后面还会有特殊情况：双端队列）
1
2
3
4
5
6

队头填充进四个元素

2.队列的基本顺序存储代码：

#define MaxSize 10//队列的初始化尺寸

template<typename T>
class SeqQueue 
{
public:
	SeqQueue();
	~SeqQueue();

public:
	bool EnQueue(const T& e);//入队列
	bool DeQueue(T& e);//出队列
	bool GetHead(T& e);//读取头元素
	void ClearQueue();//清空队列
	void DispList();//输出顺序队列中的所有元素
	int ListLength();//获取队列长度（元素个数）
	bool IsEmpty();//判断队列是否为空
	bool IsFull();//判断队列是否已满

private:
	T* m_data;
	int m_front;//队头指针(数组下标)
	int m_rear;//队尾指针（数组下标）,允许出队的那一端
};

template<typename T>
SeqQueue<T>::SeqQueue() 
{
	m_data = new T[MaxSize];
	m_front = 0;
	m_rear = 0;
}

template<typename T>
SeqQueue<T>::~SeqQueue() 
{
	delete[] m_data;
}

template<typename T>
bool SeqQueue<T>::EnQueue(const T& e)
{
	if (IsFull() == true) 
	{
		cout << "队列满了，不能再进行入队列操作了！" << endl;
		return false;
	}
	m_data[m_rear] = e;
	m_rear++;
	return true;
}

template<typename T>
bool SeqQueue<T>::DeQueue(T& e)
{
	if (IsEmpty() == true) 
	{
		cout << "当前队列为空，不能进行出队列操作!" << endl;
		return false;
	}
	e = m_data[m_front];
	m_front++;
	return true;
}

template<typename T>
bool SeqQueue<T>::GetHead(T& e) 
{
	if (IsEmpty() == true) 
	{
		cout << "队列为空，无法进行获取头元素操作!" << endl;
		return false;
	}
	e = m_data[m_front];
	return true;
}

template<typename T>
void SeqQueue<T>::DispList() 
{
	for (int i = 0; i < m_rear;i++) 
	{
		cout << m_data[i] << " ";
	}
	cout << endl;
}

template<typename T>
int SeqQueue<T>::ListLength()
{
	return m_rear - m_front;
}

template<typename T>
bool SeqQueue<T>::IsEmpty() 
{
	if (m_front == m_rear) 
	{
		return true;
	}
	return false;
}

template<typename T>
bool SeqQueue<T>::IsFull() 
{
	if (m_rear >= _Maximum) 
	{
		return true;
	}
	return false;
}

template<typename T>
void SeqQueue<T>::ClearQueue() 
{
	m_rear = m_front = 0;
}
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

此时思考一个问题，当删除元素时（元素出队列时）会出现假饱和的情况，如上图m_data[0]和m_data[1]再进行出队列操作之后，这两个位置可以容纳新的元素，但m_rear没有回到原本的m_data[0]位置，因此需要引入一个新的队列结构，环形队列，m_rear这个位置可以从0到9再到0,周而复始不停的重复，保存的数据像在一个环状空间一样，这种头尾相连的队列结构就叫循环队列。

3.优化普通队列，成为可以循环接受数据的循环队列

循环队列代码如下：

#define MaxSize 10

template<typename T>
class RoundQueue
{
public:
	RoundQueue();
	~RoundQueue();

public:
	bool EnQueue(const T& e);//入队列
	bool DeQueue(T& e);//出队列
	bool GetHead(T& e);//读取头元素
	void ClearQueue();//清空队列
	void DispList();//输出顺序队列中的所有元素
	int ListLength();//获取队列长度（元素个数）
	bool IsEmpty();//判断队列是否为空
	bool IsFull();//判断队列是否已满

private:
	T m_data;
	int m_front;//队头指针(数组下标)
	int m_rear;//队尾指针（数组下标）,允许出队的那一端
	char m_tag;
};

template<typename T>
RoundQueue<T>::RoundQueue()
{
	m_data = new T[MaxSize];
	m_front = 0;
	m_rear = 0;
	m_tag = 0;//加入表示栈是否满的状态
}

template<typename T>
RoundQueue<T>::~RoundQueue()
{
	delete[] m_data;
}

template<typename  T>
bool RoundQueue<T>::EnQueue(const T& e) 
{
	if (IsFull () == true)
	{
		cout << "队列满了，不能再进行入队列操作了！" << endl;
		return false;
	}
	m_tag = 1;
	m_data[m_rear] = e;
	m_rear = (m_rear + 1) % MaxSize;
	return true;
}

template<typename T>
bool RoundQueue<T>::DeQueue(T& e) 
{
	if (IsEmpty() == true)
	{
		cout << "当前队列为空，不能进行出队列操作!" << endl;
		return false;
	}
	m_tag = 0;
	e = m_data[m_front];
	m_front = (m_front + 1) % MaxSize;
	return true;
}

template<typename T>
bool RoundQueue<T>::GetHead(T& e)
{
	if (IsEmpty() == true)
	{
		cout << "队列为空，无法进行获取头元素操作!" << endl;
		return false;
	}
	e = m_data[m_front];
	return true;
}

template<typename T>
void RoundQueue<T>::DispList()
{
	for (int i = m_front;i != m_rear)
	{
		cout << m_data[i] << " ";
		i = (i + 1) % MaxSize;
	}
	cout << endl;
}

template<typename T>
bool RoundQueue<T>::IsFull()
{
	if (m_rear == m_front && tag == 0)
	{
		return true;
	}
	return false;
}

template<typename T>
int RoundQueue<T>::ListLength()
{
	return (m_rear + MaxSize - m_front) % MaxSize;
}

template<typename T>
bool RoundQueue<T>::IsEmpty()
{
	if (m_front == m_rear && tag == 0)
	{
		return true;
	}
	return false;
}

template<typename T>
void RoundQueue<T>::ClearQueue()
{
	m_rear = m_front = m_tag = 0;
}
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

循环队列队列满的情况，如下图：

4.队列的链式结构实现

和前面所有的数据结构一样，队列也有链式结构

空队列的情况：

插入两个元素之后的队列：

实现代码如下图所示：

template<typename T>
struct QueueNode 
{
	T data;//数据域
	QueueNode<T>* next;//指针域，指向下一个节点
};

template<typename T>
class LinkQueue 
{
public:
	LinkQueue();
	~LinkQueue();

public:
	bool EnQueue(const T& e);//入队
	bool DeQueue(T& e);//出队
	bool GetHead(T& e);//读取头元素
	void DispList();//输出链式队列中的所有元素
	int ListLength();//获取链式队列的长度（链式表元素个数）
	bool IsEmpty();//判断链式队列是否为空

private:
	QueueNode<T>* m_front;//头指针，这一端允许出队（删除）
	QueueNode<T>* m_rear;//尾指针记录入队
	int m_length;
};

template<typename T>
LinkQueue<T>::LinkQueue() 
{
	m_front = new QueueNode<T>;
	m_front->next = nullptr;
	m_rear = m_front;
	m_length = 0;
}

template<typename T>
LinkQueue<T>::~LinkQueue() 
{
	QueueNode<T>* pnode = m_front->next;
	QueueNode<T>* ptmp;
	while (pnode != nullptr)
	{
		ptmp = pnode;
		pnode = pnode->next;
		delete ptmp;
	}
	delete m_front;
	m_front = m_rear = nullptr;
	m_length = 0;
}

template<typename T>
bool LinkQueue<T>::EnQueue(const T& e) 
{
	QueueNode<T>* node = new QueueNode<T>;
	node->data = e;
	node->next = nullptr;

	m_rear->next = node;//新节点插入到头指针之后
	m_rear = node;//更新队尾指针的位置
	m_length++;
	return true;
}

template<typename T>
bool LinkQueue<T>::DeQueue(T& e) 
{
	if (IsEmpty() == true) 
	{
		cout << "当前链式队列为空，无法进行出队列操作!" << endl;
		return false;
	}
	QueueNode<T>* p_willdel = m_front->next;
	e = p_willdel->data;
	m_front->next = p_willdel->next;
	if (m_rear == p_willdel) //队列中只有一个元素，删除之后，m_rear和m_front相连
	{
		m_rear = m_front;
	}
	delete p_willdel;
	m_length--;
	return true;
}

template<typename T>
void LinkQueue<T>::DispList() 
{
	QueueNode<T>* p = m_front->next;
	while (p != nullptr) 
	{
		cout << p->data << " ";
		p = p->next;
	}
	cout << endl;
}

template<typename T>
int LinkQueue<T>::ListLength() 
{
	return m_length;
}

template<typename T>
bool LinkQueue<T>::IsEmpty() 
{
	if (m_front == m_rear) 
	{
		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

5.双端队列

前面的几种队列都可以看成普通的队列，还有一种变形的队列-双端队列。双端队列就是允许两端插入和删除数据。STL中提供的名字叫做deque的容器，就是一个典型的双端队列。双端队列的存取如图所示：

也可以对双端队列进行一系列的限制，可以有输入受限的的双端队列和输出受限的双端队列，如图为输入受限的双端队列，只能一端输入，两端输出：

也可也一端输出，两端输入的双端队列，如图：

代码实现如下：

// 节点
template<class T>
class Node
{
public:
	T data;
	Node<T> *left;
	Node<T> *right;
	Node() {
		data= 0;
		left = right = nullptr;
	}
	Node(T n) {
		data= n;
		left = right = nullptr;
	}
};
// 双端队列
template<class T>
class double_ended_queue {
public:
	Node<T>*queue_left, *queue_right;
	int num;
	int size;
	
	double_ended_queue() {
		queue_left=queue_right = nullptr;
		num = 0;
		size = 10;
	}
	
	void IsEmpty();
	void IsFull();
	void AddLeft(T);
	void AddRight(T);
	void DeleteLeft();
	void DeleteRight();
	void Print();
};

template<class T>
void double_ended_queue<T>::IsEmpty() {
	num == 0 ? cout << "YES" << endl : cout << "NO" << endl;
}

template<class T>
void double_ended_queue<T>::IsFull() {
	num == size ? cout << "YES" << endl : cout << "NO" << endl;
}

template<class T>
void double_ended_queue<T>::Print() {
	if (num == 0)
	{
		cout << "EMPTY" << endl;
		return;
	}
	Node<T>*p = queue_left;
	for (int i = 0; i < num-1; i++) {
		cout << p->data << " ";
			p = p->right;
	}
	cout << p->data << endl;
}

template<class T>
void double_ended_queue<T>::AddLeft(T n) {
	Node<T>*p = new Node<T>(n);
	if (num == 0)
	{
		queue_left =queue_right=p;
		queue_left->left =queue_left->right=nullptr;
		num++;
	}
	else{
		if (num == size)
		{
			cout << "FULL  ";
			Print();
			return;
		}
		queue_left->left = p;
		p->right = queue_left;
		queue_left = queue_left->left;
		num++;
	}
	Print();
}

template<class T>
void double_ended_queue<T>::AddRight(T n) {
	Node<T>*p = new Node<T>(n);
	if (num == 0)
	{
		queue_left = queue_right = p;
		queue_right->left = queue_right->right = nullptr;
		num++;
	}
	else {
		if (num == size)
		{
			cout << "FULL  " ;
			Print();
			return;
		}
		queue_right->right = p;
		p->left = queue_right;
		queue_right = queue_right->right;
		num++;
	}
	Print();
}

template<class T>
void double_ended_queue<T>::DeleteLeft() {
	if (num == 0) {
		cout << "EMPTY" << endl;
		return;
	}
	Node<T>*p = queue_left->right;
	delete queue_left;
	queue_left = p;
	num--;
	Print();
}
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