@[TOC]

数据结构和算法（五）栈的操作和实现

本篇博客的Demo下载：

1. 栈的简介

栈是一种后进先出的结构，有一个栈底指针，一个栈顶指针，入栈只能从栈顶入栈，出栈也只能从栈顶出栈。它的结构示意图如下：

我们可以对比一下队列：队列是一种先进先出的数据结构，只能从队尾入队，从对头出队，队列的结构图如下图：

2. 顺序栈的实现

2.1 顺序栈的基本操作

2.1.1 顺序栈结构

//顺序栈结构
typedef struct KSqueueStack{
    KStackElementType data[MAXSIZE];
    int top; //用于栈顶指针
}SqStack;

2.1.2 顺序栈建栈

//1. 构建一个空栈S
KStatus initStack(SqStack *S) {
    S->top = -1;
    return OK;
}

2.1.3 顺序栈置空

//2. 将栈置空
KStatus clearStack(SqStack *S) {
    S->top = -1;
    return OK;
}```
#### 2.1.4 顺序栈判空
```swift
//3. 判断顺序栈是否为空
KStatus isEmpty(SqStack S) {
    return  S.top == -1 ;
}

2.1.5 顺序栈获取长度

//4. 获取栈长度
int getLength(SqStack S) {
    return S.top + 1;
}

2.1.6 顺序栈获取栈顶元素

//5. 获取栈顶
KStatus getTop(SqStack S, KStackElementType *e) {
    //栈空，则返回错误
    if (S.top == -1) return ERROR;
    *e = S.data[S.top];
    return OK;
}

2.1.7 顺序栈压栈

入栈前如下图所示：

入栈后如下图所示：

入栈代码实现：

//6. 压栈
KStatus push(SqStack *S, KStackElementType e) {
    //判断是否 栈满
    if (S->top == MAXSIZE -1) return ERROR;
    //1. 栈顶指针+1;
    //2. 将新插入的元素赋值给栈顶空间
    //S->top ++;
    //S->data[S->top] = e;
    S->data[++(S->top)] = e;
    return OK;
}

2.1.8 顺序栈出栈

//7. 出栈
KStatus pop(SqStack *S, KStackElementType *e) {
    //判断是否栈空
    if(S->top == -1) return ERROR;
    //1. 将要删除的栈顶元素赋值给e
    //2. 栈顶指针--;
    //*e = S->data[S->top];
    //S->top--;
    *e = S->data[S->top--];
    return OK;
}

2.1.9 顺序栈遍历

//8. 栈遍历
KStatus traverse(SqStack S) {
    int i = 0;
    printf("栈所有元素：");
    while (i < S.top) {
        printf("%d ",S.data[i++]);
    }
    printf("\n");
    return OK;
}

2.1.10 顺序栈单元测试

//9. 测试
void test() {
    SqStack S;
    int e;
    
    if (initStack(&S) == OK) {
        for (int j = 1 ; j < 10; j++) {
            push(&S, j);
        }
    }
    
    printf("顺序栈中元素为:\n");
    traverse(S);
    
    pop(&S, &e);
    printf("弹出栈顶元素为: %d\n",e);
    traverse(S);
    printf("是否为空栈:%d\n",isEmpty(S));
    getTop(S, &e);
    printf("栈顶元素:%d \n栈长度:%d\n",e,getLength(S));
    clearStack(&S);
    printf("是否已经清空栈 %d, 栈长度为:%d\n",isEmpty(S),getLength(S));
}

输出结果

Hello, World!
顺序栈中元素为:
栈所有元素：1 2 3 4 5 6 7 8 
弹出栈顶元素为: 9
栈所有元素：1 2 3 4 5 6 7 
是否为空栈:0
栈顶元素:8 
栈长度:8
是否已经清空栈 1, 栈长度为:0
Program ended with exit code: 0

3. 链式栈的实现

链式栈是有链表来实现的一种栈结构，它的结构示意图如下图：

3.1 链式栈的基本操作

3.1.1 链式栈结构


//链栈结点
typedef struct KStackNode {
    KStackElementType data;    //结点数据
    struct KStackNode *next;   //指向下一个结点的指针
}StackNode, *LinkStackPtr;

//链栈结构
typedef struct KLinkStack {
    LinkStackPtr top;   //栈顶结点
    int count;          //栈大小
}LinkStack;

3.1.2 链式栈建栈

//1. 构造一个空栈S
KStatus initStack(LinkStack *S) {
    S->top = NULL;
    S->count = 0;
    return OK;
}

3.1.3 链式栈置空

//2. 链栈置空
KStatus clearStack(LinkStack *S) {
    LinkStackPtr p,q;
    //p指向栈顶结点
    p = S->top;
    while (p) {
        //保存要删除的结点p
        q = p;
        //然p指向它的下一个结点
        p = p->next;
        //删除 p结点
        free(q);
    }
    return OK;
}

3.1.4 链式栈判空

//3. 判断栈是否为空
KStatus isEmpty(LinkStack S) {
    return S.count == 0;
}

3.1.5 链式栈获取长度

