队列实际上是一个受限的线性表.所以可以利用单链表一部分功能来实现.
单链表的定义见:http://blog.csdn.net/weiwenhp/article/details/8634469
1.队列的链表表示
#include "LinkList.h"
template<class T>
class LinkQueue
{
private:
LinkList<T> m_pList;
public:
void EnQue(T val){m_pList.Add(val);} //入栈
T GetRear(){return m_pList.GetTailVal();} //返回栈尾元素值
T DeQue(){ //出栈
T val = m_pList.GetHeadVal();
m_pList.RemoveAt(0);
return val;
}
T GetFront(){return m_pList.GetHeadVal();} //返回栈头部元素值
int Size(){ return m_pList.Size();}
void Clear() { m_pList.Clear(); }
};
2.队列的数组表示
一般用数组表示队列时,为了充分利用空间,采用所谓的循环队列表示.数组逻辑上变得是首尾相连了.
假设列队头部指针为front,尾指针为rear.当数组全部容量用来装队列元素时,由于数组满的时候和空的时候都是front==rear,为了区分队列是满还是空有两种方法.
1.使用一个额外的变量size来表示元素个数,但元素个数等于数组容量maxSize时表示满了
2.不使用额外变量,而是让元素总个数比数组容量小1,这样当队列头指针等于尾指针时表示为空,两者相减为1时表示满了.
根据方法1实现的队列
#include <iostream>
using namespace std;
const static int QUE_SIZE = 100;
template<class T>
class QueArray
{
private:
T* m_pArray; //表示队列的数组
int m_nSize; //当前元素个数
int m_nMaxSize; //数组可容纳最大元素数量
int front; //队头部
int rear; //队列尾部
public:
QueArray(int nMaxSize = QUE_SIZE){
m_nMaxSize = nMaxSize;
m_pArray = new T[m_nMaxSize];
m_nSize = front = rear = 0;
}
~QueArray(void){ delete []m_pArray;}
bool IsFull(){ return m_nSize > m_nMaxSize ;}
bool IsEmpty(){ return m_nSize ==0;}
int Size(){ return m_nSize;}
void Clear() { m_nSize = front = rear = 0; }
bool EnQue(T val){ //队列尾部添加元素
if(IsFull()){
cout<<"queue is full."<<endl;
return false;
}
m_pArray[rear] = val;
rear = (rear + 1) % m_nMaxSize;
m_nSize++;
}
T GetRear() { //返回队列尾部元素
if(IsEmpty()){
cout<<"queue is empty"<<endl;
return NULL;
}
return m_pArray[rear -1];
}
T DeQue(){ //返回队列头部元素并删除
if(IsEmpty()){
cout<<"queue is empty"<<endl;
return NULL;
}
T val = m_pArray[front];
front = (front + 1) % m_nMaxSize;
m_nSize --;
return val;
}
T GetFront(){ //返回头部元素
if(IsEmpty()){
cout<<"queue is empty"<<endl;
return NULL;
}
return m_pArray[front];
}
};
根据方法2实现的队列
#include <iostream>
using namespace std;
const static int QUE_SIZE = 100;
template<class T>
class QueArray
{
private:
T* m_pArray; //队列数组
int m_nMaxSize; //可容纳最大元素个数
int front; //头部元素
int rear; //尾部元素
public:
QueArray(int nMaxSize = QUE_SIZE){
m_nMaxSize = nMaxSize;
m_pArray = new T[m_nMaxSize + 1]; //数组元素比最大容量大1
front = rear = 0;
}
~QueArray(void){ delete []m_pArray;}
bool IsFull(){ return (rear+1)%m_nMaxSize == front;}
bool IsEmpty(){ return front == rear;}
int Size(){ return m_nSize;}
void Clear() { m_nSize = front = rear = 0; }
bool EnQue(T val){
if(IsFull()){
cout<<"queue is full."<<endl;
return false;
}
m_pArray[rear] = val;
rear = (rear + 1) % m_nMaxSize;
}
T GetRear() {
if(IsEmpty()){
cout<<"queue is empty"<<endl;
return NULL;
}
return m_pArray[rear -1];
}
T DeQue(){
if(IsEmpty()){
cout<<"queue is empty"<<endl;
return NULL;
}
T val = m_pArray[front];
front = (front + 1) % m_nMaxSize;
return val;
}
T GetFront(){
if(IsEmpty()){
cout<<"queue is empty"<<endl;
return NULL;
}
return m_pArray[front];
}
};