数据结构探险-01队列篇

发表于   |   分类于   |  

数据结构探险—队列篇-慕课网

本课程将和大家一起领略数据结构的精巧设计并详细的演示队列结构的实现，课程以原理为基础，同时以C++编码做为效果实现。使大家可以由表及里，由浅入深的进入数据结构的美妙世界。

1 课程简介

数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。

课程特点

  • 数据结构的原理
  • 以 c++ 完整得编写各种数据结构

2 队列原理

先进先出(FIFO, first in first out)

2.1 普通队列

容易理解，容易实现，但每次移动需要移动每一项数据，变化成本大。

2.2 环型队列

长度固定，性能更好，但实现起来较复杂。

3 队列结构的面相对象设计

说明： 我们采用 c++ 来实现队列数据结构，和 c 语言面向过程的实现方式不同，c++ 采用类的方式实现队列封装型更好。

4 环型队列代码实现

  • 出队是队头移动。
  • 入队是队尾移动。
  • 队尾下表实际上指向的是队列最后一个元素后面一个元素。
  • 环型队列实际是用数组实现的，为了实现队列头尾的环型移动，采用取余运算。
1
2
3
4
5
.
├── MyQueue.cpp
├── MyQueue.h
├── main.cpp
└── makefile

MyQueue.h

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 MYQUEUE_H
#define MYQUEUE_H
class MyQueue
{
public:
	MyQueue(int queueCapacity); // 创建队列
	virtual ~MyQueue(); // 销毁队列
	void ClearQueue(); // 清空队列
	bool QueueEmpty() const; // 队列判空
	int QueueLength() const; // 队列长度
	bool EnQueue(int element); // 新元素入队
	bool DeQueue(int &element); // 首元素出队
	bool QueueFull() const; // 判断队列是否已满
	void QueueTraverse(); // 遍历队列
private:
	int *m_pQueue; // 队列数组指针
	int m_iQueueLen; // 队列元素个数
	int m_iQueueCapacity; // 队列数组容量
	int m_iHead; // 队头
	int m_iTail; // 尾
};

#endif

MyQueue.cpp

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include "MyQueue.h"
#include <iostream>
using namespace std;

// 构造函数
MyQueue::MyQueue(int queueCapacity)
{
	m_iQueueCapacity = queueCapacity;
	ClearQueue();
	m_pQueue = new int[m_iQueueLen]; // 队列长度(注意：这里为了简化没有处理可能出现的内存分配失败)
}

// 析构函数
MyQueue::~MyQueue()
{
	delete []m_pQueue;
	m_pQueue = NULL;
}

// 清空队列
void MyQueue::ClearQueue()
{
	m_iHead = 0; // 队头下标
	m_iTail = 0; // 队尾下标
	m_iQueueLen = 0; // 队列长度
}

// 判空
bool MyQueue::QueueEmpty() const
{
	return m_iQueueLen == 0 ? true : false;
}

// 队列长度
int MyQueue::QueueLength() const
{
	return m_iQueueLen;
}

// 判满
bool MyQueue::QueueFull() const
{
	return m_iQueueLen == m_iQueueCapacity ? true : false;
}

// 从队尾插入新元素(需要顺时针移动队尾指针)
bool MyQueue::EnQueue(int element)
{
	if(QueueFull())
	{
		return false;
	}
	else
	{
		m_pQueue[m_iTail] = element;
		m_iTail++;
		m_iTail = m_iTail % m_iQueueCapacity; // 实现环型的核心代码
		m_iQueueLen++;
		return true;
	}
}

// 从队首出队（需要顺时针移动队头指针）
bool MyQueue::DeQueue(int &element)
{
	if(QueueEmpty())
	{
		return false;
	}
	else
	{
		element = m_pQueue[m_iHead];
		m_iHead++;
		m_iHead = m_iHead % m_iQueueCapacity; // 实现环型的核心代码
		m_iQueueLen--;
		return true;
	}
}

// 遍历(从队头遍历到队尾)
void MyQueue::QueueTraverse()
{
	for(int i = 0; i < m_iQueueLen; i++)
	{
		cout << m_pQueue[(m_iHead + i) % m_iQueueCapacity] << endl;
	}
}

main.cpp

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
#include <iostream>
#include "MyQueue.h"
using namespace std;

int main(void)
{
	// 创建队列实例
	MyQueue *queue = new MyQueue(4);

	// 插入数据
	queue->EnQueue(3);
	queue->EnQueue(5);
	queue->EnQueue(7);
	queue->EnQueue(9);

	// 队首出队，赋值给 ele
	int ele = 0;
	cout << "DeQueue:" << queue->DeQueue(ele) << endl;

	// 遍历
	queue->QueueTraverse();

	delete queue;
	queue = NULL;
	return 0;
}

5 升华与应用