//4. 获取栈长度
int getLength(LinkStack S) {
    return S.count;
}

3.1.6 链式栈获取栈顶元素

//5. 获取栈顶元素
KStatus getTop(LinkStack S, KStackElementType *e) {
    //判断是否栈空
    if (S.top == NULL) return ERROR;
    *e = S.top->data;
    return OK;
}

3.1.7 链式栈压栈

链式栈结构，入栈示意图如下：

//6. 压栈
KStatus push(LinkStack *S, KStackElementType e) {
    //1. 创建一个新结点，
    LinkStackPtr newNode = (LinkStackPtr)malloc(sizeof(StackNode));
    //2. 赋值给新结点
    newNode->data = e;
    
    //3. 插入新结点到栈顶结点后面
    //3.1 把当前的栈顶元素的结点指针指向直接后继结点
    newNode->next = S->top;
    //3.2 将新结点赋值给栈顶指针
    S->top = newNode;
    //栈大小+1
    S->count++;
    
    return OK;
}

3.1.8 链式栈出栈

链式栈结构，出栈示意图如下图：

//7. 出栈
KStatus pop(LinkStack *S, KStackElementType *e) {
    LinkStackPtr p;
    if (isEmpty(*S)) return ERROR;
    //1. 将栈顶元素赋值给*e
    *e = S->top->data;
    //2. 将栈顶结点赋值给p
    p = S->top;
    //3. 使得栈顶指针下移一位, 指向后一结点
    S->top = S->top->next;
    //4. 释放p结点
    free(p);
    //栈大小减1
    S->count--;
    
    return OK;
}

3.1.9 链式栈遍历

//8. 遍历栈
KStatus traverse(LinkStack S) {
    LinkStackPtr p = S.top;
    printf("遍历栈元素：");
    while (p) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
    return OK;
}

3.1.10 链式栈单元测试

//9. 单元测试
void test() {
    int j;
    LinkStack s;
    int e;
    if(initStack(&s)==OK)
        for(j=1;j<=10;j++)
            push(&s,j);
    printf("栈中元素依次为：");
    traverse(s);
    pop(&s,&e);
    printf("弹出的栈顶元素 e=%d\n",e);
    traverse(s);
    printf("栈空否：%d(1:空 0:否)\n",isEmpty(s));
    getTop(s,&e);
    printf("栈顶元素 e=%d 栈的长度为%d\n",e,getLength(s));
    clearStack(&s);
    printf("清空栈后，栈空否：%d(1:空 0:否)\n",isEmpty(s));
}

输出结果

Hello, World!
栈中元素依次为：遍历栈元素：10 9 8 7 6 5 4 3 2 1 
弹出的栈顶元素 e=10
遍历栈元素：9 8 7 6 5 4 3 2 1 
栈空否：0(1:空 0:否)
栈顶元素 e=9 栈的长度为9
清空栈后，栈空否：0(1:空 0:否)
Program ended with exit code: 0

3. 栈的应用

3.1 递归

3.1.1 函数调用及递归实现

下⾯面3种情况下,我们会使⽤用到递归来解决问题

定义是递归的

数据结构是递归的

问题的解法是递归的

3.1.2 深度优先搜索

3.1.3 回溯算法

3.1.4 Hanoi塔问题

问题描述: 假如有3个分别命名为A,B,C的塔座,在塔座A上插有n个直接⼤大⼩小各不不相同的,从⼩小到⼤大的编号为1,2,3...n的圆盘. 现在要求将塔座A上的n个圆盘移动到塔座C上. 并仍然按照同样的顺序叠排. 圆盘移动时必须按照以下的规则:1. 每次只能移动⼀一个圆盘;2. 圆盘可以插在A,B,C的任⼀一塔座上;3. 任何时刻都不不能将⼀一个较⼤大的圆盘压在⼩小的圆盘之上.

求解过程图如下：

3.2 表达式求值

在编译系统中，算术表达式可以分为三类：算术表达式，关系表达式，逻辑表达式。

任何一个算术表达式都是由：操作数，运算符和分界符组成。我们把操作数，运算符和分界符（分界符标志了一个算术表达式的结束）称为一个算术表达式的单词。

中缀表达式：算术表达式中的运算符总是出现在两个操作数之间（除单目运算符外）例如：A+（B-C/D）*E
后缀表达式：表达式中的运算符出现在操作数之后。编译系统对于中缀表达式处理方法是将其变成后缀表达式，例如：ABCD/-E*+

后缀表达式的特点：

