006-队列的知识讲解与基本实现

队列

引言

中午在食堂打饭,真是一个令人头疼的事情,去食堂的路上也总是步伐匆匆,为什么啊,这还用说,迟一点去,你就会知道什么叫做人山人海了,在食堂排队的时候,相比较学生来说,打饭阿姨毕竟是少数,在每个窗口都有人的时候,不免我们就得等待,直到前面的一个学生打完饭离开,后面排队的人才可以继续向前走,直到轮到自己,别提多费劲了,但是秩序和规则却是我们每个人都应该遵守的,也只能抱怨自己来的迟了

这种 “先进先出” 的例子就是我们所讲的基本数据结构之一 ”队列“

例子补充:用电脑的时候,有时候机器会处于疑似死机的状态, 鼠标点什么似乎都没有用,双击任何快捷方式都不动,就当你失去耐心,打算reset的时候,突然它就像酒醒了一样,把你刚才点击的所有操作全部按照顺序执行了一遍,这其实是因为操作系统中的多个程序隐需要通过一个通道输出,而按照先后次序排队等待造成的 ——《大话数据结构》

队列的基本定义

定义:队列是一种只允许在一段进行删除操作,在另一端进行插入操作的线性表

允许插入的一段称作队尾 (rear),允许删除的的一端称为队头 (front)

队列的数据元素又叫做队列元素,在队列中插入一个队列元素称为入队,从队列中删除一个队列元素称为出队 ,也正是因为队列只允许在一段插入,另一端删除,所以这也就是我们前面例子中体现出来的先进先出 (FIFO-first in first out) 的概念

补充:除此之外,还有的队列叫做双端队列,也就是可以在表的两边进行插入和删除操作的线性表

双端队列分类:

  1. 输出受限的双端队列:删除操作限制在表的一段进行,而插入操作允许早表的两端进行

  2. 插入操作限制在表的一段进行,而删除操作允许在表的两端进行

队列的抽象数据类型

#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; 
}

结尾:

如果文章中有什么不足,或者错误的地方,欢迎大家留言分享想法,感谢朋友们的支持!

如果能帮到你的话,那就来关注我吧!如果您更喜欢微信文章的阅读方式,可以关注我的公众号

在这里的我们素不相识,却都在为了自己的梦而努力 ❤

一个坚持推送原创开发技术文章的公众号:理想二旬不止


   转载规则


《006-队列的知识讲解与基本实现》 BWH_Steven 采用 知识共享署名 4.0 国际许可协议 进行许可。
  目录