首页 > 代码库 > 队列的三种实现（静态数组、动态数组及指针）
队列的三种实现（静态数组、动态数组及指针）
本文有关栈的介绍部分参考自网站数据结构。
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 else55 {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 else84 {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/.
队列的三种实现（静态数组、动态数组及指针）