数据结构复习篇:队列
队列是一种先进先出（FIFO）的线性表。跟栈一样，它们的pop()、push()操作的时间复杂度都为1。同样有两种实现，基于数组的AQueue和链式LQueue的。难点在于基于数组的。为了保证pop()和push()的时间复杂度为1，要用到“循环存储”的思想。这个思想就是把一个固定长度数组看作是一个首尾相接的“圈”。这样，我们的“入队”push()和“出队”pop()操作，就可以直接向队尾加入一个元素或从队首取出一个元素。要在数组中，实现循环存储，需要用到一个小技巧：
例如，已知数组A长度为100，那么，当队尾为A[99]时，如果再执行一个push()操作（前提是，A[0]没有被队首元素占用），那么A[0]将成为新的队尾，怎么告诉计算机当队尾下标为99时，新加入的元素应该放在下标为0的地方而不是100呢？这里用到一个求余运算，可以解决“下标循环”的问题：
设数组长度为Len，队尾下标为rear，那么加入一个元素后，新的队尾下标为：
newRear = (rear+1)%Len
还有一点需要注意，因为队列是可以为空的，这个时候，队首与队尾的下标相等，那么当有一元素的时候，队尾下标指向那个元素的后面那个位置，这就是说，队尾下标所指的那个位置，是不存放元素的，所以数组的长度Len应比队列长度queSize大1。
链式队列很容易理解，我不多说了。
下面是我按照C＋＋标准库中queue的接口，自己写的代码：
/*
定义队列的共公接口
文件名：QueueInterface.h
*/
#ifndef QUEUEINTERFACK_H
#define QUEUEINTERFACK_H
#include "NodeInterface.h"
using namespace std;
namespace zyk
{
template<class T> class Queue
{
public:
//从今天开始,我决定采用STL的接口,
//这样有利于我们熟悉标准库函数
virtual T & back() = 0; //返回队尾元素
virtual T & front() = 0; //返回队首元素
virtual void pop() = 0; //出队
virtual void push(const T&) = 0;//进队
virtual bool empty() = 0; //返回值指示队列是否为空
virtual int size() = 0; //返回队中元素个数
};
//基于数组的队列AQueue
template<class T> class AQueue : Queue<T>
{
private:
int maxSize; //队列的最大容量,由于采用循环存储的方式,
//它比实际值大1,以保证队尾rear所指的位置,
//是队尾元素的下一个位置
int mfront; //指示队首元素的在数组中的下标
int mrear; //队尾元素的在数组中的下标的下一个位置
T * listArray; //数组指针
public:
AQueue(int size = 100)
{
maxSize = size + 1; //这一点很关键
mfront = mrear = 0;
listArray = new T[maxSize];
}
~AQueue()
{
delete [] listArray;
}
T & back()
{
//当rear=0里,(rear-1)%maxSize将会成为负-1,而(mrear-1+maxSize)%maxSize可以解决这个问题
return listArray[(mrear - 1 + maxSize)%maxSize];
}
T & front()
{
return listArray[mfront];
}
void pop()
{
mfront = (mfront+1)%maxSize;
}
void push(const T & item)
{
listArray[mrear] = item;
mrear = (mrear+1)%maxSize;
}
bool empty()
{
if (mrear == mfront)
return true;
else return false;
}
int size()
{
return (mrear - mfront + maxSize)%maxSize;
}
};
//链式队列
template<class T> class LQueue : Queue<T>
{
private:
int queSize; //队元素的个数
Node<T> * pfront; //指向队首元素
Node<T> * prear; //指向队尾元素
public:
LQueue()
{
queSize = 0;
pfront = prear = NULL;
}
~LQueue()
{
while (pfront != NULL)
{
Node<T> * tmp;
tmp = pfront;
pfront = pfront->next;
delete tmp;
}
}
T & back()
{
return prear->element;
}
T & front()
{
return pfront->element;
}
void pop()
{
Node<T> * tmp;
tmp = pfront;
if (queSize == 1) //只有一个元素.
{
prear = pfront->next;
}
pfront = pfront->next;
delete tmp;
--queSize;
}
void push(const T & item)
{
if (queSize == 0) //第一个元素入栈,这时情况比较特殊
{
pfront = prear = new Node<T>(item); //一同指向第一个元素
++queSize;
return;
}
prear->next = new Node<T>(item);
prear = prear->next;
++queSize;
}
bool empty()
{
if (queSize == 0)
return true;
else
return false;
}
int size()
{
return queSize;
}
};
}
#endif