转载

队列 1 - 基本概念及实现方法

继续是《数据结构算法与应用：C++语言描述》的笔记，这是第六章队列的内容。

队列是一种特殊的线性表，其插入和删除操作分别在线性表的两端进行，因此，队列是一个 先进先出(first-in-first-out,FIFO)的线性表 。

抽象数据类型

定义队列(queue)是一个线性表，其插入和删除操作分别在表的不同端进行。添加新元素的那一端称为队尾(rear),而删除元素的那一端被称为队首(front)。

其抽象数据类型如下：

抽象数据类型Queue{ 实例     有序线性表，一端称为front，另一端称为rear； 操作     Create(): 创建一个空的队列；     IsEmpty(): 如果队列为空，则返回true，否则返回false；     IsFull(): 如果队列满，则返回true，否则返回false；     First(): 返回队列的第一个元素；     Last(): 返回队列的最后一个元素；     Add(x): 向队列中添加元素x；     Delete(x): 删除队首元素，并送入x； }

公式描述

使用公式$location(i)=i-1$来描述一个队列，那么所使用的数组是 queue[MaxSize] ,那么第一个元素是queue[0],第二个元素是queue 1 ,$/cdots$。 front总是为0，而rear始终是最后一个元素的位置，队列的长度为rear+1，对于一个空队列有rear=-1 。

按照上述公式描述队列，在添加一个元素的时候，需要将rear加1，并把新元素放入queue[rear]，其所需要的时间是$O(1)$。而删除一个元素，则需要将位置1到位置n的元素分别左移一个位置，即删除一个元素需要花费的时间是$/theta(n)$，n是删除完成后队列中的元素数目。因此，这个公式对于队列的删除操作会花费比较多时间，虽然其应用在堆栈的时候，堆栈的添加和删除操作所需时间只需要$/theta(1)$。

这里考虑另一个公式$location(i)=location(1)+i-1$,它可以使得队列的删除操作所需要的时间减小至$/theta(1)$。因为在删除的时候，只需要简单的将location(1)加1即可。在用该公式的时候， front = location(1), rear=location(最后一个元素),一个空队列具有形状$rear /lt front$ 。

如下图所示，每次操作将导致front右移一个位置。

队列 1 - 基本概念及实现方法

当$rear /lt MaxSize-1$时才可以直接在队列的尾部添加新元素。若$rear = MaxSize-1且front /gt 0$时（表明队列未满），为了能够继续向队列添加新元素，必须将所有元素平移到队列的左端，如下图所示，以便在队列的右端留出空间。在使用新的公式情况下，最坏情况下的时间复杂性增加了$/theta(n)$，所以，新公式在提高删除操作执行效率的同时，却降低了添加操作的执行效率。

队列 1 - 基本概念及实现方法

上述两个公式都各有缺点，所以这里就有了第三个公式，可以将队列的添加和删除操作在最坏情况下的时间复杂性均为$/theta(1)$,如下所示：

location(i) = (location(1)+i-1)/% MaxSize

这个时候用来描述队列的数组被视为一个环，如下所示，此时， front指向队列首元素的下一个位置（逆时针），而rear的含义不变。下图b是添加一个元素，而图c表示的是删除了一个元素。

队列 1 - 基本概念及实现方法

当且仅当front=rear时队列为空，但是由于队列满的条件也是front=rear，所以为了避免这种问题，可以不允许队列被填满，在添加元素前，先判断本次操作是否会导致队列被填满，如果是，则报错。因此，队列的最大容量实际上是MaxSize-1。

下面给出基于公式化描述的类Queue的代码实现。

#ifndef QUEUE_H_ #define QUEUE_H_ #include<iostream>  template<class T> class Queue{ private:     // 与第一个元素在逆时针方向上相差一个位置     int front;     // 指向最后一个元素     int rear;     int MaxSize;     T* queue; public:     Queue(int MaxQueueSize = 10);     ~Queue(){ delete[] queue; }     bool IsEmpty() const { return front == rear; }     bool IsFull() const {         return (((rear + 1) % MaxSize == front) ? 1 : 0);     }     T First() const;     T Last() const;     Queue<T>& Add(const T& x);     Queue<T>& Delete(T& x);     void Output(std::ostream&); }; #endif

下面给出其添加和删除操作函数的实现：

template<class T> Queue<T>& Queue<T>::Add(const T& x){     // 将x添加到队列的尾部     if (IsFull())         throw NoMem();     rear = (rear + 1) % MaxSize;     queue[rear] = x;     return *this; }  template<class T> Queue<T>& Queue<T>::Delete(T& x){     // 删除第一个元素，并将其送入x     if (IsEmpty())         throw OutOfBounds();     front = (front + 1)&MaxSize;     x = queue[front];     return *this; }

其他成员函数实现可以查看 Queue-数组实现 。

链表描述

像堆栈一样，也可以使用链表来实现一个队列。此时需要两个变量 front和rear 分别跟踪队列的两端。这时有两种情形：从front开始链接到rear，如下图a所示，或者从rear开始链接到front，如下图b所示。

队列 1 - 基本概念及实现方法

下面两张图分别展示了两种情形添加和删除操作，两种情形都适合于添加操作，而从front到rear的链接更便于删除操作的执行，因此，我们将采用从front到rear的链接模式。

队列 1 - 基本概念及实现方法

可以取处置 front=rear=0，且当且仅当队列为空时front=0 。下面程序给出自定义类 LinkedQueue 。除了析构函数外，链表队列所有成员函数的复杂性均为$/theta(1)$。

#ifndef LINKEDQUEUE_H_ #define LINKEDQUEUE_H_ #include<iostream>  template<class T> class LinkedQueue;  template<class T> class Node{     friend LinkedQueue<T>; private:     T data;     Node<T>* link; };  template<class T> class LinkedQueue{ private:     Node<T>* front;     Node<T>* rear; public:     LinkedQueue(){ front = rear = 0; }     ~LinkedQueue();     bool IsEmpty() const{         return ((front) ? false : true);     }     bool IsFull() const;     T First() const;     T Last() const;     LinkedQueue<T>& Add(const T& x);     LinkedQueue<T>& Delete(T& x);     void Output(std::ostream&); }; #endif

然后同样是给出添加和删除操作的实现代码：

template<class T> LinkedQueue<T>& LinkedQueue<T>::Add(const T& x){     // 添加元素x     Node<T>* p = new Node<T>;     p->data = x;     p->link = 0;     if (front)         // 队列不为空         rear->link = p;     else         // 队列为空         front = p;     rear = p;      return *this; }  template<class T> LinkedQueue<T>& LinkedQueue<T>::Delete(T& x){     // 删除第一个元素，并放入x     if (IsEmpty())         throw OutOfBounds();     x = front->data;      // 删除第一个节点     Node<T>* p = front;     front = front->link;     delete p;      return *this; }

具体实现可以查看 链表实现的队列 。