点击刷新
本文有关栈的介绍部分参考自网站数据结构。
1. 队列
1.1 队列的定义
队列（Queue）是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表。
（1）允许删除的一端称为队头（Front）。
（2）允许插入的一端称为队尾（Rear）。
（3）当队列中没有元素时称为空队列。
（4）队列亦称作先进先出（First In First Out）的线性表，简称为FIFO表。
队列的修改是依先进先出的原则进行的。新来的成员总是加入队尾（即不允许"加塞"），每次离开的成员总是队列头上的（不允许中途离队），即当前"最老的"成员离队。
【例】在队列中依次加入元素a1，a2，…，an之后，a1是队头元素，an是队尾元素。退出队列的次序只能是a1，a2，…，an。
1.2 队列的运算
（1）initQueue（Q）
置空队。构造一个空队列Q。
（2）isEmpty（Q）
判队空。若队列Q为空，则返回真值，否则返回假值。
（3） isFull（Q）
判队满。若队列Q为满，则返回真值，否则返回假值。
注意：
此操作只适用于队列的顺序存储结构。
（4） enQueue（Q，x）
若队列Q非满，则将元素x插入Q的队尾。此操作简称入队。
（5） deQueue（Q）
若队列Q非空，则删去Q的队头元素，并返回该元素。此操作简称出队。
（6） front（Q）
若队列Q非空，则返回队头元素，但不改变队列Q的状态。
2. 实现
在实现的时候，队列的基本函数都有（isEmpty、enQueue、deQueue、front）。因为我是用面向对象的方法来设计队列，所以队列的初始化、拷贝构造、赋值运算符重载等也都具备。另外，我采取了C++中的模板类来设计队列，使得队列设计能适应更多的场合。
队列的实现跟栈的实现没什么大的区别，只需代码细小的修改就OK了。所以，在这里，我只给出基于静态数组的队列的设计。
2.1 基于静态数组
基于静态数组的队列的最大特点就是队列的大小是固定的，用户在初始化之后就无法改变。在编译期，编译器就已经给这个队列分配好内存，在“内存的栈”上分配。
这是我所设计的队列模板类：
1 template<class T, int defCapacity = 1024> 2 class Queue 3 { 4 public: 5 Queue(); 6 virtual ~Queue(); 7 bool isEmpty(); 8 bool enQueue(T val); // 通过在队尾添加一个值来改变队列。 9 T front(); // 访问队首的值，保持队列不变。 10 bool deQueue(); // 通过删除队首的值来改变一个队列。 11 int getSizeOfQueue(); 12 13 private: 14 T queue[defCapacity]; 15 int sizeOfQueue; 16 17 };
具体实现代码为：
1 #include <iostream> 2 #include <cassert> 3 using namespace std; 4 5 // const int CAPACITY = 1024; 6 7 template<class T, int defCapacity = 1024> 8 class Queue 9 { 10 public: 11 Queue(); 12 virtual ~Queue(); 13 bool isEmpty(); 14 bool enQueue(T val); // 通过在队尾添加一个值来改变队列。 15 T front(); // 访问队首的值，保持队列不变。 16 bool deQueue(); // 通过删除队首的值来改变一个队列。 17 int getSizeOfQueue(); 18 19 private: 20 T queue[defCapacity]; 21 int sizeOfQueue; 22 23 }; 24 25 26 template<class T, int defCapacity> 27 Queue<T, defCapacity>::Queue() 28 { 29 sizeOfQueue = 0; 30 } 31 32 template<class T, int defCapacity> 33 Queue<T, defCapacity>::~Queue() 34 { 35 36 } 37 38 template<class T, int defCapacity> 39 bool Queue<T, defCapacity>::isEmpty() 40 { 41 return sizeOfQueue == 0; 42 } 43 44 template<class T, int defCapacity> 45 bool Queue<T, defCapacity>::enQueue(T val) 46 { 47 // assert(sizeOfQueue < defCapacity); 48 bool isSuccess = true; 49 if (sizeOfQueue == defCapacity) 50 { 51 cerr << "There is no space for new elements." << endl; 52 isSuccess = false; 53 } 54 else 55 { 56 queue[sizeOfQueue] = val; 57 sizeOfQueue++; 58 } 59 return isSuccess; 60 } 61 62 template<class T, int defCapacity> 63 T Queue<T, defCapacity>::front() 64 { 65 //assert(sizeOfQueue > 0); 66 if (sizeOfQueue == 0) 67 { 68 cerr << "There is no elements in the queue." << endl; 69 } 70 return queue[0]; 71 } 72 73 template<class T, int defCapacity> 74 bool Queue<T, defCapacity>::deQueue() 75 { 76 // assert(sizeOfQueue > 0); 77 bool isSuccess = true; 78 if (sizeOfQueue == 0) 79 { 80 cerr << "There is no element in Queue." << endl; 81 isSuccess = false; 82 } 83 else 84 { 85 for (int i = 0; i < sizeOfQueue - 1; i++) 86 { 87 queue[i] = queue[i + 1]; 88 } 89 sizeOfQueue--; 90 } 91 return isSuccess; 92 } 93 94 template<class T, int defCapacity> 95 int Queue<T, defCapacity>::getSizeOfQueue() 96 { 97 return sizeOfQueue; 98 }
Boost单元测试代码为：
1 #define BOOST_TEST_MODULE Stack_Test_Module 2 3 #include "stdafx.h" 4 #include "../Queue/queue.hpp" 5 6 const int MAXSIZE = 3; 7 struct Stack_Fixture 8 { 9 public: 10 Stack_Fixture() 11 { 12 testQueue = new Queue<int, MAXSIZE>(); 13 } 14 15 ~Stack_Fixture() 16 { 17 delete testQueue; 18 } 19 20 Queue<int, MAXSIZE> * testQueue; 21 }; 22 23 24 25 BOOST_FIXTURE_TEST_SUITE(Stack_Test_Fixture, Stack_Fixture) 26 27 BOOST_AUTO_TEST_CASE(Queue_Test) 28 { 29 // isEmpty ------------------------------------ 30 BOOST_REQUIRE(testQueue->isEmpty() == true); 31 32 // isEmpty ------------------------------------ 33 BOOST_REQUIRE(testQueue->getSizeOfQueue() == 0); 34 35 // enQueue & front --------------------------------- 36 BOOST_REQUIRE(testQueue->enQueue(1) == true); 37 BOOST_REQUIRE(testQueue->front() == 1); 38 BOOST_REQUIRE(testQueue->getSizeOfQueue() == 1); 39 40 BOOST_REQUIRE(testQueue->enQueue(2) == true); 41 BOOST_REQUIRE(testQueue->front() == 1); 42 BOOST_REQUIRE(testQueue->getSizeOfQueue() == 2); 43 44 BOOST_REQUIRE(testQueue->enQueue(3) == true); 45 BOOST_REQUIRE(testQueue->front() == 1); 46 BOOST_REQUIRE(testQueue->getSizeOfQueue() == 3); 47 48 BOOST_REQUIRE(testQueue->enQueue(3) == false); 49 BOOST_REQUIRE(testQueue->front() == 1); 50 BOOST_REQUIRE(testQueue->getSizeOfQueue() == 3); 51 52 // deQueue & front ---------------------------------- 53 BOOST_REQUIRE(testQueue->deQueue() == true); 54 BOOST_REQUIRE(testQueue->front() == 2); 55 BOOST_REQUIRE(testQueue->getSizeOfQueue() == 2); 56 57 BOOST_REQUIRE(testQueue->deQueue() == true); 58 BOOST_REQUIRE(testQueue->front() == 3); 59 BOOST_REQUIRE(testQueue->getSizeOfQueue() == 1); 60 61 BOOST_REQUIRE(testQueue->deQueue() == true); 62 BOOST_REQUIRE(testQueue->getSizeOfQueue() == 0); 63 64 BOOST_REQUIRE(testQueue->deQueue() == false); 65 66 } 67 68 69 BOOST_AUTO_TEST_SUITE_END()
2.2 基于动态数组
请参考栈的三种实现（静态数组、动态数组及指针）2.2。
2.3 基于指针
请参考栈的三种实现（静态数组、动态数组及指针）2.3。
本篇博文的代码均托管到Taocode : http://code.taobao.org/p/datastructureandalgorithm/src/.
© 著作权归作者所有
发表评论
