// MyQueue.cpp : 定義控制臺應用程序的入口點。
//實現鏈式隊列（queue），包括一個頭結點。隊列操作包括在隊頭出隊（pop）、在隊尾入隊（push）、
//取得隊頭元素（front_element)、取得隊尾元素（back_element）、隊列元素個數（size）、
//隊列是否為空（empty）。
#include "stdafx.h"
#include <iostream>
using namespace std;
//定義隊列的節點結構
template <class T>
struct NODE
{
?NODE<T>* next;
?T data;
};
template <class T>
class MyQueue
{
public:
?MyQueue()
?{
??NODE<T>* p = new NODE<T>;
??if (NULL == p)
??{
???cout << "Failed to malloc the node." << endl;
??}
??p->data = NULL;
??p->next = NULL;
??front = p;
??rear = p;
?}
//在隊尾入隊
?void push(T e)
?{
??NODE<T>* p = new NODE<T>;
??if (NULL == p)
??{
???cout << "Failed to malloc the node." << endl;
??}
??p->data = e;
??p->next = NULL;
??rear->next = p;
??rear = p;
?}
//在隊頭出隊
?T pop()
?{
??T e;
??if (front == rear)
??{
???cout << "The queue is empty." << endl;
???return NULL;
??}
??else
??{
???NODE<T>* p = front->next;
???front->next = p->next;
???e = p->data;
???//注意判斷當只有一個元素，且刪除它之后，rear指向的node被刪除
???//應將其指向頭結點
???if (rear == p)
???{
????rear = front;
???}
???delete p; p = NULL;
???return e;
??}
?}
?//取得隊頭元素
?T front_element()
?{
??if (front == rear)
??{
???cout << "The queue is empty." << endl;
???return NULL;
??}
??else
??{
???NODE<T>* p = front->next;
???return p->data;
??}
?}
?T back_element()
?{
??if (front == rear)
??{
???cout << "The queue is empty." << endl;
???return NULL;
??}
??else
??{
???return rear->data;
??}
?}

?//取得隊列元素個數
?int size()
?{
??int count(0);
??NODE<T>* p = front;
??while (p != rear)
??{
???p = p->next;
???count++;
??}
??return count;
?}

?//判斷隊列是否為空
?bool empty()
?{
??if (front == rear)
??{
???return true;
??}
??else
??{
???return false;
??}
?}
private:
?NODE<T>* front; //指向頭結點的指針。 front->next->data是隊頭第一個元素。
?NODE<T>* rear;//指向隊尾（最后添加的一個元素）的指針
};
int _tmain(int argc, _TCHAR* argv[])
{
?MyQueue<int> myqueue;
?cout << myqueue.size() << endl;
?myqueue.push(10);
?myqueue.push(20);
?myqueue.push(30);
?cout << myqueue.front_element() << endl;
?cout << myqueue.back_element() << endl;
?myqueue.pop();
?if (myqueue.empty())
?{
??cout << "The queue is empty now." << endl;
?}
?else
?{
??cout << "The queue has " << myqueue.size() << " elements now." << endl;
?}
?myqueue.pop();
?myqueue.pop();
?if (myqueue.empty())
?{
??cout << "The queue is empty now." << endl;
?}
?else
?{
??cout << "The queue has " << myqueue.size() << " elements now." << endl;
?}
?return 0;
}