数据结构学习记录连载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;
}