// MyQueue.cpp : 定義控制臺(tái)應(yīng)用程序的入口點(diǎn)。
//實(shí)現(xiàn)鏈?zhǔn)疥?duì)列（queue），包括一個(gè)頭結(jié)點(diǎn)。隊(duì)列操作包括在隊(duì)頭出隊(duì)（pop）、在隊(duì)尾入隊(duì)（push）、
//取得隊(duì)頭元素（front_element)、取得隊(duì)尾元素（back_element）、隊(duì)列元素個(gè)數(shù)（size）、
//隊(duì)列是否為空（empty）。
#include "stdafx.h"
#include <iostream>
using namespace std;
//定義隊(duì)列的節(jié)點(diǎn)結(jié)構(gòu)
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;
 }
//在隊(duì)尾入隊(duì)
 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;
 }
//在隊(duì)頭出隊(duì)
 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;
   //注意判斷當(dāng)只有一個(gè)元素，且刪除它之后，rear指向的node被刪除
   //應(yīng)將其指向頭結(jié)點(diǎn)
   if (rear == p)
   {
    rear = front;
   }
   delete p; p = NULL;
   return e;
  }
 }
 //取得隊(duì)頭元素
 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;
  }
 }

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

 //判斷隊(duì)列是否為空
 bool empty()
 {
  if (front == rear)
  {
   return true;
  }
  else
  {
   return false;
  }
 }
private:
 NODE<T>* front; //指向頭結(jié)點(diǎn)的指針。 front->next->data是隊(duì)頭第一個(gè)元素。
 NODE<T>* rear;//指向隊(duì)尾（最后添加的一個(gè)元素）的指針
};
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;
}