數據結構學習記錄連載10（隊列提高要求實現）

1.QueueNode.h：鏈式隊列結點類定義

/*
* Copyright (c) 2009,FreshAir團隊嵌入式軟件研發組
* All rights reserved.
*
* 文件名稱：QueueNode.h

* 摘 要： 鏈式隊列結點類定義
*
* 當前版本：1.0
* 作 者： 吳友強
* 完成日期：2009年10月19日
*
* 取代版本：
* 原作者 ：
* 完成日期：
*/

#include <iostream.h>
#include <stdlib.h>
template <class T> class LinkQueue;

template <class T>
class QueueNode
{
 friend class LinkQueue<T>;
private:
 QueueNode<T> *next;
public:
 T data;

 //構造函數
 QueueNode(const T& item, QueueNode<T> *ptrNext = NULL)
 {
  data =item;
  next = ptrNext;
 }

 ~QueueNode() {};
};

2.LinkQueue.h：鏈式隊列模板類的定義與接口實現

/*
* Copyright (c) 2009,FreshAir團隊嵌入式軟件研發組
* All rights reserved.
*
* 文件名稱：LinkQueue.h
* 摘 要： 鏈式隊列模板類的定義與接口實現
*
* 當前版本：1.0
* 作 者： 吳友強
* 完成日期：2009年10月19日
*
* 取代版本：
* 原作者 ：
* 完成日期：
*/

#include "QueueNode.h"

template <class T>
class LinkQueue
{
private:
 QueueNode<T> *front;
 QueueNode<T> *rear;
 int size;
public:
 LinkQueue(void);
 ~LinkQueue(void);

 void QueueInsert(const T& item);
 T QueueDelete(void);
 T QueueFront(void) const;
 int QueueIsEmpty(void) const
 {
  return size <= 0;
 }

 void ClearQueue(void);
 int GetQueueSize(void) const
 {
  return size;
 }
};

template <class T>
LinkQueue<T>::LinkQueue()
{
 front = rear = NULL;
 size = 0;
}

template <class T>
LinkQueue<T>::~LinkQueue()
{
 ClearQueue();
 front = rear = NULL;
}

/*
* 函數名稱: QueueInsert
* 輸　入: item
* item: 需要插入的數據
* 輸　出:
* 功能描述: 將item插入到隊列中
* 作　者: 吳友強
* 日　期: 2009年10月19日
* 修　改:
* 日　期:
*/
template <class T>
void LinkQueue<T>::QueueInsert(const T& item)
{
 QueueNode<T> *newNode = new QueueNode<T>(item, NULL);

 if (rear != NULL)   //原先不為空鏈時才要連接
 {
  rear->next = newNode;
 }

 rear = newNode;    //新結點為隊尾結點

 if (front == NULL)
 {
  front = newNode;  //原先為空鏈時給front賦值
 }

 size++;
}

/*
* 函數名稱: QueueDelete
* 輸　入: 
* 輸　出:
* 功能描述: 刪除隊列頭部的一個數據
* 作　者: 吳友強
* 日　期: 2009年10月19日
* 修　改:
* 日　期:
*/
template <class T>
T LinkQueue<T>::QueueDelete()
{
 if (size == 0)
 {
  cout << "隊列以空無元素可刪!" << endl;
  exit(0);
 }

 QueueNode<T> *p = front->next;
 T data = front->data;
 delete front;
 front = p;
 size--;
 return data;
}

/*
* 函數名稱: QueueFront
* 輸　入: 
* 輸　出:
* 功能描述: 訪問隊列頭部的一個數據
* 作　者: 吳友強
* 日　期: 2009年10月19日
* 修　改:
* 日　期:
*/
template <class T>
T LinkQueue<T>::QueueFront() const
{
 return front->data;
}

/*
* 函數名稱: ClearQueue
* 輸　入: 
* 輸　出:
* 功能描述: 清空隊列
* 作　者: 吳友強
* 日　期: 2009年10月19日
* 修　改:
* 日　期:
*/
template <class T>
void LinkQueue<T>::ClearQueue()
{
 QueueNode<T> *p, *q;

 p = front;
 while (p != NULL)
 {
  q = p;
  p = p->next;
  delete q;
 }

 size = 0;
}

3.LinkQueueTest.cpp：用鏈式堆棧和隊列實現回文判斷

/*
* Copyright (c) 2009,FreshAir團隊嵌入式軟件研發組
* All rights reserved.
*
* 文件名稱：LinkQueueTest.cpp
* 摘 要： 用鏈式堆棧和隊列實現回文判斷
*
* 當前版本：1.0
* 作 者： 吳友強
* 完成日期：2009年10月19日
*
* 取代版本：
* 原作者 ：
* 完成日期：
*/

#include <iostream.h>
#include <stdlib.h>
#include <string.h>

#include "LinkQueue.h"
#include "LinkStack.h"

void main(void)
{
 LinkStack<char> myStack;
 LinkQueue<char> myQueue;

 char str[80];

 cout << "輸入字符序列，回車換行結束：" << endl;
 cin.getline(str, 80);
 int h = strlen(str);
 cout << "h = " << h << endl;

 for (int i=0; i<h; i++)
 {
  myQueue.QueueInsert(str[i]);
  myStack.Push(str[i]);
 }

 while (!myQueue.QueueIsEmpty())
 {
  if (myQueue.QueueDelete() != myStack.Pop())
  {
   cout << "不是回文！" << endl;
   return ;
  }
 }

 cout << "是回文！" << endl;
}