C++数据结构——队列
参考博客：
1、队列（Queue）与栈一样，是一种线性存储结构，它具有如下特点：
（1）队列中的数据元素遵循“先进先出”（First In First Out）的原则，简称FIFO结构；
（2）在队尾添加元素，在队头删除元素。
2、队列的相关概念：
（1）队头与队尾： 允许元素插入的一端称为队尾，允许元素删除的一端称为队头；
（2）入队：队列的插入操作；
（3）出队：队列的删除操作。
3、队列的操作：
（1）入队： 通常命名为push()
（2）出队： 通常命名为pop()
（3）求队列中元素个数
（4）判断队列是否为空
（5）获取队首元素
4、队列的分类：
（1）基于数组的循环队列（循环队列）
（2）基于链表的队列（链队列）
5、实例分析
C++队列queue模板类的定义在<queue>头文件中,queue 模板类需要两个模板参数，一个是元素类型，一个容器类型，元素类型是必要的，容器类型是可选的，默认为deque 类型。C++队列Queue是一种容器适配器，它给予程序员一种先进先出(FIFO)的数据结构。
那么我们如何判断队列是空队列还是已满呢？
a、栈空： 队首标志=队尾标志时，表示栈空。
b、栈满 : 队尾+1 = 队首时，表示栈满。
使用标准库的队列时, 应包含相关头文件，在栈中应包含头文件： #include< queue> 。定义：queue< int > q;
-
q.empty() 如果队列为空返回true，否则返回false
-
q.size() 返回队列中元素的个数
-
q.pop() 删除队列首元素但不返回其值
-
q.front() 返回队首元素的值，但不删除该元素
-
q.push() 在队尾压入新元素
-
q.back() 返回队列尾元素的值，但不删除该元素
（1）基于数组的循环队列（循环队列）
以数组作为底层数据结构时，一般讲队列实现为循环队列。这是因为队列在顺序存储上的不足：每次从数组头部删除元素（出队）后，需要将头部以后的所有元素往前移动一个位置，这是一个时间复杂度为O（n）的操作。具体的示例图参考：http://www.cnblogs.com/QG-whz/p/5171123.html。
循环队列，可以把数组看出一个首尾相连的圆环，删除元素时将队首标志往后移动，添加元素时若数组尾部已经没有空间，则考虑数组头部的空间是否空闲，如果是，则在数组头部进行插入。参考博客：【c++版数据结构】之循环队列的实现，判断循环队列是“空”还是“ 满”，有两种处理方法：
- A. 设置状态标志位以区别空还是满
- B. 少用一个元素，约定“队头front在队尾rear的下一个位置（指的是环的下一个位置）”作为“满”的标志
C语言中，不能用动态分配的一维数组来实现循环队列，如果用户的应用程序中设有循环队列，则必须为它设定一个最大队列长度；如果用户无法预估所用队列的最大长度，则宜采用链队列。
定义front为队列头元素的位置，rear为队列尾元素的位置，MAXSIZE为循环队列的最大长度。注意以下几点，循环队列迎刃而解：
- A. 求元素的个数：(rear - front + MAXSIZE) % MAXSIZE
- B. front/rear指向逻辑的下一个空间 front =（front+1)%MAXSIZE，rear = (rear+1)%MAXSIZE
- C. 判空：front == rear
- D. 判满：(rear+1+MAXSZIE) == front
例子1、简单的队列操作
-
#include <queue>
-
#include <iostream>
-
using
namespace
std;
-
-
int main(){
-
queue<
int> q;
-
for (
int i =
0; i <
10; i++){
-
q.push(i);
-
}
-
if (!q.empty()){
-
cout <<
"队列q非空！" <<
endl;
-
cout <<
"q中有" << q.size() <<
"个元素" <<
endl;
-
}
-
cout <<
"队头元素为：" << q.front() <<
endl;
-
cout <<
"队尾元素为：" << q.back() <<
endl;
-
for (
int j =
0; j <
10; j++){
-
int tmp = q.front();
-
cout << tmp <<
" ";
-
q.pop();
-
}
-
cout <<
endl;
-
if (!q.empty()){
-
cout <<
"队列非空！" <<
endl;
-
}
-
system(
"pause");
-
return
0;
-
}
-
#include <iostream>
-
#include <queue>
-
#include <string>
-
using
namespace
std;
-
-
template <
typename T>
-
class LoopQueue
-
{
-
public:
-
LoopQueue(
int c =
10);
-
~LoopQueue();
-
bool isEmpty();
//队列的判空
-
int size();
//队列的大小
-
bool push(T t);
//入队列
-
bool pop();
//出队列
-
T front();
//队首元素
-
-
private:
-
int capacity;
-
int begin;
-
int end;
-
T*
queue;
-
};
-
-
-
template<
typename T>
-
LoopQueue<T>::LoopQueue(
int c =
10)
-
:capacity(c), begin(
0), end(
0),
queue(
nullptr)
-
{
-
queue =
new T[capacity];
-
};
-
-
template<
typename T>
-
LoopQueue<T>::~LoopQueue()
-
{
-
delete[]
queue;
-
}
-
-
template <
typename T>
-
bool LoopQueue<T>::isEmpty()
//判断循环队列是否为空
-
{
-
if (begin == end)
-
return
true;
-
return
false;
-
};
-
-
template<
typename T>
-
int LoopQueue<T>::size()
-
{
-
return (end - begin + capacity) % capacity;
//计算循环队列的长度
-
};
-
-
template<
typename T>
-
bool LoopQueue<T>::push(T t)
-
{
-
if (end +
1 % capacity == begin)
//判断队列是否已满
-
{
-
return
false;
-
}
-
queue[end] = t;
-
end = (end +
1) % capacity;
-
return
true;
-
};
-
-
template <
typename T>
-
bool LoopQueue<T>::pop()
//判断队列是否为空
-
{
-
if (end == begin)
-
{
-
return
false;
-
}
-
begin = (begin +
1) % capacity;
-
return
true;
-
};
-
-
template <
typename T>
-
T LoopQueue<T>::front()
-
{
-
if (end == begin)
-
{
-
return
false;
-
}
-
return
queue[begin];
-
};
-
-
int main()
-
{
-
LoopQueue<string> queue(6);
-
queue.push(
"one");
-
queue.push(
"two");
-
queue.push(
"three");
-
queue.push(
"four");
-
queue.push(
"five");
-
cout <<
"队列长度" <<
queue.size() <<
endl;
-
while (!
queue.isEmpty())
-
{
-
cout <<
queue.front() <<
endl;
-
queue.pop();
-
}
-
getchar();
-
//system("pause");
-
return
0;
-
}
运行结果：
（2）基于链表的队列（链队列）
链队列是基于链表实现的队列，它不存在数组的O(n)的元素移动问题或空间浪费问题。我们所要确定的就是链表哪头做队首，哪头做队尾。显然我们应该以链表头部为队首，链表尾部为队尾。存储一个指向队尾的指针，方便从链表尾插入元素；使用带头节点的链表，方便从链表头删除元素。
代码参考：链式队列的C++实现
-
#include <iostream>
-
#include <cstdlib>
-
using
namespace
std;
-
-
struct QNode //定义队列结点的数据结构
-
{
-
QNode *next;
//指针域,指向下一个结点
-
double data;
//数据域，存储队列信息
-
};
-
-
struct LinkQueue //定义队列的数据结构
-
{
-
QNode *front;
//队首指针,指向QNode类型的指针
-
QNode *rear;
//队尾指针
-
};
-
-
void InitQueue(LinkQueue &Q) //构造一个空的队列
-
{
-
QNode *q;
-
q =
new QNode;
//申请一个结点的空间
-
q->next =
NULL;
//当作头结点
-
//队首与队尾指针都指向这个结点，指针域为NULL
-
Q.front = q;
-
Q.rear = q;
-
}
-
-
int IsEmpty(LinkQueue &Q) //判断队列是否为空
-
{
-
if (Q.rear == Q.front)
-
return
0;
-
else
-
return
1;
-
}
-
-
void EnQueue(LinkQueue &Q, double e) //从队列尾部插入元素
-
{
-
QNode *p;
//新创建一个结点
-
p =
new QNode;
-
p->next =
NULL;
-
p->data = e;
//输入数据信息
-
//将新结点插入队列尾部
-
Q.rear->next = p;
-
Q.rear = p;
//设置新的尾结点
-
}
-
-
void DeQueue(LinkQueue &Q, double &e) //从队列首部删除一个结点
-
{
-
QNode *p;
-
p = Q.front->next;
-
e = p->data;
//保存要出队列的数据
-
Q.front->next = p->next;
//将下一个结点当作头结点后面链接的第一个结点
-
if (Q.rear == p)
//如果要删除的元素即为尾结点，则将头指针赋予尾指针，一同指向头结点，表示队列为空
-
Q.rear = Q.front;
-
delete p;
-
}
-
-
void DestoryQueue(LinkQueue &Q) //销毁一个队列
-
{
-
while (Q.front)
-
{
-
Q.rear = Q.front;
//从头节点开始，一个一个删除队列结点，释放空间
-
delete Q.front;
-
Q.front = Q.rear;
-
}
-
}
-
int main()
-
{
-
LinkQueue *Q;
//定义一个队列Q
-
Q =
new LinkQueue;
-
InitQueue(*Q);
-
cout <<
"开始往队列里输入数据，以-1作为结束符" <<
endl;
-
cout <<
"请输入一个数：" <<
endl;
-
double a, x;
-
cin >> a;
-
while (a !=
-1)
-
{
-
EnQueue(*Q, a);
-
cout <<
"请输入一个数：" <<
endl;
-
cin >> a;
-
}
-
//输出队列元素,队首->队尾
-
QNode *p;
-
p = Q->front->next;
-
if (p ==
NULL)
//如果为空表，直接退出
-
{
-
cout <<
"队列为空！" <<
endl;
-
return
0;
-
}
-
cout <<
"队列数据依次为：" <<
endl;
-
while (p !=
NULL)
-
{
-
cout << p->data <<
" ";
-
p = p->next;
-
}
-
cout <<
endl;
-
//删除队列元素
-
while (!IsEmpty(*Q))
-
{
-
DeQueue(*Q, x);
-
cout << x <<
" ";
-
}
-
//释放内存空间
-
delete Q->front;
-
delete Q;
-
system(
"pause");
-
return
0;
-
}
运行结果：
还可以参考代码：C++ 链队列和循环队列基本操作。
总结：
1、循环队列中判断队空的方法是判断front==rear，队满的方法是判断front=（rear+1）%MAXSIZE。（为什么不用一个length表示队长，当length==maxSize时表示队满，原因就是，在频繁的队列操作中，多出一个变量会大量的增加执行时间，所以不如浪费一个数组空间来得划算。）
2、用单链表表示的链式队列特别适合于数据元素变动较大的情形，而且不存在溢出的情况。
转载：https://blog.csdn.net/zichen_ziqi/article/details/80819939