2 栈

[2] 栈 (stack)

定义

栈是特殊的线性表：只允许在一端进行插入或删- 除操作，其逻辑结构与普通线性表相同；
栈顶（Top）：允许进行插入和删除的一端（最上面的为栈顶元素）；
栈底（Bottom）：固定的，不允许进行插入和删除的一端（最下面的为栈底元素）；
空栈：不含任何元素的空表；
特点：后进先出（后进栈的元素先出栈）；
缺点：栈的大小不可变，解决方法——共享栈；

基本操作

创建&销毁

InitStack(&S) 初始化栈：构造一个空栈 S，分配内存空间；
DestroyStack(&S) 销毁栈：销毁并释放栈 S 所占用的内存空间；

增&删

Push(&S, x) 进栈：若栈 S 未满，则将 x 加入使其成为新栈顶；
Pop(&S, &x) 出栈：若栈 S 非空，则弹出（删除）栈顶元素，并用 x 返回；

查&其他

GetTop(S, &x) 读取栈顶元素
- 若栈 S 非空，则用 x-返回栈顶元素
- 栈的使用场景大多只访问栈顶元素
StackEmpty(S) 判空
- 断一个栈 S 是否为空，若 S 为空，则返回 true,否则返回 false；

[2-1-1] 静态栈

{0}

#define MaxSize 10         //定义栈中元素的最大个数

typedef struct{
    ElemType data[MaxSize];       //静态数组存放栈中元素
    int top;                      //栈顶元素
}SqStack;

void testStack(){
    SqStack S;       //声明一个顺序栈(分配空间)
                     //连续的存储空间大小为 MaxSize*sizeof(ElemType)
}

{0-1}

//初始化栈
void InitStack(SqStack &S){
    S.top = -1;                   //初始化栈顶指针
}

{0-1-1}

void testStack(){
    SqStack S;       //声明一个顺序栈(分配空间)
    InitStack(S);
    //...
}

{1} 入栈

//新元素进栈
bool Push(SqStack &S, ElemType x){
    if(S.top == MaxSize - 1)        //栈满
        return false;

    S.top = S.top + 1;    //指针先加1
    S.data[S.top] = x;    //新元素入栈

    /*
    S.data[++S.top] = x;
    */
    return true;
}

{2} 出栈

//出栈
bool Pop(SqStack &x, ElemType &x){
    if(S.top == -1)          //栈空
        return false;

    x = S.data[S.top];       //先出栈
    S.top = S.top - 1;       //栈顶指针减1
    // x = S.data[S.top--];
    return true;
    //只是逻辑上的删除，数据依然残留在内存里
}

{3} 读栈顶

//读栈顶元素
bool GetTop(SqStack S, ElemType &x){
    if(S.top == -1)
        return false;

    x = S.data[S.top];      //x记录栈顶元素
    return true;
}

{5-2}

//判栈空
bool StackEmpty(SqStack S){
    if(S.top == -1)      //栈空
        return true;
    else                 //栈不空
        return false;
}

top 指针指向下一个位置

也可以初始化时定义 S.top = 0 ：top 指针指向下一个可以插入元素的位置(栈顶元素的后一个位置)
- 进栈操作：栈不满时，栈顶指针先加 1，再送值到栈顶元素。S.data[S.top++] = x;
- 出栈操作：栈非空时，先取栈顶元素值，再将栈顶指针减 1。x = S.data[–S.top];
- 栈空条件：S.top==-1
- 栈满条件：S.top==MaxSize-1
- 栈长：S.top+1

[2-1-1-1] 共享栈

利用栈底位置相对不变的特性，可以让两个顺序栈共享一个一维数组空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸。

{0/0-1} 结构体定义以及初始化

存取数据的时间复杂度均为 O（1）

#define MaxSize 10         //定义栈中元素的最大个数

typedef struct{
    ElemType data[MaxSize];       //静态数组存放栈中元素
    int top0;                     //0号栈栈顶指针
    int top1;                     //1号栈栈顶指针
}ShStack;

//初始化栈
void InitSqStack(ShStack &S){
    S.top0 = -1;        //初始化栈顶指针
    S.top1 = MaxSize;
}

栈满条件：top1-top0=1

[2-2] 链栈

特性

