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

发表于 | 分类于

队列基础知识

和栈类似，队列也是一种线性表，不过队列是在一端插入在另外一端删除。插入的一端称为队尾，删除的一端称为队头。队列的基本操作是入队和出队。由于队列的插入删除特性，因此队列具有“先进先出(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;
}

参考资料

数据结构与算法分析