数据结构【第六篇】队列 (queue) 的实现与讲解
数据结构【第六篇】队列 (queue) 的实现与讲解
引言
中午在食堂打饭，真是一个令人头疼的事情，去食堂的路上也总是步伐匆匆，为什么啊，这还用说，迟一点去，你就会知道什么叫做人山人海了，在食堂排队的时候，相比较学生来说，打饭阿姨毕竟是少数，在每个窗口都有人的时候，不免我们就得等待，直到前面的一个学生打完饭离开，后面排队的人才可以继续向前走，直到轮到自己，别提多费劲了，但是秩序和规则却是我们每个人都应该遵守的，也只能抱怨自己来的迟了
这种 “先进先出” 的例子就是我们所讲的基本数据结构之一 ”队列“
例子补充：用电脑的时候，有时候机器会处于疑似死机的状态， 鼠标点什么似乎都没有用，双击任何快捷方式都不动，就当你失去耐心，打算reset的时候，突然它就像酒醒了一样，把你刚才点击的所有操作全部按照顺序执行了一遍，这其实是因为操作系统中的多个程序隐需要通过一个通道输出，而按照先后次序排队等待造成的 ——《大话数据结构》
队列的基本定义
定义：队列是一种只允许在一段进行删除操作，在另一端进行插入操作的线性表
允许插入的一段称作队尾 (rear)，允许删除的的一端称为队头 (front)
队列的数据元素又叫做队列元素，在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队 ，也正是因为队列只允许在一段插入，另一端删除，所以这也就是我们前面例子中体现出来的先进先出 (FIFO-first in first out) 的概念
补充：除此之外，还有的队列叫做双端队列，也就是可以在表的两边进行插入和删除操作的线性表 双端队列分类：
- 输出受限的双端队列：删除操作限制在表的一段进行，而插入操作允许早表的两端进行
- 插入操作限制在表的一段进行，而删除操作允许在表的两端进行
队列的抽象数据类型
#ifndef _QUEUE_H_
#define _QUEUE_H_
#include <exception>
using namespace std;
// 用于检查范围的有效性
class outOfRange:public exception {
public:
const char* what()const throw() {
return "ERROR! OUT OF RANGE.\n";
}
};
// 用于检查长度的有效性
class badSize:public exception {
public:
const char* what()const throw() {
return "ERROR! BAD SIZE.\n";
}
};
template <class T>
class Queue {
public:
//判队空
virtual bool empty() const = 0;
//清空队列
virtual void clear() = 0;
//求队列长度
virtual int size() const = 0;
//入队
virtual void enQueue(const T &x) = 0;
//出队
virtual T deQueue() = 0;
//读队头元素
virtual T getHead() const = 0;
//虚析构函数
virtual ~Queue(){}
};
#endif 循环队列
队列作为一个特殊的线性表，自然也有着顺序以及链式存储两种方式，我们先来看看它的顺序存储方式——循环队列
在队列的顺序存储中，我们除了创建一个具有一定空间的数组空间外，还需要两个指针，分别指向队列的前端和微端，下面的代码中，我们选择将队头指针指向头元素的前一个位置，队尾指针指向队尾元素（当然这不是唯一的方式，还可以将头指针指向头元素，队尾指针指向队尾元素的后一个位置，原理是基本一致的）
为什么要这么做，并且为什么这种存储我们叫做循环队列？
我们一步步分析一下：
我们先按照我们一般的想法画出队列元素进出队的过程，例如队列元素出队
这样的设想，也就是根据我们前面食堂排队的例子画出来的，但是我们可以清晰的看到，当a0出队后，a0后的元素全部需要前移，将空位补上，但我们在计算机中讲究性能二字，如何可以提高出队的性能呢？
循环队列就这样被设计出来了，我们如果不再限制队头一定在整个空间的最前面，我们的元素也就不需要集体移动了
问题一
这个时候我们就需要考虑这样的问题了：
① 如何为了解决只有一个元素的时候，队头和队尾重合使得处理变得麻烦？
- 这时我们前面提到的两个指针就派上用场了（队头指针指向头元素的前一个位置，队尾指针指向队尾元素）当头尾指针相等的时候，代表是空队列
问题二
但是有一个大问题出现了 ！
如果前面有空闲的空间还好说，一旦头元素前面没有空间，我们的队头指针就指向到了数组之外，也就会出现数组越界问题，这该怎么办呢？
我们可以看到，虽然我们的表头已经没有了任何空间，但是表的后半部分还有空余空间，这种现象我们称作假溢出，打个比方，接近上课你缓缓走进教室，看到只有前排剩下了两个位置，你总不会转身就走吧，当然可以去前排坐，只有实在没座位了，才考虑离开
我们可以做出这样一种比较可行的方案
- 我们只需要将这个队列收尾连接起来，当后面的空间满后，接着从前面空出来的空间中进队，同样的，我们的表头指针也找到了可以指向的位置
- 具体的连接方法，就是将date[0…maxSize] 的单元0认为是maxSize - 1
问题三
我们刚才也提到了，当表头指针和表尾指针相等的时候就解决了空队列的情况，但是在表满的情况下，你会发现，同样也满足表头表尾指针相等，那么又如何解决这个问题呢？（我们给出三种可行的解决方案）
- A：设置一个标志变量flag，当front = rear的时，且flag = 0的时候为空，若flag = 1 的时候为队列满
- B：设计一个计数器count统计当前队列中的元素数量，count == 0 队列空，count == maxsSize 队列满
- C：保留一个存储空间用于区分是否队列已满，也就是说，当一个还空闲一个单元时候，我们就认为表已经满了
我们重点讲解 C 中的方法
我们根据这种方法可以总结出几个条件的运算式
- 队列为满的条件：
(rear+1) % MaxSize == front - 队列为空的条件：
front == rear - 队列中元素的个数：
(rear- front + maxSize) % MaxSize - 入队：
rear = (rear + 1) % maxSize - 出队：
front = (front + 1) % maxSize
(一) 顺序队列的类型定义
#ifndef _SEQQUEUE_H_
#define _SEQQUEUE_H_
#include "Queue.h"
template <class T>
class seqQueue:public Queue<T> {
private:
//指向存放元素的数组
T &data;
//队列的大小
int maxSize;
//定义队头和队尾指针
int front, rear;
//扩大队列空间
void resize();
public:
seqQueue(int initSize = 100);
~seqQueue() {delete []data;}
//清空队列
void clear() {front = rear = -1;}
//判空
bool empty() const {return front == rear;}
//判满
bool full() const {return (rear + 1) % maxSize == front;}
//队列长度
int size() const {(rear- front + maxSize) % maxSize;}
//入队
void enQueue(const T &x);
//出队
T deQueue();
//取队首元素
T getHead() const;
};
#endif (二) 初始化一个空队列
template <class T>
seqQueue<T>::seqQueue(int initSize) {
if (initSize <= 0) throw badSize();
data = new T[initSize];
maxSize = initSize;
front = rear = -1;
}(三) 入队
template <class T>
void seqQueue<T>::enQueue(const T &x) {
//队满则扩容
if ((rear + 1) % maxSize == front) resize();
//移动队尾指针
rear = (rear + 1) % maxSize;
//x 入队
data[rear] = x;
}(四) 出队
template <class T>
T seqQueue<T>::deQueue() {
//队列为空则抛出异常
if (empty()) throw outOfRange();
//移动队尾指针
front = (front + 1) % maxSize;
//x入队
return data[front];
}(五) 取队首元素
template <class T>
T seqQueue<T>::getHead() const {
if (empty()) throw outOfRange();
//返回队首元素，不移动队首指针
return data[(front + 1) % maxSize];
}(六) 扩大队列空间
template <class T>
void seqQueue<T>::resize() {
T *p = data;
data = new T[2 *maxSize];
for(int i = 1; i < size(); ++i)
//复制元素
data[i] = p[(front + i) % maxSize];
//设置队首和队尾指针
front = 0; rear = size();
maxSize *= 2;
delete p;
}链队列
用链式存储结构表示队列我们叫做链队列，用无头结点的单链表表示队列，表头为队头，表尾为队尾，需要两个指针分别指向队头元素和队尾元素，这种存储结构的好处之一就是不会出现队列满的情况
(一) 顺序队列的类型定义
#ifndef _LINKQUEUE_H_
#define _LINKQUEUE_H_
#include <iostream>
#include "Queue.h"
template <class T>
class linkQueue:public Queue<T> {
private:
struct node {
T data;
node *next;
node (const T &x, node *N = NULL) {
data = x;
next = N;
}
node ():next(NULL){}
~node () {}
};
node *front, *rear;
public:
linkQueue(){front = rear = NULL;};
~linkQueue() {clear();}
//清空队列
void clear();
//判空
bool empty() const {return front == NULL;}
//队列长度
int size() const;
//入队
void enQueue(const T &x);
//出队
T deQueue();
//取队首元素
T getHead() const;
};
#endif (二) 清空队列
template <class T>
void linkQueue<T>::clear() {
node *p;
//释放队列中所有节点
while(front != NULL) {
p = front;
front = front -> next;
delete p;
}
//修改尾指针
rear = NULL;
} (三) 求队列长度
template <class T>
int linkQueue<T>::size() const {
node *p = front;
int count = 0;
while(p) {
count++;
p = p -> next;
}
return count;
}(四) 入队
template <class T>
void linkQueue<T>::enQueue(const T &x) {
if(rear == NULL)
front = rear = new node(x);
else {
rear -> next = new node(x);
rear = rear -> next;
}
}(五) 出队
template <class T>
T linkQueue<T>::deQueue() {
//队列为空则抛出异常
if (empty()) throw outOfRange();
node *p = front;
//保存队首元素
T value = front -> data;
front = front -> next;
if (front == NULL)
rear = NULL;
delete p;
return value;
}(六) 取队首元素
template <class T>
T linkQueue<T>::getHead() const {
if (empty()) throw outOfRange();
return front -> data;
}结尾：
邮箱：ideal_bwh@163.com
如果能帮到你的话，那就来关注我吧！
如果您更喜欢微信文章的阅读方式，可以关注我的公众号
如果您更加喜欢PC端的阅读方式，可以访问我的个人博客
域名：www.ideal-20.cn
在这里的我们素不相识，却都在为了自己的梦而努力 ❤ 一个坚持推送原创Java技术的公众号：理想二旬不止