数据结构之队列的定义与实现

队列基础知识

和栈类似,队列也是一种线性表,不过队列是在一端插入在另外一端删除。插入的一端称为队尾,删除的一端称为队头。队列的基本操作是入队和出队。由于队列的插入删除特性,因此队列具有“先进先出(FIFO)”的特点。同理,使用顺序表实现的队列称为顺序队列,使用链表实现的队列称为链式队列。队列采用数组实现时一般需要实现为循环数组,故一般也称为循环队列。队列实现中一般有如下操作:

  • 入队:Enqueue
  • 出队:Dequeue
  • 判断是否为空:IsEmpty
  • 清空队列:MakeEmpty
  • 读取队首元素:Front

队列的链表实现

在采用链表实现队列时,由于队列是“先进先出”的,因此可以尝试使用尾插法同时从头部删除的方式实现队列“先进先出”的特点。在STL中queue的实现中,其底层采用的是deque,和栈类似,list也可实现队列。

仿照《数据结构与算法分析-C语言描述》的定义,队列可定义如下:

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
template <typename DataType>
class Node
{
public:
Node(DataType inData):data(inData),next(nullptr) {}
public:
DataType data;
Node *next;
};


template <typename DataType>
class Queue
{
public:
Queue():dummyNode(-1), queueSize(0), lastNode(nullptr) {}
~Queue();
void Enqueue(DataType inData); //入队
void Dequeue(); //出队
DataType Front(); //读取队首元素,队空则抛出异常
bool IsEmpty(); //判断队列是否为空
void MakeEmpty(); //清空队列
int QueueSize(); //返回队列大小
private:
Node<DataType> dummyNode;
int queueSize;
Node<DataType> *lastNode;
};

如上所示,队列的数据成员有哑节点、队列大小以及一个指链表尾端的指针。如下依次实现各个操作

  • 入队操作,采用尾插法
1
2
3
4
5
6
7
8
9
template <typename DataType>
void Queue<DataType>::Enqueue(DataType inData)
{
if (queueSize <= 0 || lastNode == nullptr) {
lastNode = &dummyNode;
}
lastNode->next = new Node<DataType>(inData);
lastNode = lastNode->next; ++queueSize;
}
  • 出队操作,不断删除链表第一个元素,队空抛出异常
1
2
3
4
5
6
7
8
9
10
template <typename DataType>
void Queue<DataType>::Dequeue()
{
if (queueSize <= 0 || dummyNode.next == nullptr) {
throw "Queue is empty!";
}
Node<DataType> *tmp = dummyNode.next; /*删除头部*/
dummyNode.next = dummyNode.next->next;
delete tmp; --queueSize;
}
  • 读取队首元素,队空则抛出异常
1
2
3
4
5
6
7
8
template <typename DataType>
DataType Queue<DataType>::Front()
{
if (queueSize <= 0 || dummyNode.next == nullptr) {
throw "Queue is empty!";
}
return dummyNode.next->data;
}
  • 判断队列是否为空
1
2
3
4
5
template <typename DataType>
bool Queue<DataType>::IsEmpty()
{
return queueSize <= 0 || dummyNode.next == nullptr;
}
  • 清空队列,也可以直接通过调用Dequeue函数实现
1
2
3
4
5
6
7
8
9
10
11
template <typename DataType>
void Queue<DataType>::MakeEmpty()
{
Node<DataType> *tmp = dummyNode.next;
/*循环删除头部*/
while (tmp != nullptr) {
dummyNode.next = tmp->next;
delete tmp; --queueSize;
tmp = dummyNode.next;
}
}
  • 返回队列大小
1
2
3
4
5
template <typename DataType>
int Queue<DataType>::QueueSize()
{
return queueSize;
}
  • 析构函数,直接调用MakeEmpty函数实现
1
2
3
4
5
template <typename DataType>
Queue<DataType>::~Queue()
{
MakeEmpty();
}

队列的循环数组实现

