資料結構與算法-----隊列-使用連結清單（鍊式結構）實作

資料結構：隊列結構特點

1.基本特征：先進先出

2.基本操作：從後端(rear)壓入(push)，從前端(front)彈出(pop)

3.實作要點：初始化空間、從後端指針壓入，從前端指針彈出，判空（連結清單結構隻需要判空，不考慮容量不足情況）

下面使用連結清單實作隊列結構，那麼成員變量就是front和rear兩個節點結構的指針變量，front指向前端，rear指向後端

#include <iostream>
using namespace std;
class Queue{
public:
	Queue(void):front(NULL),rear(NULL){}
	~Queue(void){
		for(Node *p;front;front=p){
			p=p->next;
			delete front;	
		}	
	}
	void push(int data){
		Node *node=new Node(data);
		if(rear)
			rear->next=node;
		else//如果是第一個節點，那麼需要把front也指向node
			front=node;	
		rear=node;
	}
	int pop(){
		if(empty())
			throw UnderFlow();
		int pdata;
		Node *p=front;
		pdata=front->data;
		delete front;
		front=NULL;
		front=p->next;	
		if(front==NULL)//如果删除的是最後一個節點，那麼需要把rear也置為NULL
			rear=NULL;	
		return pdata;	
	}
	bool empty(){
		return rear==NULL && front==NULL;	
	}
private:
	class UnderFlow:public exception{
	public:
		const char* what() const throw(){
			return "下溢";	
		}	
	};
	class Node{
		public:
			Node(int pdata=0,Node *pnext=NULL):data(pdata),next(pnext){}
			~Node(void){}
			int data;
			Node *next;
	};
	Node *front;//前端
	Node *rear;//後端
};
int main(){
	try{
		Queue q;
		for(int i=1;i<=10;++i){
			q.push(i);
		}
		while(!q.empty())
			cout<<q.pop()<<endl;
	}
	catch(exception& ex){
		cout << ex.what() << endl;
		return -1;
	}	
}</span>