阅读 231

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

数据结构和算法(1)线性表实现

数据结构和算法(2)单向循环链表的创建插入删除实现

数据结构和算法(3)双向链表与双向循环链表的实现

数据结构和算法(4)链表相关面试题

数据结构和算法(5)栈和队列的操作和实现

数据结构和算法(6)队列的操作和实现

@[TOC]

数据结构和算法(五)栈的操作和实现

  • 本篇博客的Demo下载:
  1. 顺序栈的基本操作实现
  2. 链式栈的基本操作实现

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种情况下,我们会使⽤用到递归来解决问题

  1. 定义是递归的
  2. 数据结构是递归的
  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. 任何时刻都不不能将⼀一个较⼤大的圆盘压在⼩小的圆盘之上.

hanoi塔问题

求解过程图如下:

hanoi塔问题求解过程图

3.2 表达式求值

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

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

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

后缀表达式的特点:

  1. 后缀表达式的操作数和中缀表达式的操作数先后次序完全相同(上面ABCDE),只是运算符的先后次序改变了(+-/*);
  2. 后缀表达式中没有括号,后缀表达式的运算次序就是其执行次序

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

从左到右读入后缀表达式的各项(运算符或运算数):

  1. 运算数:入栈
  2. 运算符:从堆栈中弹出适当数量的运算数,计算并结果入栈
  3. 最后,堆栈顶上的元素就是表达式的结果值

3.2.1 中缀表达式求值

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

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

过程:

  1. 运算数相对顺序不变
  2. 运算符号顺序发生改变
  3. 需要存储“等待中”的运算符号
  4. 要将当前运算符号与“等待中”的最后一个运算符号比较

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

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

  1. 运算数:直接输出
  2. 左括号:压入堆栈
  3. 右括号:将栈顶的运算符弹出并输出,直到遇到左括号(出栈,不输出)
  4. 运算符: (1) 若优先级大于栈顶运算符时,则把它压栈 (2) 若优先级小于等于栈顶运算符时,将栈顶运算符弹出并输出;再比较新的栈顶运算符,直到该运算符大于栈顶运算符优先级为止,然后将该运算符压栈
  5. 若各对象处理完毕,则把堆栈中存留的运算符一并输出

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

3.2.3 后缀表达式的实现过程

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

  • 运算符优先级别注意: 若把O1看成栈顶运算符,O2看成当前扫描读到的运算符。
  1. 当O1为“+”或“-”,O2为“*”或“/”时,O1的优先级 < O2的优先级(满足先乘除,后加减)
  2. 当O1为“+”“-”“*”或“/”,O2为“(”时,O1的优先级 < O2的优先级(满足先括号内,后括号外的规则)
  3. 当O1的运算符和O2的运算符同级别时,O1的优先级 > O2的优先级别(同级别先左后右规则)
  4. 由于后缀表达式无括号,当O1为“(”,O2为“)”时,用标记“=”使算法在此时去掉该对算法;
  5. 当O1为“#”时,O2为“#”时,用标记“=”使算法在此时结束处理
  6. 若表中的值为空,则不允许出现这种情况,一旦出现即为中缀算术表达式语法出错,如O1为“)”,而O2为“(”情况,即为中缀表达式语法错误!)。
  • 算法步骤:
  1. 设置一个堆栈,初始时将栈顶元素置为#
  2. 顺序读入中缀算术表达式,当读到的单词为操作数是就将其输出,并接着读下一个单词
  3. 单读到的单词为运算符时,令a为当前栈顶运算符的变量,b为当前扫描读到运算符的变量,把当前读到的运算符赋给b,然后比较变量a的优先级和b的优先级。若a的优先级高于b的优先级,则将a退栈并作为后缀表达式的一个单词输出,,然后比较新的栈顶元素运算符a的优先级与b的优先级。
  1. 若优先级 a<b,则将b的值进栈,然后接着读下一个单词

  2. 若优先级 a>b,则将a退栈并作为后缀表达式的一个单词输出,然后比较新的栈顶元素运算符a的优先级与b的优先级。

  3. 若优先级 a=b且a为“(”,b为“)”。则将a退栈,接着读下一个单词

  4. 若优先级 a=b且a为“#”,b为“#”。算法结束。

  • 代码实现:
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. 队列

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

  1. 插入和删除操作:只能在一端插入,而在另一端删除
  2. 数据插入:入队(AddQ)
  3. 数据删除:出队列(DeleteQ)
  4. 先进先出:FIFO

4.1 队列基本操作

队列基本操作

4.2 循环队列

循环队列基本结构

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

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

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

循环队列的操作

关注下面的标签,发现更多相似文章
评论