定义：采用链式存储的栈称为链栈。
优点：链栈的优点是便于多个栈共享存储空间和提高其效率，且不存在栈满上溢的情况。
特点：
- 进栈和出栈都只能在栈顶一端进行(链头作为栈顶)
- 链表的头部作为栈顶，意味着
  - 在实现数据"入栈"操作时，需要将数据从链表的头部插入
  - 在实现数据"出栈"操作时，需要删除链表头部的首元节点
  - 因此，链栈实际上就是一个只能采用头插法插入或删除数据的链表

栈的链式存储结构可描述为：

typedef struct Linknode{
    ElemType data;              //数据域
    struct Linknode *next;      //指针域
}*LiStack;                      //栈类型的定义

基本操作

初始化
进栈
出栈
获取栈顶元素
判空、判满

[2-2-1-1] 有头节点的栈

{0}

#include<stdio.h>

struct Linknode{
    int data;             //数据域
    Linknode *next;       //指针域
}Linknode,*LiStack;

typedef Linknode *Node;   //结点结构体指针变量
typedef Node List;        //结点结构体头指针变量

{0-1}

//1. 初始化
void InitStack(LiStack &L){   //L为头指针
    L = new Linknode;
    L->next = NULL;
}

{1-3-1} 头插法进栈

//3. 进栈(：链栈基本上不会出现栈满的情况)
void pushStack(LiStack &L, int x){
    Linknode s;          //创建存储新元素的结点
    s = new Linknode;
    s->data = x;

    //头插法
    s->next = L->next;
    L->next = s;
}

{2-3-1} 头出栈

//4.出栈
bool popStack(LiStack &L, int &x){
    Linknode s;
    if(L->next == NULL) //栈空不能出栈
        return false;

    s = L->next;
    x = s->data;
    L->next = L->next->next;
    delete(s);

    return true;
}

{5-2}

//2.判栈空
bool isEmpty(LiStack &L){
    if(L->next == NULL){
        return true;
    }
    else
        return false;
}

[2-2-1-0] 无头节点的栈

{0}

#include<stdio.h>

struct Linknode{
    int data;             //数据域
    Linknode *next;       //指针域
}Linknode,*LiStack;

typedef Linknode *Node;   //结点结构体指针变量
typedef Node List;        //结点结构体头指针变量

{0-1}

//1.初始化
void initStack(LiStack &L){
    L=NULL;
}

{1-3-1}

//3.进栈
void pushStack(LiStack &L, int x){
    Linknode s;          //创建存储新元素的结点
    s = new Linknode;

    s->next = L;
    L = s;
}

{2-3-1}

//4.出栈
bool popStack(LiStack &L, int &x){
    Linknode s;
    if(L = NULL)     //栈空不出栈
        return false;

    s = L;
    x = s->data;
    L = L->next;
    delete(s);

    return true;
}

{5-2}

//2.判栈空
bool isEmpty(LiStack &L){
    if(L == NULL)
        return true;
    else
        teturn false;
}

AP>栈的应用--用栈实现括号匹配

((())) 最后出现的左括号最先被匹配 (栈的特性—LIFO);
遇到左括号就入栈;
遇到右括号，就“消耗”一个左括号 (出栈); 匹配失败情况：
扫描到右括号且栈空，则该右括号单身;
扫描完所有括号后，栈非空，则该左括号单身;
左右括号不匹配;

代码：

#define MaxSize 10

typedef struct{
    char data[MaxSize];
    int top;
} SqStack;

//初始化栈
InitStack(SqStack &S)

//判断栈是否为空
bool StackEmpty(SqStack &S)

//新元素入栈
bool Push(SqStack &S, char x)

//栈顶元素出栈，用x返回
bool Pop(SqStack &S, char &x)



bool bracketCheck(char str[], int length){
    SqStack S;      //声明
    InitStack(S);   //初始化栈

    for(int i=0; i<length; i++){
        if(str[i] == '(' || str[i] == '[' || str[i] == '{'){
            Push(S, str[i]);       //扫描到左括号，入栈
        }else{
            if(StackEmpty(S))      //扫描到右括号，且当前栈空
                return false;      //匹配失败

            char topElem;          //存储栈顶元素
            Pop(S, topElem);       //栈顶元素出栈

            if(str[i] == ')' && topElem != '(' )
                return false;

            if(str[i] == ']' && topElem != '[' )
                return false;

            if(str[i] == '}' && topElem != '{' )
                return false;
        }
    }

    StackEmpty(S);                //栈空说明匹配成功
}

