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

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

  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/.

上一篇:流API--流的基础知识


下一篇:Django restful Framework 之序列化与反序列化