隊列的鏈接存儲結構——鏈隊列
圖解：
LinkQueue.h
[cpp]
//LinkQueue.h
#ifndef LINKQUEUE_H
#define LINKQUEUE_H
template <class T>
struct Node
{
T data;
Node<T> *next; //此處<T>也可以省略
};
template <class T>
class LinkQueue
{
public:
LinkQueue( ); //構造函數，初始化一個空的鏈隊列
~LinkQueue( ); //析構函數，釋放鏈隊列中各結點的存儲空間
void EnQueue(T x); //將元素x入隊
T DeQueue( ); //將隊頭元素出隊
T GetQueue( ); //取鏈隊列的隊頭元素
bool Empty( ); //判斷鏈隊列是否為空
private:
Node<T> *front, *rear; //隊頭和隊尾指針，分別指向頭結點和終端結點
};
#endif;
LinkQueue.cpp
[cpp]
//LinkQueue.cpp
#include "LinkQueue.h"
/*
* 前置條件：隊列不存在
* 輸 入：無
* 功 能：初始化隊列
* 輸 出：無
* 後置條件：創建一個空隊列
*/
template <class T>
LinkQueue<T>::LinkQueue( )
{
Node <T> *s;
s=new Node<T>;
s->next=NULL;
front=rear=s;
}
/*
* 前置條件：隊列存在
* 輸 入：無
* 功 能：銷毀隊列
* 輸 出：無
* 後置條件：釋放隊列所占用的存儲空間
*/
template <class T>
LinkQueue<T>::~LinkQueue( )
{
while(front)
{
Node <T> *p;
p=front->next;
delete front;
front=p;
}
}
/*
* 前置條件：隊列已存在
* 輸 入：元素值s
* 功 能：在隊尾插入一個元素
* 輸 出：無
* 後置條件：如果插入成功，隊尾增加了一個元素
*/
template <class T>
void LinkQueue<T>::EnQueue(T x)
{
Node<T> *s;
s=new Node<T>;
s->data=x; //申請一個數據域為x的結點s
s->next=NULL;
rear->next=s; //將結點s插入到隊尾
rear=s;
}
/*
* 前置條件：隊列已存在
* 輸 入：無
* 功 能：刪除隊頭元素
* 輸 出：如果刪除成功，返回被刪元素值，否則，拋出刪除異常
* 後置條件：如果刪除成功，隊頭減少了一個元素
*/
template <class T>
T LinkQueue<T>::DeQueue()
{
Node <T> *p; int x;
if (rear==front) throw "下溢";
p=front->next;
x=p->data; //暫存隊頭元素
front->next=p->next; //將隊頭元素所在結點摘鏈
if (p->next==NULL) rear=front; //判斷出隊前隊列長度是否為1
delete p;
return x;
}
/*
* 前置條件：隊列已存在
* 輸 入：無
* 功 能：讀取隊頭元素
* 輸 出：若隊列不空，返回隊頭元素
* 後置條件：隊列不變
*/
template <class T>
T LinkQueue<T>::GetQueue()
{
if (front!=rear)
return front->next->data;
}
/*
* 前置條件：隊列已存在
* 輸 入：無
* 功 能：判斷隊列是否為空
* 輸 出：如果隊列為空，返回1，否則，返回0
* 後置條件：隊列不變
*/
template <class T>
bool LinkQueue<T>::Empty( )
{
if(front==rear)
return 1;
else
return 0;
}