在使用数组实现队列时,由于队列是在一端插入,另外一端删除,因此队列和栈不同的是需要两个指针分别指向队首和队尾,同时需要采用循环数组的实现方式,循环数组意味着在物理结构上队首、队尾标记可能不遵循前后的位置关系。采用循环数组实现队列的基本ADT定义如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
template <typename DataType>
class Queue
{
public:
Queue(int inQueueCapacity);
~Queue(); //析构函数,回收内存
void Enqueue(DataType inData); //入队,堆满则抛出异常
void Dequeue(); //出队,队空则抛出异常
DataType Front(); //读取队首元素,队空则抛出异常
bool IsEmpty(); //判断队列是否为空
void MakeEmpty(); //清空队列
int QueueSize(); //返回队列大小
private:
int queueCapacity;
DataType *queuePtr; /*动态申请*/
int front, rear; /*分别指向队首、队尾*/
int queueSize;
};

如上所示为队列的循环数组实现的基本数据结构定义。queueCapacity保存队列的容量,queuePtr为队列的空间起始地址,front、rear分别用来指示队首、队尾位置,queueSize表示当前队列的大小。在计算front、rear时由于需要考虑绕回的情况,因此其不能直接加1,应该加1后再对容量取模。在我的是实现版本中,front==rear的情况可能是队空或者队满,因此在判断队空或者队满的时候不能简单判断两者是否相等。以下为各函数具体实现。

  • 构造函数的实现,分配内存,初始化数据成员
1
2
3
4
5
6
template <typename DataType>
Queue<DataType>::Queue(int inQueueCapacity): queueCapacity(inQueueCapacity),
front(0), rear(0), queueSize(0)
{
queuePtr = new DataType[inQueueCapacity];
}
  • 入队操作,堆满则抛出异常
1
2
3
4
5
6
7
8
9
10
template <typename DataType>
void Queue<DataType>::Enqueue(DataType inData)
{
if (queueSize >= queueCapacity) {
throw "Queue is full";
}
queuePtr[rear] = inData;
rear = (rear+1) % queueCapacity;
++queueSize;
}
  • 出队操作,队空抛出异常
1
2
3
4
5
6
7
8
9
template <typename DataType>
void Queue<DataType>::Dequeue()
{
if (queueSize <= 0 && front == rear) {
throw "Queue is empty!";
}
front = (front+1) % queueCapacity;
--queueSize;
}
  • 读取队首元素,队空则抛出异常
1
2
3
4
5
6
7
8
template <typename DataType>
DataType Queue<DataType>::Front()
{
if (queueSize <= 0 && front == rear) {
throw "Queue is empty!";
}
return queuePtr[front];
}
  • 判断队列是否为空
1
2
3
4
5
template <typename DataType>
bool Queue<DataType>::IsEmpty()
{
return queueSize <= 0 && front == rear;
}
  • 清空队列,也可以直接通过调用Dequeue函数实现
1
2
3
4
5
6
template <typename DataType>
void Queue<DataType>::MakeEmpty()
{
queueSize = 0;
front = rear = 0;
}
  • 返回队列大小
1
2
3
4
5
template <typename DataType>
int Queue<DataType>::QueueSize()
{
return queueSize;
}
  • 析构函数,直接调用MakeEmpty函数实现
1
2
3
4
5
6
template <typename DataType>
Queue<DataType>::~Queue()
{
MakeEmpty();
delete [] queuePtr;
}

代码测试

基本数据结构测试代码如下:

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
#include <iostream>
using std::cout;
using std::endl;

int main()
{
try {
Queue<int> TestQueue; /*实际测试*/
/*Queue<int> TestQueue(20);*/
for (int i = 0; i < 13; i++) {
TestQueue.Enqueue(i);
}
for (int i = 0; i < 100; i++) {
cout << TestQueue.Front() << ";";
TestQueue.Dequeue();
}
cout << endl;

}
catch(const char *msg) {
cout << msg << endl;
return -1;
}
return 0;
}

参考资料

数据结构与算法分析