栈
栈
-
定义
只允许在表的末端进行插入和删除的线性表。允许插入删除的叫栈顶，不允许插入删除的叫栈底。其性质为后进先出。 -
基本操作
- 初始化
- 求长度
- 取栈顶元素
- 入栈
- 出栈
- 判断栈是否为空
- 清空栈
-
常见存储方式：顺序存储与链式存储
顺序存储
-
顺序栈的类模板定义
元素：栈顶指针（下标形式）、最大容量、数据元素的数组（elems）
函数：构造函数、析构函数、入栈、出栈、求长度等等。 -
注意点
- 对于top指针的初值可以设置为两种，-1或0。在本文中设置为-1.
- 不同的top初值在写函数时操作完全不同。主要体现在入栈与出栈上
top==-1，先加一，再入栈；先出栈，再减一。
top== 0 , 先入栈，再加一；先减一，再出栈。
-
类模板定义
template<class ElemType>
class SeqStack
{
protected:
// 顺序栈的数据成员:
int top1; // 栈顶指针
int maxSize; // 栈的最大容量
ElemType* elems; // 元素存储空间
public:
// 顺序栈的方法声明及重载编译系统默认方法声明:
SeqStack(int size = DEFAULT_SIZE); // 构造函数
virtual ~SeqStack(); // 析构函数
int GetLength() const; // 求栈的长度
bool IsEmpty() const; // 判断栈是否为空
void Clear(); // 将栈清空
void Traverse(void (*Visit)(const ElemType&)) const; // 遍历栈
Status Push(const ElemType e); // 入栈
Status Top(ElemType& e) const; // 取顶元素
Status Pop(ElemType& e); // 出栈
SeqStack(const SeqStack<ElemType>& s); // 复制构造函数
SeqStack<ElemType>& operator =(const SeqStack<ElemType>& s);
// 赋值语句重载
}; -
入栈出栈代码
template<class ElemType>// 入栈
Status SeqStack<ElemType>::Push(const ElemType e)
// 操作结果：将元素e追加到栈顶,如成功则返加SUCCESS,如栈已满将返回OVER_FLOW
{
if (top == maxSize - 1) // 栈已满
return OVER_FLOW;
else { // 操作成功
elems[++top] = e; // 将元素e追加到栈顶
return SUCCESS;
}
}注意点：入栈判满；top初值为-1，先加一，再入栈。
template<class ElemType>
Status SeqStack<ElemType>::Pop(ElemType& e)
// 操作结果：如栈非空,删除栈顶元素,并用e返回栈顶元素,函数返回SUCCESS,否则
// 函数返回UNDER_FLOW
{
if (IsEmpty()) // 栈空
return UNDER_FLOW;
else { // 操作成功
e=elems[top--];
return SUCCESS;
}
}**注意点：出栈判空；top初值为-1，先出栈，再减一。
-
共享数组的顺序栈
对于顺序存储来说，存储空间很浪费，而且容易产生溢出现象，因此共享数组的顺序栈存储方式出现了。其本质是将一个顺序栈放在数组头，另一个放在数组的尾，等于共享顶部的资源空间。- 栈满情况 top1== top2-1
- 栈空情况 top1等于0 并且 top2等于 maxsize
- 对于栈的基本操作需要指明具体操作哪一个栈，所以对基本所有的类内成员函数需要多加一个参数no来确定要操作的是哪一个栈。
修改后的类模板定义如下
template<class ElemType>
class SeqStack
{
protected:
// 顺序栈的数据成员:
int top1,top2; // 栈顶指针
int maxSize; // 栈的最大容量
ElemType* elems; // 元素存储空间
public:
// 顺序栈的方法声明及重载编译系统默认方法声明:
SeqStack(int size = DEFAULT_SIZE); // 构造函数
virtual ~SeqStack(); // 析构函数
int GetLength() const; //求长度
bool IsEmpty(int no) const; // 判断栈是否为空
void Clear(); // 将栈清空
void Traverse(void (*Visit)(const ElemType&),int no) const; // 遍历栈
Status Push(const ElemType e); // 入栈
Status Top(ElemType& e,int no) const; // 取顶元素
Status Pop(ElemType& e,int no); // 出栈
SeqStack(const SeqStack<ElemType>& s); // 复制构造函数
SeqStack<ElemType>& operator =(const SeqStack<ElemType>& s); // 赋值语句重载
};
链式存储
-
对于链式栈采用链表的方式存储元素，可以同时让多个栈共享存储。这里主要使用不带表头的单链表实现链式栈。表头为栈顶，入栈出栈都是对表头进行操作。
问题：
1）栈顶放在链表的头部/尾部，哪个操作起来方便？- 表头，因为表尾不便于删除，每次删除都需要遍历找前驱。
2）带头结点和不带头结点相比，有多大影响？
- 不带头结点链表的入栈出栈都在表头进行，比较简单方便。
3）和链表相比，类定义主要不同点在哪里？
- 主要区别在于链式栈只对头结点操作，而链表有插入删除等等对于中间结点的操作。
-
链式栈类模板定义
元素：只需要一个栈顶指针即可
成员函数：构造函数、析构函数、入栈与出栈、判空template<class ElemType>
class LinkStack
{
protected:
// 链栈的数据成员:
Node<ElemType> *top; // 栈顶指针
public:
// 链栈的函数成员:
LinkStack(); // 无参数的构造函数
virtual ~LinkStack(); // 析构函数
int GetLength() const; // 求栈长度
bool IsEmpty() const; // 判断栈是否为空
void Clear(); // 将栈清空
void Traverse(void (*Visit)(const ElemType &)) const ; // 遍历栈
Status Push(const ElemType e); // 入栈
Status Top(ElemType &e) const; // 返回栈顶元素
Status Pop(ElemType &e); // 出栈
LinkStack(const LinkStack<ElemType> &s); // 复制构造函数
LinkStack<ElemType> &operator =(const LinkStack<ElemType> &s); // 赋值语句重载
}; -
入栈出栈
template<class ElemType>
Status LinkStack<ElemType>::Push(const ElemType e)
// 操作结果：将元素e追加到栈顶,如成功则返加SUCCESS,否则如动态内存已耗尽
// 将返回OVER_FLOW
{
Node<ElemType> *p = new Node<ElemType>(e, top);
if (p == NULL) // 系统内存耗尽
return OVER_FLOW;
else { // 操作成功
top = p;
return SUCCESS;
}
}虽然说链式存储不用像顺序存储那样考虑空间的问题，但是系统在分配动态内存时还是存在动态内存耗尽的可能性，所以仍然要对动态开辟的空间进行判空操作。
template<class ElemType>
Status LinkStack<ElemType>::Pop(ElemType &e)
// 操作结果：如栈非空,删除栈顶元素,并用e返回栈顶元素,函数返回SUCCESS,否则
// 函数返回UNDER_FLOW
{
if (IsEmpty()) // 栈空
return UNDER_FLOW;
else { // 操作成功
Node<ElemType> *p = top; // 保留原栈顶
e = top->data; // 用e返回栈顶元素
top = top->next; // 修改栈顶
delete p; // 删除原栈顶结点
return SUCCESS;
}
}出栈首先要判空，然后top向后移动一位，再将之前的栈顶删除
-
栈的两种存储结构的比较
- 栈的顺序存储结构是一种静态的存储结构，必须确定存储空间的大小，太大会造成存储空间的浪费，太小会因栈满而产生溢出。
- 栈的链接存储结构是一种动态的存储结构，因为结点是动态分配的，所以不会出现溢出问题。
栈的应用——表达式求值
-
中缀表达式：
我们自然使用的数学表达式，按照规定的优先级（先乘除后加减）进行运算。
如：（32-26）*5 + 28 / 4 -
后缀表达式：
中缀表达式由于优先级的问题，虽然利于人的理解，但不便于使用计算机语言来实现，所以引入后缀表达式，将运算符放在运算对象之后。
如：32 26 -5 * 28 4 / +
特点：运算按照运算符出现顺序进行，没有括号。
由后缀表达式延伸的还有前缀表达式，即把每一个运算符放在运算对象之前。 -
利用栈实现中缀表达式的存储与计算
具体过程：从左向右扫描；遇到操作数，操作数入栈；遇到操作符，操作数按数量出栈进行计算，再将结果入栈；直至扫描完整个表达式，完成计算。
异常分析：操作数与操作符一定是对应准确的，如果表达式扫描完成，栈空或栈中仍有操作数，则后缀表达式错误。
后缀表达式计算代码：void PostfixExpressionCalculation ()
// 操作结果：后缀式的计算
{
LinkStack<double> opnd; // 操作数栈
char ch; // 临时字符
double operand, first, second; // 操作数
cout << "输入后缀表达式,以'#'号结束:";
ch = GetChar(); // 读入一个字符
while (ch != '#') { // 当前表达式还未运算结束, 继续运算
if (isdigit(ch) || ch == '.') { // ch为一个操作数的第1个字符
cin.putback(ch); // 将字符ch放回输入流
cin >> operand; // 读入操作数
opnd.Push(operand); // 操作数入栈
}
else if(!IsOperator(ch) || ch == '(' || ch ==')') {// ch既不是操作数,也不属于操作符
throw Error("表达式中有非法符号!"); // 抛出异常
}
else { // ch为操作符
if (opnd.Pop(second) == UNDER_FLOW) // 取第二操作数
throw Error("缺少操作数!"); // 取数失败，则抛出异常
if (opnd.Pop(first) == UNDER_FLOW) // 取第一操作数
throw Error("缺少操作数!"); // 取数失败，抛出异常
opnd.Push(Operate(first, ch, second)); // 运算结果入opnd栈
}
ch = GetChar(); // 读入新字符
}
if (opnd.Pop(operand) == UNDER_FLOW)
throw Error("缺少操作数!"); // 抛出异常
if (!opnd.IsEmpty())
throw Error("缺少操作符!"); // 抛出异常
cout << "表达式结果为：" << operand << endl; // 显示表达式的值
}; -
中缀表达式转后缀表达式
中缀表达式与后缀表达式的操作数顺序是一致的，只是中缀表达式多了优先级。
具体过程：- 操作符栈初始化，将结束符"#"入栈，读入中缀表达式的首字符ch。
- 分三种情况重复一下步骤，直至ch与栈顶操作符op同为“#”，停止循环。
1.ch为数字或.说明当前读入为操作数。先判断前一项是否为操作数或“）”，如果是上述情况则抛出异常；否则退回ch,输入整个操作数，并直接输出操作数，操作数计数器++。
2.ch不为1中的情况也不是操作符，非法字符，抛出异常。
3.ch不为上述情况，ch为操作符。1)若为“（”，但前项为操作数或“）”，则抛出异常；
2)若op优先级高于ch，则进行循环，先判断未被使用的操作数数量，如果数量小于2，则缺少操作数，发生异常。反之，将op出栈，再比较新栈顶操作符与输入操作符的优先级决定出栈与否。
3)若op与串不存在优先级，则说明有非法字符，抛出异常。
4)若op的优先级低于ch，则ch入栈，继续读下一个字。
5)若op的优先级等于ch,说明op与ch为“（”和“）”，后缀表达式不需要括号，op退栈，读下一个字。
代码实现：
void InfixInToPostfix()
// 操作结果：中缀式转换为后缀式
{
LinkStack<char> optr; // 操作符栈
char ch; // 临时字符
char priorChar; // 当前输入的前一个字符
char op = '#'; // 操作符栈的栈顶字符
double operand; // 操作数
int operandCount = 0; // 操作数计数器
optr.Push('#'); // 在操作符栈中加入一个'#'
priorChar = '#'; // 前一字符
cout << "输入中缀表达式,以'#'号结束:";
ch = GetChar(); // 读入一个字符
while (op != '#' || ch != '#') { // 当前表达式还未运算结束, 继续运算
if (isdigit(ch) || ch == '.') { // ch为一个操作数的第1个字符
if (priorChar == '0' || priorChar == ')')
throw Error("两个操作数之间缺少运算符!"); // 抛出异常
cin.putback(ch); // 将字符ch放回输入流
cin >> operand; // 读入操作数
cout << operand << " "; // 输出操作数
operandCount++; // 操作数数目加1
priorChar = '0'; // 前一字符是操作数
ch = GetChar(); // 读入下一个字符
}
else if(!IsOperator(ch)) { // 既不是操作数,也不是操作符
throw Error("表达式中有非法符号!"); // 抛出异常
}
else { // ch为操作符
if (ch == '(' && (priorChar == '0' || priorChar == ')'))
throw Error("'('前缺少操作符!"); // 抛出异常
while (OperPrior(op, ch) == 2) {
if (operandCount < 2)
throw Error("缺少操作数!");
operandCount--;
optr.Pop(op);
cout << op << " ";
if (optr.Top(op) == UNDER_FLOW)
throw Error("缺少操作符!"); // 抛出异常
}
switch (OperPrior(op, ch)) {
case -1 : throw Error("括号不匹配!");
case 0 : optr.Pop(op);
if (optr.Top(op) == UNDER_FLOW)
throw Error("缺少操作符!"); // 抛出异常
priorChar = ch; // 新的前一字符为(
ch = GetChar(); // 读入新字符
break;
case 1 : optr.Push(ch);
op = ch;
priorChar = ch; // 新的前一字符为)
ch = GetChar(); // 读入新字符
break;
}
}
}
if (operandCount != 1)
throw Error("缺少操作数!"); // 抛出异常
cout << endl;
}; -
中缀表达式简单转换后缀方式
给所有的操作步骤加上括号，将操作符对应移动到括号外，删除括号。
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 xljのblog！
wechat
alipay
