"《算法导论》之‘队列’"：队列的三种实现（静态数组、动态数组及指针）

时间：2022-03-03 09:07:29

　　本文有关栈的介绍部分参考自网站数据结构。

　 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 基于静态数组　　

　　基于静态数组的队列的最大特点就是队列的大小是固定的，用户在初始化之后就无法改变。在编译期，编译器就已经给这个队列分配好内存，在“内存的栈”上分配。

　　这是我所设计的队列模板类：

 template<class T, int defCapacity = >

 class Queue

 {

 public:

     Queue();

     virtual ~Queue();

     bool isEmpty();

     bool enQueue(T val);       // 通过在队尾添加一个值来改变队列。

     T front();                 // 访问队首的值，保持队列不变。

     bool deQueue();            // 通过删除队首的值来改变一个队列。

     int getSizeOfQueue();

 private:

     T queue[defCapacity];

     int sizeOfQueue;

 };

　　具体实现代码为：

 #include <iostream>

 #include <cassert>

 using namespace std;

 // const int CAPACITY = 1024;

 template<class T, int defCapacity = >

 class Queue

 {

 public:

     Queue();

     virtual ~Queue();

     bool isEmpty();

     bool enQueue(T val);    // 通过在队尾添加一个值来改变队列。

     T front();                // 访问队首的值，保持队列不变。

     bool deQueue();            // 通过删除队首的值来改变一个队列。

     int getSizeOfQueue();

 private:

     T queue[defCapacity];

     int sizeOfQueue;

 };

 template<class T, int defCapacity>

 Queue<T, defCapacity>::Queue()

 {

     sizeOfQueue = ;

 }

 template<class T, int defCapacity>

 Queue<T, defCapacity>::~Queue()

 {

 }

 template<class T, int defCapacity>

 bool Queue<T, defCapacity>::isEmpty()

 {

     return sizeOfQueue == ;

 }

 template<class T, int defCapacity>

 bool Queue<T, defCapacity>::enQueue(T val)

 {

     // assert(sizeOfQueue < defCapacity);

     bool isSuccess = true;

     if (sizeOfQueue == defCapacity)

     {

         cerr << "There is no space for new elements." << endl;

         isSuccess = false;

     }

     else

     {

         queue[sizeOfQueue] = val;

         sizeOfQueue++;

     }

     return isSuccess;

 }

 template<class T, int defCapacity>

 T Queue<T, defCapacity>::front()

 {

     //assert(sizeOfQueue > 0);

     if (sizeOfQueue == )

     {

         cerr << "There is no elements in the queue." << endl;

     }

     return queue[];

 }

 template<class T, int defCapacity>

 bool Queue<T, defCapacity>::deQueue()

 {

     // assert(sizeOfQueue > 0);

     bool isSuccess = true;

     if (sizeOfQueue == )

     {

         cerr << "There is no element in Queue." << endl;

         isSuccess = false;

     }

     else

     {

         for (int i = ; i < sizeOfQueue - ; i++)

         {

             queue[i] = queue[i + ];

         }

         sizeOfQueue--;

     }

     return isSuccess;

 }

 template<class T, int defCapacity>

 int Queue<T, defCapacity>::getSizeOfQueue()

 {

     return sizeOfQueue;

 }

queue.hpp

　　Boost单元测试代码为：

 #define BOOST_TEST_MODULE Stack_Test_Module

 #include "stdafx.h"

 #include "../Queue/queue.hpp"

 const int MAXSIZE = ;

 struct Stack_Fixture

 {

 public:

     Stack_Fixture()

     {

         testQueue = new Queue<int, MAXSIZE>();

     }

     ~Stack_Fixture()

     {

         delete testQueue;

     }

     Queue<int, MAXSIZE> * testQueue;

 };

 BOOST_FIXTURE_TEST_SUITE(Stack_Test_Fixture, Stack_Fixture)

 BOOST_AUTO_TEST_CASE(Queue_Test)

 {

     // isEmpty ------------------------------------

     BOOST_REQUIRE(testQueue->isEmpty() == true);

     // isEmpty ------------------------------------

     BOOST_REQUIRE(testQueue->getSizeOfQueue() == );

     // enQueue & front ---------------------------------

     BOOST_REQUIRE(testQueue->enQueue() == true);

     BOOST_REQUIRE(testQueue->front() == );

     BOOST_REQUIRE(testQueue->getSizeOfQueue() == );

     BOOST_REQUIRE(testQueue->enQueue() == true);

     BOOST_REQUIRE(testQueue->front() == );

     BOOST_REQUIRE(testQueue->getSizeOfQueue() == );

     BOOST_REQUIRE(testQueue->enQueue() == true);

     BOOST_REQUIRE(testQueue->front() == );

     BOOST_REQUIRE(testQueue->getSizeOfQueue() == );

     BOOST_REQUIRE(testQueue->enQueue() == false);

     BOOST_REQUIRE(testQueue->front() == );

     BOOST_REQUIRE(testQueue->getSizeOfQueue() == );

     // deQueue & front ----------------------------------

     BOOST_REQUIRE(testQueue->deQueue() == true);

     BOOST_REQUIRE(testQueue->front() == );

     BOOST_REQUIRE(testQueue->getSizeOfQueue() == );

     BOOST_REQUIRE(testQueue->deQueue() == true);

     BOOST_REQUIRE(testQueue->front() == );

     BOOST_REQUIRE(testQueue->getSizeOfQueue() == );

     BOOST_REQUIRE(testQueue->deQueue() == true);

     BOOST_REQUIRE(testQueue->getSizeOfQueue() == );

     BOOST_REQUIRE(testQueue->deQueue() == false);

 }

 BOOST_AUTO_TEST_SUITE_END()

BoostUnitTest.cpp

　　2.2 基于动态数组

　　请参考栈的三种实现（静态数组、动态数组及指针）2.2。

　　2.3 基于指针

　　请参考栈的三种实现（静态数组、动态数组及指针）2.3。

　　本篇博文的代码均托管到Taocode : http://code.taobao.org/p/datastructureandalgorithm/src/.

相关文章