数据结构学习记录连载8（堆栈提高要求续）

说明：提高要求的链式堆栈实现与测试

1.StackNode.h：链式堆栈的结点类

/*
* Copyright (c) 2009,FreshAir团队嵌入式软件研发组
* All rights reserved.
*
* 文件名称：StackNode.h
* 摘 要：堆链式栈类的定义与实现
*
* 当前版本：1.0
* 作 者：吴友强
* 完成日期：2009年10月13日
*
* 取代版本：
* 原作者 ：
* 完成日期：
*/
template <class T> class LinkStack;//前向声明

template <class T>
class StackNode
{
friend class LinkStack<T>;
private:
StackNode<T> *next;
public:
T data;

StackNode(const T& item, StackNode<T> *ptrNext = NULL)
{
data = item;
next = ptrNext;
}

~StackNode(){}
};

2.LinkStack.h：定义链式堆栈类和实现接口

/*
* Copyright (c) 2009,FreshAir团队嵌入式软件研发组
* All rights reserved.
*
* 文件名称：LinkStack.h
* 摘 要：堆链式栈类的定义与实现
*
* 当前版本：1.0
* 作 者：吴友强
* 完成日期：2009年10月13日
*
* 取代版本：
* 原作者 ：
* 完成日期：
*/

#include "StackNode.h"
template <class T>
class LinkStack
{
private:
StackNode<T> *top;
int size;
public:
LinkStack(void);
~LinkStack(void);

int StackSize(void) const;//堆栈数据个数
int StackEmpty(void) const;//堆栈是否为空（返回1）
void Push(const T& item);//入栈
T Pop(void);//出栈
T Peek(void);//返回栈顶数据
void ClearStack(void);//清空堆栈
};

template <class T>
LinkStack<T>::LinkStack(void)
{
top = NULL;
size = 0;
}

template <class T>
LinkStack<T>::~LinkStack(void)
{
ClearStack();
top = NULL;
}

template <class T>
int LinkStack<T>::StackSize(void) const
{
return size;
}

template <class T>
int LinkStack<T>::StackEmpty(void) const
{
return size == 0 ? 1 : 0;
}

/*
* 函数名称: Push
* 输　入:item
*item:压入堆栈的数据
* 输　出:
* 功能描述: 将item入栈
* 作　者:吴友强
* 日　期:2009年10月17日
* 修　改:
* 日　期:
*/
template <class T>
void LinkStack<T>::Push(const T& item)
{
StackNode<T> *newNode = new StackNode<T>(item, top);
top = newNode;
size++;
}

template <class T>
T LinkStack<T>::Pop(void)
{
if (size == 0)
{
cout << "堆栈以空无元素可删除" << endl;
exit(0);
}

StackNode<T> *p = top->next;
T data = top->data;
delete top;
size--;
top = p;
return data;
}

template <class T>
T LinkStack<T>::Peek(void)
{
return top->data;
}

template <class T>
void LinkStack<T>::ClearStack(void)
{
StackNode<T> *p, *q;

p = top;
while (p != NULL)
{
q = p;
p = p->next;
delete q;
}
size = 0;
}

3.LinkStackTest.cpp：测试程序，计算后缀表达式（加减乘除）

/*
* Copyright (c) 2009,FreshAir团队嵌入式软件研发组
* All rights reserved.
*
* 文件名称：LinkStackTest.cpp
* 摘 要：测试链式堆栈的功能,计算后缀表达式（加减乘除）
*
* 当前版本：1.0
* 作 者：吴友强
* 完成日期：2009年10月17日
*
* 取代版本：
* 原作者 ：
* 完成日期：
*/

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

#include "LinkStack.h"

/*
* 函数名称: Insert
* 输　入:s
* s:用作存储的数据结构
* 输　出:
* 功能描述: 借助堆栈s计算后缀表达式的值后屏幕输出
* 作　者:吴友强
* 日　期:2009年10月17日
* 修　改:
* 日　期:
*/
template <class T>
void PostExp(LinkStack<T> &s)
{
char ch;
T x, x1, x2;

cout << "输入后缀表达式，结尾加符号#" << endl;

while (cin >> ch, ch != '#')//输入字符直到输入为'#'
{
if (isdigit(ch))//ch为操作数
{
cin.putback(ch);//回退一位
cin >> x;//输入数值给变量x
s.Push(x);//数值入栈
}
else//ch为操作符
{
x2 = s.Pop();//退栈得操作数
x1 = s.Pop();//退栈得被操作数
switch (ch)
{
case '+':
{
x1 += x2;
break;
}
case '-':
{
x1 -= x2;
break;
}
case '*':
{
x1 *= x2;
break;
}
case '/':
{
x1 /= x2;
break;
}
default:
break;
}
s.Push(x1);//操作结果入栈
}
}
cout << "后缀表达式计算结果为：" << s.Pop() << endl;
}

int main()
{
LinkStack<int> s;
PostExp(s);

return 0;
}