后缀表达式的操作数和中缀表达式的操作数先后次序完全相同（上面ABCDE），只是运算符的先后次序改变了（+-/*）；

后缀表达式中没有括号，后缀表达式的运算次序就是其执行次序

应用堆栈实现后缀表达式求值的基本过程：

从左到右读入后缀表达式的各项（运算符或运算数）：

运算数：入栈

运算符：从堆栈中弹出适当数量的运算数，计算并结果入栈

最后，堆栈顶上的元素就是表达式的结果值

3.2.1 中缀表达式求值

基本策略：将中缀表达式转换为后缀表达式，然后求值。

如何将中缀表达式转换为后缀表达式？例如：2+9/3-5 -> 2 9 3 / +5 -

过程：

运算数相对顺序不变

运算符号顺序发生改变

需要存储“等待中”的运算符号

要将当前运算符号与“等待中”的最后一个运算符号比较

3.2.2 中缀表达式如何转换为后缀表达式

从头到尾读取中缀表达式的每个对象，对不同对象按不同的情况处理。

运算数：直接输出

左括号：压入堆栈

右括号：将栈顶的运算符弹出并输出，直到遇到左括号（出栈，不输出）

运算符: (1) 若优先级大于栈顶运算符时，则把它压栈 (2) 若优先级小于等于栈顶运算符时，将栈顶运算符弹出并输出；再比较新的栈顶运算符，直到该运算符大于栈顶运算符优先级为止，然后将该运算符压栈

若各对象处理完毕，则把堆栈中存留的运算符一并输出

3.2.3 后缀表达式的实现过程

编译系统设置一个存放运算符的堆栈，初始时栈顶置一个分界符“#”。编译系统从左到右依次扫描中缀表达式，每读到一个操作数就把它作为后缀表达式的一部分输出，每读到一个运算符（分界符也看作运算符）就将其优先级与栈顶运算符优先级运算符进行比较，以决定是就所读到的运算符进栈，还是将栈顶运算符作为最为后缀算术表达式的一部分输出。

运算符优先级别注意：若把O1看成栈顶运算符，O2看成当前扫描读到的运算符。

当O1为“+”或“-”，O2为“*”或“/”时，O1的优先级 < O2的优先级(满足先乘除，后加减)

当O1为“+”“-”“*”或“/”，O2为“（”时，O1的优先级 < O2的优先级（满足先括号内，后括号外的规则）

当O1的运算符和O2的运算符同级别时，O1的优先级 > O2的优先级别（同级别先左后右规则）

由于后缀表达式无括号，当O1为“（”，O2为“）”时，用标记“=”使算法在此时去掉该对算法；

当O1为“#”时，O2为“#”时，用标记“=”使算法在此时结束处理

若表中的值为空，则不允许出现这种情况，一旦出现即为中缀算术表达式语法出错，如O1为“）”，而O2为“（”情况，即为中缀表达式语法错误！)。

算法步骤：

设置一个堆栈，初始时将栈顶元素置为#

顺序读入中缀算术表达式，当读到的单词为操作数是就将其输出，并接着读下一个单词

单读到的单词为运算符时，令a为当前栈顶运算符的变量，b为当前扫描读到运算符的变量，把当前读到的运算符赋给b,然后比较变量a的优先级和b的优先级。若a的优先级高于ｂ的优先级，则将ａ退栈并作为后缀表达式的一个单词输出，，然后比较新的栈顶元素运算符ａ的优先级与ｂ的优先级。

若优先级ａ＜ｂ，则将ｂ的值进栈，然后接着读下一个单词

若优先级ａ＞ｂ，则将ａ退栈并作为后缀表达式的一个单词输出，然后比较新的栈顶元素运算符ａ的优先级与ｂ的优先级。

若优先级ａ＝ｂ且ａ为“（”，ｂ为“）”。则将ａ退栈，接着读下一个单词

若优先级ａ＝ｂ且ａ为“＃”，ｂ为“＃”。算法结束。

代码实现：

int PostExp(char str[])  //借助堆栈计算后缀表达式str的值
{
    KStackElementType x,x1,x2;
    int i;
    KNode *head;    //定义头指针变量head
    initStack(&head);   //初始化链式堆栈head
    for(i-0;str[i]!=#;i++)   //循环直到输入为#
    {
        if(isdigit(str[i]))   //当str[i]为操作数时
        {
            x=(int)(str[i]-48);  //转换成int类型数据存于变量x中
            push(head,x);   //x入栈
        }
        else                     //当str[i]为运算符时
        {  
            pop(head,&x2);  //退栈的操作数，存于变量x2中
            pop(head,&x1);  //退栈的被操作数，存于变量x1中
            switch(str[i])      //执行str[i]所表示的运算
            {
            case '+':
                {
                    x1+=x2; break;
                }
            case '-':
                {
                    x1-=x2; break;
                }
            case '*':
                {
                    x1*=x2; break;
                }
            case '/':
                {
                    if(x2==0.0)
                    {
                        printf("除数为0错误！\n");
                        exit(0);
                    }
                    else
                    {
                        x1/=x2;
                        break;
                    }
                }
            }
            push(head,x1);    //运算结果入栈
        }
    }
    pop(head,&x);     //得到计算结果存于x
    return x;             //返回计算结果
}

4. 队列

队列：具有一定操作约束的线性表有以下特点：

插入和删除操作：只能在一端插入，而在另一端删除

数据插入：入队（AddQ）

数据删除：出队列（DeleteQ）

先进先出：FIFO

4.1 队列基本操作

4.2 循环队列

循环队列中头尾指针和元素之间的关系

数据结构和算法（五）栈和队列的操作和实现