LingjieLi Gomputer Graphics/Algorithm/Linux/Server/Architecture

数据结构(陈越何钦铭) 线性结构2.2-堆栈(Stack)


堆栈是一种线性结构,是一种特殊的线性表,入栈和出战只能在栈顶操作,在递归,函数调用,表达式求值,深度优先搜索,回溯算法中有广泛的应用

1.引例:表达式求值

  • 中缀表达式:运算符位于两个运算数之间
  • 后缀表达式:运算符位于两个运算数之后
  • 前缀表达式:运算符位于两个运算树之前
1.1表达式求值:应用堆栈实现后缀表达式求值的基本过程
1.运算数:入栈
2.运算符:从堆栈中弹出只当数量的运算数,计算结果并入栈
3.栈顶上的元素就是表达式的结果 ##### **1.2中缀表达式求值:将中缀表达式转换为后缀表达式,然后求值** **中缀表达式如何转换为后缀表达式?**
从头至尾读取中缀表达式的每个对象,对不同对象按不同的情况处理
-1.运算数:直接输出
- 2.左括号:压入堆栈
- 3.右括号:将栈顶的运算符弹出并输出,知道遇到左括号(弹出,不输出)
- 4.运算符:
	- 若优先级大于栈顶运算符:入栈
	- 若运算符小于等于栈顶运算符,栈顶运算符弹出并输出;在比较新的栈顶运算符,直到该运算符大于栈顶运算符优先级,然后将该运算符入栈(在堆栈中的左括号优先级最小)
- 5.若各对象处理完毕,则把堆栈中存留的运算符一并输出

2堆栈的操作:堆栈的抽象数据结构

3堆栈的存储

3.1顺序存储

通常由一个一维数组和一个指示栈顶元素位置的变量组成

#defind MaxSize <存储数据元素的最大个数>
typedef struct SNode *Stack
struct SNode
{
	ElementTypr Data[MaxSize];
    int Top;
};
3.2链式存储

实际上是一个单链表,插入和删除操作只在栈顶进行,栈顶指针Top在链表的头部 生成一个头结点,s->next=NULL,头结点的数据部分是空的,这样的好处在于插入节点时,不需要判断当前栈是否为空

typedef struct SNode *Stack
struct SNode
{
	ElementType Data;
    SNode *Next; 
};

4堆栈应用

4.1使用一个数组存储两个堆栈

使两个堆栈分别从数组的两头向中间生长,当两个堆栈的栈顶指针相遇时,代表堆栈满


Comments

Content