继续是《数据结构算法与应用：C++语言描述》的笔记，这是第六章队列的内容。
队列是一种特殊的线性表，其插入和删除操作分别在线性表的两端进行，因此，队列是一个先进先出(first-in-first-out,FIFO)的线性表。
抽象数据类型
定义 队列(queue)是一个线性表，其插入和删除操作分别在表的不同端进行。添加新元素的那一端称为队尾(rear),而删除元素的那一端被称为队首(front)。
其抽象数据类型如下：1
2
3
4
5
6
7
8
9
10
11
12抽象数据类型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],第二个元素是queue1,$\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右移一个位置。
当$rear \lt MaxSize-1$时才可以直接在队列的尾部添加新元素。若$rear = MaxSize-1且front \gt 0$时（表明队列未满），为了能够继续向队列添加新元素，必须将所有元素平移到队列的左端，如下图所示，以便在队列的右端留出空间。在使用新的公式情况下，最坏情况下的时间复杂性增加了$\theta(n)$，所以，新公式在提高删除操作执行效率的同时，却降低了添加操作的执行效率。
上述两个公式都各有缺点，所以这里就有了第三个公式，可以将队列的添加和删除操作在最坏情况下的时间复杂性均为$\theta(1)$,如下所示：
这个时候用来描述队列的数组被视为一个环，如下所示，此时，front指向队列首元素的下一个位置（逆时针），而rear的含义不变。下图b是添加一个元素，而图c表示的是删除了一个元素。
当且仅当front=rear时队列为空，但是由于队列满的条件也是front=rear，所以为了避免这种问题，可以不允许队列被填满，在添加元素前，先判断本次操作是否会导致队列被填满，如果是，则报错。因此，队列的最大容量实际上是MaxSize-1。
下面给出基于公式化描述的类Queue的代码实现。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27#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
下面给出其添加和删除操作函数的实现：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19template<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所示。
下面两张图分别展示了两种情形添加和删除操作，两种情形都适合于添加操作，而从front到rear的链接更便于删除操作的执行，因此，我们将采用从front到rear的链接模式。
可以取处置front=rear=0，且当且仅当队列为空时front=0。下面程序给出自定义类LinkedQueue。除了析构函数外，链表队列所有成员函数的复杂性均为$\theta(1)$。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34#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
然后同样是给出添加和删除操作的实现代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31template<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;
}
具体实现可以查看链表实现的队列。
小结
本节主要是简单介绍了队列的定义以及使用数组和链表来实现的方法。