队列

定义
一种先进先出的线性表，只允许从一段插入元素，从另一端删除元素。允许删除的叫队头（front),允许删除的叫队尾（rear）。
基本操作
- 初始化
- 求长度
- 取队头元素
- 入队
- 出队
- 判断队空
- 清空队列
常见存储方式：顺序存储（循环队列形式）与链式存储

循环队列

由于队列先进先出的性质，如果设置为简单的顺序存储方式，存在这种情况：入队至队满，再出队，此时想要入队是不行的，但对于我们开辟的空间来说并没有完全使用，因此将一般的顺序存储的队列改为循环队列，解决假溢出的现象。

循环队列类模板定义
元素：队头指针、队尾指针、maxsize、存储数据元素的数组elems
主要成员函数：构造函数、析构、入队与出队函数

template<class ElemType>
class SeqQueue
{
protected:
   int front, rear;									 // 队头队尾指针
   int maxSize;										 // 队列容量
   ElemType* elems;									 // 元素存储空间
public:
   SeqQueue(int size = DEFAULT_SIZE);					 // 构造函数
   virtual ~SeqQueue();								 // 析构函数
   int GetLength() const;								 // 求队列长度
   bool IsEmpty() const;								 // 判断队列是否为空
   bool IsFull() const;                                 //判断队列是否为满
   void Clear();										 // 将队列清空
   void Traverse(void (*Visit)(const ElemType&)) const; // 遍历队列
   Status DelQueue(ElemType& e);					     // 出队操作
   Status GetHead(ElemType& e) const;				     // 取队头操作
   Status EnQueue(const ElemType e);				     // 入队操作
   SeqQueue(const SeqQueue<ElemType>& q);			     // 复制构造函数
   SeqQueue<ElemType>& operator =(const SeqQueue<ElemType>& q);// 赋值语句重载
};

判空判满代码实现
template<class ElemType>
bool SeqQueue<ElemType>::IsEmpty() const
// 操作结果：如队列为空，则返回true，否则返回false
{
return rear==front;
}
template<class ElemType>
bool SeqQueue<ElemType>::IsFull() const
{
return (rear+1)% maxsize==front;
}
对于循环队列的判空判满存在有一个问题：无论在队满还是队空的情况下都是front==rear；这会带来歧义，所以有以下几种处理方式。
- 如上述的代码，少用一个存储空间，当（rear+1)%maxsize==front时即为队满。
- 增加一个flag指标，队列为空时flag为0，队列为满时，flag为1。
- 最简单的方法是加入一个类内元素length，length等于maxsize则为满，length==0 则为空。

入队出队代码实现

template<class ElemType>
Status SeqQueue<ElemType>::EnQueue(const ElemType e)
// 操作结果：如果队列已满，返回OVER_FLOW,
// 否则插入元素e为新的队尾，返回SUCCESS
{
   if (IsFull())
      return OVER_FLOW;
   else {	// 队列未满，入队成功
      elems[rear] = e;					// 插入e为新队尾
      rear = (rear + 1) % maxSize;
      return SUCCESS;
   }
}

入队判满，直接写入到队尾。

template<class ElemType>
Status SeqQueue<ElemType>::DelQueue(ElemType& e)
// 操作结果：如果队列非空，那么删除队头元素，并用e返回其值，函数返回SUCCESS,
// 否则函数返回UNDER_FLOW，
{
   if (!IsEmpty()) {
      e = elems[front];					// 用e返回队头元素
      front = (front + 1) % maxSize;		// front指向下一元素
      return SUCCESS;
   }
   else
      return UNDER_FLOW;
}

出队判空，front后移。

注意点
- 循环队列可以使用front和rear的组合表示整个队列，也可以使用front和length的组合，这种组合的实现是基于front+length==rear，本质与另一个组合没有区别，但是由于length的加入使得判空判满不需要借助额外的工具，所以值得推荐。
- front与rear的初值有不同的设置，可以都为0，也可以都为-1。两者没有本质区别，只是在入队与出队的过程中会有初值的差异。

链式队列

链式队列是队列的另一种存储方式，这里使用带头结点的单链表表示。入队是在单链表的表尾加一个结点，出队是在表头删除一个结点
问题：
1）队头、队尾交换，操作是否方便？
- 不方便在尾部删除需要遍历找前驱。
2）带头结点的单链表表示链式队列，有什么方便及不方便？
- 带头结点的单链表删除头，只要找head的next就可以了。不方便在于多了一个头结点
3）有无必要定义循环队列？循环队列有什么方便及不方便？
- 没有必要，顺序存储定义循环是为了避免假溢出，但是链式队列根本不会出现假溢出这种现象，所以没必要定义。如果定义了，可以使得删除插入只用一个指针完成，但是，也会造成找不到头尾的情况。

链式对列类模板定义
元素：头尾指针
成员函数：构造析构、入队出队等

template<class ElemType>
class LinkQueue
{
protected:
   //  链队列实现的数据成员:
   Node<ElemType>* front, * rear;					// 队头队尾指指
public:
   LinkQueue();									// 无参数的构造函数
   virtual ~LinkQueue();							// 析构函数
   int GetLength() const;								// 求队列长度
   bool IsEmpty() const;								// 判断队列是否为空
   void Clear();									// 将队列清空
   void Traverse(void (*Visit)(const ElemType&)) const;	// 遍历队列
   Status DelQueue(ElemType& e);				     // 出队操作
   Status GetHead(ElemType& e) const;			     // 取队头操作
   Status EnQueue(const ElemType e);			     // 入队操作
   LinkQueue(const LinkQueue<ElemType>& q);		// 复制构造函数
   LinkQueue<ElemType>& operator =(const LinkQueue<ElemType>& q);// 赋值语句重载
};

入队出队代码实现

template<class ElemType>
Status LinkQueue<ElemType>::DelQueue(ElemType& e)
// 操作结果：如果队列非空，那么删除队头元素，并用e返回其值，函数返回SUCCESS,
//	否则函数返回UNDER_FLOW，
{
   if (!IsEmpty()) {	// 队列非空
      Node<ElemType>* p = front->next;	// 指向队列头素
      e = p->data;						// 用e返回队头元素
      front->next = p->next;				// front指向下一元素
      if (rear == p)	// 出队前队列中只有一个元素，出队后为空队列
         rear = front;
      delete p;							// 释放出队的元素结点
      return SUCCESS;
   }
   else
      return UNDER_FLOW;
}

出队先判空，因为有头结点，所以先创建一个临时指针，然后用e返回第一个结点的元素值，再修改front->next的值，判断是否出队后为空队列，最后删除临时指针。

template<class ElemType>
Status LinkQueue<ElemType>::EnQueue(const ElemType e)
// 操作结果：如果系统空间不够，返回OVER_FLOW,
//	否则插入元素e为新的队尾，返回SUCCESS
{
   Node<ElemType>* p;
   p = new Node<ElemType>(e);	        // 生成一个新结点
   if (p) {
      rear->next = p;	                // 将新结点加在队尾
      rear = rear->next;				// rear指向新队尾
      return SUCCESS;
   }
   else                               //系统空间不够，返回OVER_FLOW
      return OVER_FLOW;
}

入队在确定成功申请内存空间后，在队尾写入元素。