---------------------siwuxie095
队列
所谓 队列，从特点上来讲，是一个先入先出的数学模型，
即 First In First Out，简称为 FIFO
如：在排队买票时，先来的，就排在队列的前面，后来的，
就排在队列的后面，于是就形成了队列
队列排在最前面的称之为 队头，队列排在最后面的称之为 队尾，
也叫 队列头 或 队列尾
最关键的是，售票员一定是从队列头开始卖票的
当买票的人买到票之后，就会逐个的离开这个队列
显然，先到的人一定是先买到票的，然后离开，后到的人一定是
后买到票的，然后离开，也即 先入先出，这个模型在数据结构上
就称之为 队列
从队列的形式上来说，分为两种：一种是普通队列，一种是环形队列
普通队列
假如左方是售票员所在的窗口，右方是排队买票的人的队列：
当只有一个人买票时，他肯定排在最前面，这时，他既是 队列头，
也是 队列尾
当再来人买票时，就排在前面那个人的后面，再来人 … 再来人 …
一直排 … 总之，在队列的最后一个就是 队列尾
显然，队列的长度肯定是有一个限度的，如：排到一定程度就没法
排队了，对应到计算机中，就是排到一定程度，后面的内存就无法
再分配了
对于处理来说：
前面的售票员肯定是会给第一个来排队的人卖票，卖给他票之后，
他就离开了，于是给第二个人卖票，他拿到票之后，也离开了 …
于是就产生了两种情况：
1）在队列头的那个人买完票离开后，后面的人往前依次进一位，
第二个人就变成了队列头，他买完票离开后，所有人再往前进一
位 …
2）售票员拿着票，给第一个位置上的人卖票，卖给他票之后，他
离开了，第二个位置上的人就是队列头。售票员走动，卖票给第二
个位置上的人之后，他也离开了，售票员接着走动，卖票给第三个
位置上的人 … 售票员一直走到队列尾，最后一个人拿票离开了 …
此时，如果还有人过来排队，排的就是后面的位置
对于普通队列来说，存在着这样一些缺点：
如果是第二种情况，就显得浪费了前面的位置，因为这些位置一旦
处理完之后，人一离开，剩下的人都只能往后排，前面的位置就被
浪费了，对应到计算机中，这些位置就是一个个的内存，即 这些内
存就被浪费了
如果是第一种情况，虽然内存没有浪费，每次处理完一个，后面的
都需要往前移动一位，处理起来效率就会低，速度就会慢
如果想要将普通队列的缺点弥补，怎么办呢？就可以采用 环形队列
环形队列
所谓 环形队列，即 队列成一个环，它的好处就是屏蔽掉了
普通队列的缺点，如下：
对于环形队列来说，它仍然是有一个 队列头 和一个 队列尾 的
当队列中只有一个元素时，它既是 队列头，也是 队列尾
当再有元素进来，新元素就是 队列尾，再有元素进来 … 再 …
对于环形队列是有 顺时针 和 逆时针 之分的，上图中采用的是
顺时针
当顺时针去看这个结构时，发现：对于整个队列空间来说，还
有两个空间没被占据，如果再有两个元素把两个空间都占满了，
那么队列头和队列尾就顶到了一起，此时，如果再想排队的元
素就没法进来了
显然，环形队列中的所有内存，在使用上是非常高效的，而且
在处理时，对于队列头，处理一个，队列头就变到了第二个位
置，再处理一个，队列头就变到了第三个位置 … 如果队列尾后
再有元素来排队，就可以使用前面腾开的位置往后排
可见：使用环形队列是可以充分的利用每一个内存空间的
队列的用途
从现实生活中来说，队列的用途是非常广泛的，最为典型的
就是 自动排号机
大家到银行、移动营业厅等地方都能遇到，假设我们去打一个单子，
其中：编号 XXX 肯定就是指你是今天的第几位，用户类型 即 表明
你是普通队，还是 VIP 队，取号时间 即 你什么时间取的号 …
程序 1：
MyQueue.h：
|
#ifndef MYQUEUE_H #define MYQUEUE_H
//环形队列 class MyQueue { public: MyQueue(int queueCapacity); //创建队列 virtual ~MyQueue(); //销毁队列 void ClearQueue(); //清空队列 bool QueueEmpty() const; //判空队列 bool QueueFull() const; //判满队列 int QueueLength() const; //队列长度 bool EnQueue(int element); //新元素入队 bool DeQueue(int &element); //首元素出队 void QueueTraverse(); //遍历队列
private: int *m_pQueue; //队列数组指针 int m_iQueueLen; //队列元素个数即队列长度 int m_iQueueCapacity; //队列数组容量 int m_iHead; //队头 int m_iTail; //队尾 };
//使用 C++ 实现队列和使用 C 语言实现队列，略有不同 //但思想上是大同小异的
#endif |
MyQueue.cpp：
|
#include "MyQueue.h" #include "stdlib.h" #include <iostream> using namespace std;
//构造函数，创建一个队列 MyQueue::MyQueue(int queueCapacity) { //队列容量 m_iQueueCapacity = queueCapacity; //初始化时，队头和队尾都为 0 m_iHead = 0; m_iTail = 0; //初始化时，队列元素个数或队列长度为 0 m_iQueueLen = 0; //用数组来存放该队列，从堆中申请内存有可能失败，暂不做处理 m_pQueue = new int[m_iQueueCapacity]; }
//析构函数，销毁整个队列 MyQueue::~MyQueue() { //回收内存 delete[]m_pQueue; //将指针置于安全状态 m_pQueue = NULL; }
//清空队列，即让队列还原成初始状态， //也就是执行构造函数时创建队列的那个样子, //只不过清空队列后，它的内存还保持着，元素不在了 // //只需将队头、队尾、队列长度置为 0 即可 //不必重置容量和也不必对已经分配到的内存做相应的处理 // //显然，ClearQueue() 中的代码和构造函数中部分重复 //可以将构造函数中相应的代码替换为 ClearQueue() 的调用 void MyQueue::ClearQueue() { m_iHead = 0; m_iTail = 0; m_iQueueLen = 0; }
//判断队列是否为空 bool MyQueue::QueueEmpty() const { //通过队列长度来进行判断 if (m_iQueueLen == 0) { return true; } else { return false; }
//或使用如下方法判断 //return m_iQueueLen == 0 ? true : false; }
//判断队列是否为满 bool MyQueue::QueueFull() const { //当队列长度与队列容量相同时为满 if (m_iQueueLen == m_iQueueCapacity) { return true; } return false;
//或使用如下方法判断 //return m_iQueueLen == m_iQueueCapacity ? true:false; }
//获取队列的长度 int MyQueue::QueueLength() const { return m_iQueueLen; }
//新元素插入到队列中 bool MyQueue::EnQueue(int element) { //如果队列已满，自然就不能插入了 if (QueueFull()) { return false; } //这里的 else 加不加均可 else { //新元素总是从队尾入队，即从队尾插入 m_pQueue[m_iTail] = element;
//新元素插入后，队尾移动到后一个位置 //因为队尾一直要指向要插入的那个位置 m_iTail++;
//m_iTail++ 后需要对队列总容量取余 //因为有可能会超出容量而报错，当队尾指向环形队列的 //最后一个位置时，下一次指向应该是第 0 个位置 //注意：这里是用数组来实现的环形队列 m_iTail = m_iTail % m_iQueueCapacity;
//每插入一个元素，都让队列长度加 1 m_iQueueLen++;
return true; } }
//元素出队：一个元素要想出队，肯定是从首元素开始出队的 //首元素即队头所指向的那个元素 bool MyQueue::DeQueue(int &element) { //如果队列为空，自然也无元素可出了 if (QueueEmpty()) { return false; } //这里的 else 加不加均可 else { //将队头所指向的元素赋值为传入进来的参数 element //注意：这个 element 必须是一个引用 element = m_pQueue[m_iHead];
//首元素移出后，队头要向后移动一位 //指向下一个位置，以便于下次正常的出队 m_iHead++;
//m_iHead++ 后同样要取余并赋值给本身 m_iHead = m_iHead % m_iQueueCapacity;
//每删除一个元素，都让队列长度减 1 m_iQueueLen--;
return true; } }
//对环形队列中的每一个元素进行遍历 void MyQueue::QueueTraverse() { //遍历时，让第一个元素指向队头 //m_iQueueLen + m_iHead 使得无论队头如何增长， //在循环时都不受影响，保证循环次数不出错 for (int i = m_iHead; i < m_iQueueLen + m_iHead; i++) { //使用 i 对队列容量取余 cout << m_pQueue[i%m_iQueueCapacity] << endl; } cout << endl; } |
main.cpp：
|
#include "stdlib.h" #include "MyQueue.h" #include <iostream> using namespace std;
//环形队列检测 int main() { //初始化队列容量为 4 MyQueue *p = new MyQueue(4);
p->EnQueue(10); p->EnQueue(12); p->EnQueue(16); p->EnQueue(18); p->EnQueue(20);//插入 20 是失败的，因为容量是4 p->QueueTraverse();
int e = 0; p->DeQueue(e); cout << e << endl; p->DeQueue(e); cout << e << endl; cout << endl; p->QueueTraverse();
p->ClearQueue(); p->QueueTraverse();
p->EnQueue(20); p->EnQueue(30); p->QueueTraverse();
delete p; p = NULL;
system("pause"); return 0; } |
运行一览：
程序 2：
Customer.h：
|
#ifndef CUSTOMER_H #define CUSTOMER_H
#include <string> using namespace std;
class Customer { public: Customer(string name = "", int age = 0); void printInfo() const;
private: string m_strName; int m_iAge; };
#endif |
Customer.cpp：
|
#include "Customer.h" #include <iostream>
Customer::Customer(string name, int age) { m_strName = name; m_iAge = age; }
void Customer::printInfo() const { cout << "姓名：" << m_strName << endl; cout << "年龄：" << m_iAge << endl; cout << endl; } |
MyQueue.h：
|
#ifndef MYQUEUE_H #define MYQUEUE_H #include "Customer.h" //环形队列 class MyQueue { public: MyQueue(int queueCapacity); //创建队列 virtual ~MyQueue(); //销毁队列 void ClearQueue(); //清空队列 bool QueueEmpty() const; //判空队列 bool QueueFull() const; //判满队列 int QueueLength() const; //队列长度 bool EnQueue(Customer element); //新元素入队 bool DeQueue(Customer &element);//首元素出队 void QueueTraverse(); //遍历队列
private: Customer *m_pQueue; //Customer类型的队列指针 int m_iQueueLen; //队列元素个数即队列长度 int m_iQueueCapacity; //队列数组容量 int m_iHead; //队头 int m_iTail; //队尾 };
//使用 C++ 实现队列和使用 C 语言实现队列，略有不同 //但思想上是大同小异的
#endif |
MyQueue.cpp：
|
#include "MyQueue.h" #include "stdlib.h" #include <iostream> using namespace std;
//构造函数，创建一个队列 MyQueue::MyQueue(int queueCapacity) { //队列容量 m_iQueueCapacity = queueCapacity; //初始化时，队头和队尾都为 0 m_iHead = 0; m_iTail = 0; //初始化时，队列元素个数或队列长度为 0 m_iQueueLen = 0; //用数组来存放该队列，从堆中申请内存有可能失败，暂不做处理 m_pQueue = new Customer[m_iQueueCapacity]; }
//析构函数，销毁整个队列 MyQueue::~MyQueue() { //回收内存 delete[]m_pQueue; //将指针置于安全状态 m_pQueue = NULL; }
//清空队列，即让队列还原成初始状态， //也就是执行构造函数时创建队列的那个样子, //只不过清空队列后，它的内存还保持着，元素不在了 // //只需将队头、队尾、队列长度置为 0 即可 //不必重置容量和也不必对已经分配到的内存做相应的处理 // //显然，ClearQueue() 中的代码和构造函数中部分重复 //可以将构造函数中相应的代码替换为 ClearQueue() 的调用 void MyQueue::ClearQueue() { m_iHead = 0; m_iTail = 0; m_iQueueLen = 0; }
//判断队列是否为空 bool MyQueue::QueueEmpty() const { //通过队列长度来进行判断 if (m_iQueueLen == 0) { return true; } else { return false; }
//或使用如下方法判断 //return m_iQueueLen == 0 ? true : false; }
//判断队列是否为满 bool MyQueue::QueueFull() const { //当队列长度与队列容量相同时为满 if (m_iQueueLen == m_iQueueCapacity) { return true; } return false;
//或使用如下方法判断 //return m_iQueueLen == m_iQueueCapacity ? true:false; }
//获取队列的长度 int MyQueue::QueueLength() const { return m_iQueueLen; }
//新元素插入到队列中 bool MyQueue::EnQueue(Customer element) { //如果队列已满，自然就不能插入了 if (QueueFull()) { return false; } //这里的 else 加不加均可 else { //新元素总是从队尾入队，即从队尾插入 m_pQueue[m_iTail] = element;
//新元素插入后，队尾移动到后一个位置 //因为队尾一直要指向要插入的那个位置 m_iTail++;
//m_iTail++ 后需要对队列总容量取余 //因为有可能会超出容量而报错，当队尾指向环形队列的 //最后一个位置时，下一次指向应该是第 0 个位置 //注意：这里是用数组来实现的环形队列 m_iTail = m_iTail % m_iQueueCapacity;
//每插入一个元素，都让队列长度加 1 m_iQueueLen++;
return true; } }
//元素出队：一个元素要想出队，肯定是从首元素开始出队的 //首元素即队头所指向的那个元素 bool MyQueue::DeQueue(Customer &element) { //如果队列为空，自然也无元素可出了 if (QueueEmpty()) { return false; } //这里的 else 加不加均可 else { //将队头所指向的元素赋值为传入进来的参数 element //注意：这个 element 必须是一个引用 element = m_pQueue[m_iHead];
//首元素移出后，队头要向后移动一位 //指向下一个位置，以便于下次正常的出队 m_iHead++;
//m_iHead++ 后同样要取余并赋值给本身 m_iHead = m_iHead % m_iQueueCapacity;
//每删除一个元素，都让队列长度减 1 m_iQueueLen--;
return true; } }
//对环形队列中的每一个元素进行遍历 void MyQueue::QueueTraverse() { //遍历时，让第一个元素指向队头 //m_iQueueLen + m_iHead 使得无论队头如何增长， //在循环时都不受影响，保证循环次数不出错 for (int i = m_iHead; i < m_iQueueLen + m_iHead; i++) { cout << "前面还有 " << (i - m_iHead) << " 人" << endl; //使用 i 对队列容量取余 m_pQueue[i%m_iQueueCapacity].printInfo(); } cout << endl; } |
main.cpp：
|
#include "stdlib.h" #include "MyQueue.h" #include <iostream> using namespace std;
//队列其实是可以存放任何数据类型 //队列 MyQueue 也可以使用类模板来写 int main() { //初始化队列容量为 4 MyQueue *p = new MyQueue(4);
Customer c1("zhangsan",20); Customer c2("lisi", 30); Customer c3("wangwu", 24);
p->EnQueue(c1); p->EnQueue(c2); p->EnQueue(c3); p->QueueTraverse();
Customer c4("", 0); p->DeQueue(c4); c4.printInfo(); cout << endl; p->QueueTraverse();
delete p; p = NULL;
system("pause"); return 0; } |
运行一览：
【made by siwuxie095】