【前/中/后缀表达式】

中缀表达式 (需要界限符)

运算符在两个操作数中间:

a + b
a + b - c
a + b - c * d
((15 ÷ (7-(1+1)))×3)-(2+(1+1))
A + B × (C - D) - E ÷ F

后缀表达式 (逆波兰表达式)

运算符在两个操作数后面:

a b +
a b + c - / a b c- +
a b + c d * -
15 7 1 1 + - ÷ 3 × 2 1 1 + + -
A B C D - × + E F ÷ - (机算结果)
A B C D - × E F ÷ - + (不选择)

中缀表达式转后缀表达式-手算 步骤 1：确定中缀表达式中各个运算符的运算顺序

步骤 2：选择下一个运算符，按照[左操作数右操作数运算符]的方式组合成一个新的操作数

步骤 3：如果还有运算符没被处理，继续步骤 2

“左优先”原则: 只要左边的运算符能先计算，就优先算左边的 (保证运算顺序唯一)；

中缀：A + B - C * D / E + F
后缀：A B + C D * E / - F +

重点：中缀表达式转后缀表达式-机算 初始化一个栈，用于保存暂时还不能确定运算顺序的运算符。从左到右处理各个元素，直到末尾。可能遇到三种情况:

遇到操作数: 直接加入后缀表达式。遇到界限符: 遇到 ‘(’ 直接入栈; 遇到 ‘)’ 则依次弹出栈内运算符并加入后缀表达式，直到弹出 ‘(’ 为止。注意: '(' 不加入后缀表达式。遇到运算符: 依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入后缀表达式，若碰到 ‘(’ 或栈空则停止。之后再把当前运算符入栈。按上述方法处理完所有字符后，将栈中剩余运算符依次弹出，并加入后缀表达式。

// 设置了2个栈，n用来存放结果，ysf用来存过程中的运算符
stack<char> n,ysf;
// 获取运算符优先级
int getr(char i) {
	if (i == '+' || i == '-')
		return 1;
	else if (i == '*' || i == '/')
		return 2;
	else
		return 0;
}
///////////////////////////
// 从头遍历字符串
for (;;)
{
	// 如果为运算符号
	if (getr(str[i]) > 0)
	{
		// 如果栈里还没有任意运算符
		if (ysf.empty())
		{
            // 将运算符压入栈
			ysf.push(str[i]);
		}
        // 如果运算符优先级大于栈顶的运算符
		else if (getr(ysf.top()) < getr(str[i]))
		{
            // 将运算符压入栈
			ysf.push(str[i]);
		}
        // 同级或次级运算符
		else if (getr(ysf.top()) >= getr(str[i]))
		{
            // 将栈顶的运算符弹出，并将该运算符放入栈
			n.push(ysf.top());
			ysf.pop();
			ysf.push(str[i]);
		}
	}
    // 左括号直接入栈
	else if (str[i] == '(')
	{
		ysf.push('(');
	}
    // 如果是右括号，弹出运算符栈的栈顶元素并输出，直到遇到左括号
	else if (str[i] == ')')
	{
		while (ysf.top() != '(')
		{
			n.push(ysf.top());
			ysf.pop();
		}
		ysf.pop();
	}
    // 如果是数字，直接放入
	else
	{
		n.push(str[i]);
	}
}

后缀表达式的计算—手算: 从左往右扫描，每遇到一个运算符，就让运算符前面最近的两个操作数执行对应的运算，合体为一个操作数；

注意： 两个操作数的左右顺序

重点：后缀表达式的计算—机算

用栈实现后缀表达式的计算（栈用来存放当前暂时不能确定运算次序的操作数）

步骤 1: 从左往后扫描下一个元素，直到处理完所有元素;

步骤 2: 若扫描到操作数，则压入栈，并回到步骤 1;否则执行步骤 3;

步骤 3: 若扫描到运算符，则弹出两个栈顶元素，执行相应的运算，运算结果压回栈顶，回到步骤 1;

注意: 先出栈的是“右操作数”

前缀表达式 (波兰表达式)

运算符在两个操作数前面:

+ a b
- + a b  c
- + a b * c d

中缀表达式转前缀表达式—手算 步骤 1：确定中缀表达式中各个运算符的运算顺序

步骤 2：选择下一个运算符，按照[运算符左操作数右操作数]的方式组合成一个新的操作数

步骤 3：如果还有运算符没被处理，就继续执行步骤 2

“右优先”原则: 只要右边的运算符能先计算，就优先算右边的;

中缀：A + B * (C - D) - E / F
前缀：+ A - * B - C D / E F

前缀表达式的计算—机算 用栈实现前缀表达式的计算

步骤 1: 从右往左扫描下一个元素，直到处理完所有元素；

步骤 2: 若扫描到操作数则压入栈，并回到步骤 1，否则执行步骤 3

步骤 3: 若扫描到运算符，则弹出两个栈顶元素，执行相应运算，运算结果压回栈顶，回到步骤 1；

注意: 先出栈的是“左操作数”

中缀表达式的计算(用栈实现)

两个算法的结合：中缀转后缀 + 后缀表达式的求值

初始化两个栈，操作数栈和运算符栈

若扫描到操作数，压人操作数栈

若扫描到运算符或界限符，则按照“中缀转后缀”相同的逻辑压入运算符栈 (期间也会弹出运算符，每当弹出一个运算符时，就需要再弹出两个操作数栈的栈项元素并执行相应运算，运算结果再压回操作数栈)

AP>栈在递归中的应用

函数调用的特点：最后被调用的函数最先执行结束(LIFO)

函数调用时，需要用一个栈存储：

调用返回地址
实参
局部变量

递归调用时，函数调用栈称为 “递归工作栈”:

每进入一层递归，就将递归调用所需信息压入栈顶
每退出一层递归，就从栈顶弹出相应信息

**缺点：**太多层递归可能回导致栈溢出

适合用“递归”算法解决：可以把原始问题转换为属性相同，但规模较小的问题

2 栈 ​

[2] 栈 (stack) ​

定义 ​

基本操作 ​

创建&销毁 ​

增&删 ​

查&其他 ​

[2-1-1] 静态栈 ​

{0} ​

{0-1} ​

{0-1-1} ​

{1} 入栈 ​

{2} 出栈 ​

{3} 读栈顶 ​

{5-2} ​

top 指针指向下一个位置 ​

[2-1-1-1] 共享栈 ​

{0/0-1} 结构体定义以及初始化 ​

[2-2] 链栈 ​

特性 ​

基本操作 ​

[2-2-1-1] 有头节点的栈 ​

{0} ​

{0-1} ​

{1-3-1} 头插法进栈 ​

{2-3-1} 头出栈 ​

{5-2} ​

[2-2-1-0] 无头节点的栈 ​

{0} ​

{0-1} ​

{1-3-1} ​

{2-3-1} ​

{5-2} ​

AP>栈的应用--用栈实现括号匹配 ​

【前/中/后缀表达式】 ​

中缀表达式 (需要界限符) ​

后缀表达式 (逆波兰表达式) ​

前缀表达式 (波兰表达式) ​

中缀表达式的计算(用栈实现) ​

AP>栈在递归中的应用 ​

2 栈

[2] 栈 (stack)

定义

基本操作

创建&销毁

增&删

查&其他

[2-1-1] 静态栈

{0}

{0-1}

{0-1-1}

{1} 入栈

{2} 出栈

{3} 读栈顶

{5-2}

top 指针指向下一个位置

[2-1-1-1] 共享栈

{0/0-1} 结构体定义以及初始化

[2-2] 链栈

特性

基本操作

[2-2-1-1] 有头节点的栈

{0}

{0-1}

{1-3-1} 头插法进栈

{2-3-1} 头出栈

{5-2}

[2-2-1-0] 无头节点的栈

{0}

{0-1}

{1-3-1}

{2-3-1}

{5-2}

AP>栈的应用--用栈实现括号匹配

【前/中/后缀表达式】

中缀表达式 (需要界限符)

后缀表达式 (逆波兰表达式)

前缀表达式 (波兰表达式)

中缀表达式的计算(用栈实现)

AP>栈在递归中的应用