队列用链表来表示时,需要用两个变量来记录队列两端的变化:theFront,theBack.
根据链接方向的不同,链队有两种链接方式(其实就是链表的头插入节点和尾插入节点,头删除节点和尾删除节点)。
插如操作时,两种方式都是一样的;删除元素的时候,从头至尾的方式更便于操作。
链队的初始值为queueFront=queueBack=NULL,当且仅当队列为空时,queueFront=NULL
下面是队列链表的两种描述,对比可看出,从头到尾链接方式在删除操作时更加方便:
下面的代码的具体实现:
/*
* 测试函数
* linkedQueue.cpp
*/
#include<iostream>
#include"linkedqueue.h"
#include"myexceptions.h"
int main(void)
{
linkedQueue<int> q;
q.push(1);
cout<<"Queue back is "<<q.back()<<endl;
q.push(2);
cout<<"Queue back is "<<q.back()<<endl;
q.push(3);
cout<<"Queue back is "<<q.back()<<endl;
q.push(4);
cout<<"Queue back is "<<q.back()<<endl;
cout<<"Queue should be 1234,front to back"<<endl;
if(q.empty())
cout<<"The queue is empty"<<endl;
else
cout <<"The queue is not empty"<<endl;
cout<<"The queue size is "<<q.size()<<endl;
while(!q.empty())
{
cout <<"Queue front is "<<q.front()<<endl;
q.pop();
cout <<"Popped front element"<<endl;
}
try{q.pop();}
catch(queueEmpty message)
{
cout <<"Last pop failed"<<endl;
message.outputMessage();
}
return 0;
}
/*
* 链表的节点类,定义了节点该有的基本属性
* chainNode.h
*/
#ifndef CHAINNODE_H
#define CHAINNODE_H
template<class T>
struct chainNode
{
T element;//节点元素
chainNode<T> *next;//指向下一个元素的指针
//所需函数
chainNode() {}
//节点中元素的复制
chainNode(const T& element)
{
this->element = element;
}
//节点复制
chainNode(const T &element,chainNode<T> *next)
{
this->element = element;
this->next = next;
}
};
#endif // CHAINNODE_H
/*
* 队列抽象类定义
* queue.h
*/
#ifndef QUEUE_H
#define QUEUE_H
using namespace std;
template<class T>
class queue
{
public:
virtual ~queue(){}
virtual bool empty() const = 0;//队列为空判断
virtual int size() const = 0;//队列元素个数
virtual T& front() = 0;//队首引用
virtual T& back() = 0;//队尾引用
virtual void pop() = 0;//出队
virtual void push(const T& theElement) = 0;//入队
};
#endif // QUEUE_H
/*
*链队的具体实现类
* linkedQueue.h
*
*
*/
#ifndef LINKEDQUEUE_H
#define LINKEDQUEUE_H
#include"queue.h"
#include"myexceptions.h"
#include"chainnode.h"
#include<sstream>
using namespace std;
template<class T>
class linkedQueue : public queue<T>
{
public:
//链队初始化,将队列置空
linkedQueue(int initialCapacity = 10)
{
queueFront = NULL;
queueSize = 0;
}
//析构函数,释放队列元素,将队列置空
~linkedQueue()
{
//跟出队相似的操作,不过是要将队列中的元素一个一个的释放掉
while (queueFront != NULL)
{
chainNode<T>* nextNode = queueFront->next;
delete queueFront;
queueFront = nextNode;
}
}
bool empty() const
{
return queueSize == 0;
}
int size() const
{
return queueSize;
}
//返回队首元素
T& front()
{
if(queueSize == 0)
throw queueEmpty();
return queueFront->element;
}
//返回队尾元素
T& back()
{
if(queueSize == 0)
throw queueEmpty();
return queueBack->element;
}
//出队操作
void pop()
{
if(queueFront == NULL)
throw queueEmpty();
chainNode<T>* nextNode = queueFront->next;
delete queueFront;
queueFront = nextNode;
queueSize--;
}
//入队操作
void push(const T& theElement)
{
chainNode<T>* newNode = new chainNode<T>(theElement,NULL);
if(queueSize == 0)
queueFront = newNode;
else
queueBack->next = newNode;
queueBack = newNode;//无论队列是否为空,都有这一步操作
queueSize++;
}
private:
chainNode<T> *queueFront;
chainNode<T> *queueBack;
int queueSize;
};
#endif // LINKEDQUEUE_H
/*
* 异常处理类
* myExceptions.h
*/
#ifndef MYEXCEPTIONS_H
#define MYEXCEPTIONS_H
#include<string>
using namespace std;
//template<class T>
class queueEmpty
{
public:
queueEmpty(string theMessage =
"Invalid operation on empty queue")
{
message = theMessage;
}
void outputMessage()
{
cout << message <<endl;
}
private:
string message;
};
#endif // MYEXCEPTIONS_H