实验2 栈、队列及应用
一、实验目的
1.掌握栈和队列的设计和实现栈和队列的基本操作；
2.能根据实际问题的需要灵活运用栈和队列，掌握栈和队列的应用方法；
3.了解递归算法的非递归化方法；
4.掌握栈、队列的思想及其存储实现。
5.掌握栈、队列的常见算法的程序实现。
二、实验学时：建议2~4学时
三、基本知识
四、实验内容
内容1 回文问题（或数制转换、括号匹配问题）
1 问题描述
顺读与逆读内容都一样的字符串（不计空格）称为回文。如字符串：“madam im adam”，”dad”都是回文。
设计算法判别一个字符串是否是回文，要求利用栈实现回文的判别。
注：这里选择比较简单的应用实例，让学生容易学会栈的基本使用方法。
2 数据结构设计
字符串可以采用顺序表或链表存储，回文判别过程中的栈可采用链栈结构，为方便以后栈类的重用，栈类设计成模板类，另外设计一个回文类。
（1）链栈结点结构设计
链栈结点结构与单链表结点结构类似。
template
struct StackNode
{ //链栈结点类
T data; //栈结点数据
StackNode *link; //结点链指针
StackNode():link(NULL) { } //构造函数
StackNode(T d,StackNode *next=NULL):data(d),link(next){ }
//构造函数
};
（2）链栈类设计
根据栈的特点，链栈类数据成员有栈顶指针，成员函数有构造、入栈、出栈、栈的判空与判满、访问栈顶元素、销毁等操作。
template
class LinkedStack
{ //链栈类
private:
StackNode *top; //栈顶指针
public:
LinkedStack() : top(NULL) {} //构造函数
~LinkedStack() { makeEmpty();} //析构函数
void push(const T&x); //进栈
bool pop(T& x); //退栈
bool getTop(T& x) const; //取栈顶
bool IsEmpty() const { return top == NULL; }
void makeEmpty(); //清空栈的内容
};
（3）回文类
class palindrome //回文问题类
{
private:
char *str;
void removeBlankSpace ();//过滤判别字符串中的空格字符，可选public:
palindrome(char*s)//构造函数
{
str=new char[strlen(s)+1];
strcpy(str,s);
}
bool palindromeJudge();//回文判别
void setString(char*s);//重新设置判别字符串
void printString(){cout<3 算法设计与实现
（1）回文判别
a)原理：借助于栈，先将字符串中的字符依次入栈，重新扫描字符串，并
依次与栈顶字符比较，若匹配则栈顶元素出栈，并向后扫描，否则不是回文，若扫描完毕都匹配则是回文。
b)算法步骤：
i)初始化，过滤字符串中的空格字符（初学者也可假设字符串中不含空格
字符，跳过该步骤）；
ii)将字符串中的字符依次入栈S；
iii)原串字符依次与栈S的栈顶字符比较：
若不匹配，则返回结果“字符串不是回文”，否则栈顶字符出栈。
直到栈空，则返回结果“字符串是回文”。
c)实现
bool palindrome::palindromeJudge()//回文判别
{ //判断字符串str是否为回文
removeBlankSpace ();// 过滤str中的空格字符，也可以将该步骤略去
LinkedStack S;
char *p=str, ch;
while(*p) //将字符串str中的字符依次入栈
S.push(*p++);
p=str;
while(!S.IsEmpty())//当栈非空时
{
S.pop(ch);
if(ch!=*p) //栈顶元素与字符串中字符比较，若不匹配
{
S. makeEmpty();//先将链栈空间释放
return false; //不是回文
}
p++;
}
return true; //是回文
}// palindrome
（2）过滤空格字符操作//可作为选做内容处理
过滤空格字符的方法很多，可以将字符串看成是线性表，扫描线性表，若遇到空格字符就删除，这种方法优点是简单、易于理解，缺点是元素前移较多、效率较低。当然也可以采用遇到空格字符自动跳过的方法。这里采用的是每次只将扫描到的非空格字符前移的方法，效率较高。
a)原理
p指针是用来扫描字符串，s指针是用来指示p所指字符前移的位置，如下图所示，p指向非空格字符’d’，则将p指向字符前移到s所指位置，
如下图，此时p指向空格字符，则只要将p指针后移即可。
