数据结构-堆栈

不念不忘少年蓝@ 2023-10-04 13:36 54阅读 0赞

数据结构-堆栈

堆栈（Stack）是一组相同数据类型的组合，具有“后进先出”的特性，所有的操作均在顶端进行。

  1. 堆栈的简介

    “后进先出”可以看做是往米缸里放米，先放进去的后吃，后放进去的在顶端先吃。堆栈是一种抽象数据结构（ADT，Abstract Data Type），具有下列特性：

    • 只能从堆栈的顶端存取数据
    • 数据的存取符合后进先出的原则

    堆栈的基本运算有5种：


























    create 创建一个空堆栈
    push 把数据存压入堆栈顶端，并返回新堆栈
    pop 从堆栈顶端弹出数据，并返回新堆栈
    isEmpty 判断堆栈是否为空堆栈，若是则返回true，否则返回false
    full 判断堆栈是否已满，若是则返回true，否则返回false

    堆栈的形式可以采用数组结构和链表结构两种方式表示

    • 使用列表实现

      以列表实现的好处是算法的设计简单，但是如果堆栈本身的大小是变动的话，而列表大小只能事先规划和声明好，那么列表规划太大会浪费空间，规划太小又不够用，就很烦

      • 判断堆栈是否为空

        1. def isEmpty():
        2.         if top == -1:
        3.                 return True
        4.         else:
        5.                 return False

      • 将指定的数据存入堆栈

        1. def push(data):
        2.         global top        #全局top
        3.         global MAXSTACK        #设置最大容量
        4.         global stack
        5.         if top >= MAXSTACK - 1：
        6.                 print("堆栈已满")
        7.         else:
        8.                 top += 1
        9.                 stack[top] = data

      • 从堆栈中取出数据

        1. def pop():
        2.         global top
        3.         global stack
        4.         if isEmpty():
        5.                 print("堆栈已空")
        6.         else:
        7.                 print("弹出的元素为：%d" % stack[top])
        8.                 top = top -1

      例子：设计一个数组方针扑克牌洗牌以及发牌的过程，使用随机数来生成扑克牌放入堆栈，放满52张之后使用堆栈功能给4个玩家发牌

      1. import random
      3. global top
      5. top = -1
      6. k = 0
      8. """
      9. stack:堆栈
      10. MAX:堆栈的最大容量
      11. val:push进去的值
      12. """
      13. def push(stack,MAX,val):
      14.     global top
      15.     if top >= MAX - 1:
      16.         print("[堆栈已满]")
      17.     else:
      18.         top = top + 1
      19.         stack[top] = val    #将val放到stack中
      21. """
      22. stack:堆栈
      23. """
      24. def pop(stack):
      25.     global top
      26.     if top < 0:
      27.         print("[堆栈已空]")
      28.     else:
      29.         top = top - 1
      30.         return stack[top]
      32. """
      33. old:数组，事先声明的数组
      34. 洗牌
      35. """
      36. def shuffle(old):
      37.     result = []
      38.     while old:
      39.         p = random.randrange(0,len(old))    #随机在old数组长度范围抽取一个数
      40.         result.append(old[p])   #将该数组中对应的数加到result中
      41.         old.pop(p)  #将该数在old数组中删除
      42.     return result
      44. card = [None] * 52   #声明52张牌
      45. card_new = [None] * 52  #声明相同长度的数组用于存放洗牌
      46. stack = [0] * 52    #声明堆栈
      47. for i in range(52):
      48.     card[i] = i + 1 #对card数组元素赋值，赋值为1-52
      50. print("开始洗牌...")
      52. card_new = shuffle(card)    #洗牌，并将结果数组存到card_new中
      54. i = 0
      55. while i != 52:
      56.     push(stack,52,card_new[i])
      57.     i = i + 1
      59. print('开始发牌')
      60. print("[显示各家的牌] 东家\t\t 北家\t\t 西家\t\t 南家")
      61. print('------------------------------------')
      63. while top >= 0:
      64.     style = (stack[top]) % 4    #计算花色
      65.     if style == 0:  #梅花
      66.         ascVal = 'club'
      67.     if style == 1:  #方块
      68.         ascVal = 'diamo'
      69.     if style == 2:  #红心
      70.         ascVal = 'heart'
      71.     elif style == 3:    #黑桃
      72.         ascVal = 'spade'
      74.     print('[%s%3d]\t\t\t' % (ascVal,stack[top] % 13 + 1),end='')
      75.     if top % 4 == 0:
      76.         print()
      77.     top = top - 1

    • 使用链表实现堆栈

      用链表实现堆栈的优点是随时可以动态改变链表长度，能有效利用内存资源，缺点是算法较为复杂

      使用链表表示堆栈就需要指定一个属性next，链表方向为从上到下


























      top 顶端数据
      ↓ next指向下一个
      new_data 下一个数据
      ↓ next指向下一个
      new_data 下一个数据 
      1. class Node:        #堆栈链表节点的声明
      2.         def __init__(self):
      3.                 self.data = 0        #堆栈数据的声明
      4.                 self.next = None        #堆栈中用来指向下一个节点
      5. top = None

      • 判断是否为空堆栈

        1. def isEmpty():
        2.         global top
        3.         if (top == None):
        4.                 return 1
        5.         else:
        6.                 return 0

      • 将指定的数据压入堆栈

        1. def push(data):
        2.         global top
        3.         new_add_node = Node()
        4.         new_add_node.data = data        #将传入的值指定为节点的内容
        5.         new_add_node.next = top            #将新节点指向堆栈的顶端
        6.         top = new_add_node            #将新节点指定为堆栈

      • 从堆栈弹出数据

        1. def pop():
        2.         global top
        3.         if isEmpty():
        4.                 print('这个堆栈是空的')
        5.                 return -1
        6.         else:
        7.                 ptr = top        #指向堆栈的顶端
        8.                 top = top.next        #将堆栈顶端的指针指向下一个节点
        9.                 temp = ptr.data            #弹出堆栈的数据
        10.                 return temp
  2. 堆栈的应用

    堆栈在计算机领域的应用相当广泛，主要特性是限制了数据插入与删除的位置和方法，属于有序线性表的应用，堆栈的各种应用列举如下：

    • 二叉树和森林的遍历，例如中序遍历（Inorder）、前序遍历（Preorder）等。
    • 计算机中央处理单元（CPU）的中断处理（Interrupt Handling）
    • 图形的深度优先（DFS）查找法（或陈伟深度优先搜索法）
    • 当从递归返回（Return）时，按序从堆栈顶端取出相关值，回到原来执行递归前的状态，再往下继续执行
    • 算数表达式的转换和求值，例如中序法转换成后序法

    堆栈的应用有很多，以上只是列举了一部分而已

    • 递归算法

      递归（Recursion）是一种很特殊的算法，其定义是：加入一个函数或子程序是由自身所定义或调用的，就称为递归。递归至少需要两个条件：

      • 可以反复执行的递归过程
      • 一个跳出执行过程的出口

      比如数学上的阶乘函数，可以看做是典型的递归范例，一般以！来代表阶乘。例如4的阶乘就是4！

      4！= 4 x 3 x 2 x 1

      4! = (4 * 3!)——>(4 * 3 * 2!) ———>(4 * 3 * 2 * 1)

      函数算法表示是

      1. def factorial(i):        if i == 0:                return 1        else:                ans = i * factorial(i - 1)        #反复执行递归过程

      使用for循环设计一个计算0！~ n!的递归程序

      1. sum = 1n = int(input('请输入n=''))for i in range (0,n+1):        for j in range(i ,0,-1):                sum *= j                print('%d != %3d' % (i,sum))        sum = 1

      递归算法又可以分为直接递归和间接递归：

      • 直接递归（Direct Recursion）：在递归函数中允许直接调用该函数自身

        1. def Fun(...):        .......if ....:        Fun(...)        ......

      • 简介递归（Indirect Recursion）：在递归函数中调用其他递归函数，再从其他递归函数调用回原来的递归函数

        1. def Fun1(...):    ......if ......:        Fun2(...)        .......        def Fun2(...):        ......if ......:        Fun1(...)        ......

      斐波拉契数列





















      0 n=0
      Fn 1 n=1
      Fn-1 + Fn-2 n=2,3,4,5,…(n为正整数)

      简单来说，这就是一个数列的第零项是0，第一项是1，这个数列其他后续项的值是前两项的数值之和。

      1. def fib(n):                if n == 0:                return 0        elif n == 1 or n == 2:                return 1        else:            #否则返回fib(n-1) + fib(n-2)                return (fib(n-1) + fib(n-2))

      例子：设计一个计算第n项斐波拉契数列的递归程序：

      1. def fib(n):        if n == 0:                return 0        elif n == 1 or n == 2:                return 1        else:                return (fib(n - 1) + fib(n - 2))                n = int ( input ("请输入n="))for i in range(n + 1):        print('fib(%d) = %d' % (i,fib(i)))

      汉诺塔问题

      汉诺塔问题也是很典型的递归方式和堆栈来解决，因为它满足递归的两大特性：①有反复执行的过程②有停止的出口

      汉诺塔的游戏规则就是把一定数量的盘子每次移动一个，全部从第一个桩移动到第三个桩上，在移动的过程中要保证大盘子在下面

      借助递归的思想，加入有n个盘子，我们可以将n个盘子看做两个组成结构，就是n-1个盘子和一个盘子，每次都是将n-1个盘子移动到第二个桩上，将一个盘子（最大的）移动到第三个桩上，然后将第二个桩变换为第一个桩，继续将剩下的n-1个盘子分为两个结构进行移动，直到不能分为止

      移动步骤：

      • 将n-1个盘子从木桩1移动到木桩2
      • 将第n个最大的盘子从木桩1移动到木桩3

      • 将n-1个盘子从木桩2移动到木桩3

        • 就是把木桩2当做是木桩1逐次分解进行迭代

      算法实现：

      1. """
      2. n:需要移动的盘子数量
      3. p1,p2,p3:三根木桩
      4. """
      5. def hanoi(n,p1,p2,p3):
      6.     if n == 1:
      7.         print("盘子从%d移动到了%d"%(p1,p3))
      8.     else:
      9.         hanoi(n-1,p1,p3,p2)
      10.         print("盘子从%d移动到%d"%(p1,p3))
      11.         hanoi(n-1,p2,p1,p3)
      13. j = int(input("请输入要移动盘子的数量："))
      14. hanoi(j,1,2,3)

在这里插入图片描述

  1. 除此之外，关于堆栈的有趣应用还有我们常见的迷宫问题等，都可以通过堆栈实现

  1. 算数表达式的表示法

    根据运算符在表达式中的位置，可以分为3中表示法：

    • 中序法(Infix)：运算符在两个操作数之间，；例如A+B、(A+B)*(C+D)等都是中序表示法
    • 前序法(Prefix):运算符在操作数的前面，例如+AB、*+AB+CD等都是前序表示法
    • 后序法(Postfix):运算符在操作数的后面，例如AB+、AB+CD+等都是后序表示法

    中序法转为前序法和后序法

    中序法转换为前序法或者后序法，可以使用两种方式，即括号转换法和堆栈法。括号转换法适合人工手动操作，堆栈法则普遍用于计算机的操作系统或系统程序中

    • 括号转化法：

      括号转换法先用括号把中序法表达式的运算符优先级分出来，再进行运算符的移动，最后把括号拿掉就可以完成中序转后序或中序转前序

      6+29/3+42-8为例

      • 中序->前序（Infix->Prefix）

        • 先把表达式按照运算符优先级以括号括起来
        • 针对运算符，用括号内的运算符取代所有的左括号，以最近者为优先级

        • 将所有右括号去掉，即可得到前序法表达的结果

          1. (((6+((2*9)/3))+(4*2))-8)

          前序式：-++ 6 / * 293 * 428

      • 中序->后序（Infix->Postfix）

        • 先把表达式按照运算符优先级以括号括起来
        • 针对运算符，用用括号内的运算符取代所有的左括号，以最近者为优先级

        • 将所有左括号去掉，即可得到后序法表达的结果

          1. (((6+((2*9)/3))+(4*2))-8)

          后序法：629 * 3 /+ 42 *+ 8 -

    • 堆栈法

      这个方法必须使用运算符堆栈，也就是使用堆栈来协助进行运算符优先级的转换

      • 中序->前序（Infix->Prefix）

        • 从右向左读进中序法表达式的每个字符（token）
        • 如果读进的字符为操作数，就直接输出到前序法表达式中
        • 如果遇到“（”，就弹出堆栈内的运算符，直到弹出一个“）”，两者互相抵消
        • “）”的优先级在堆栈内比任何运算符都小，任何运算符的优先级都搞过它，不过在堆栈外却是优先级最高者
        • 当运算符准备进入堆栈内时，必须和堆栈顶端的运算符比较，如果外面的运算符优先级高于或者等于堆栈顶端的运算符，就压入堆栈，如果优先级低于堆栈顶端的运算符，就把堆栈顶端的运算符弹出，直到堆栈顶端的运算符优先级低于外面的运算符或者堆栈为空时，再把外面这个运算符压入堆栈
        • 中序法表达式读完之后，如果运算符堆栈不是空的，就将其内部的运算符逐一弹出，输出到前序法表达式中即可

      • 中序->后序（Infix->Postfix）

        • 从左到右读进中序法表达式的每个字符（token）
        • 如果读进的字符为操作数，就直接输出到前序法表达式中
        • 如果遇到“）”，就弹出堆栈内的运算符，直到弹出一个“（”，两者互相抵消
        • “（）”的优先级在堆栈内比任何运算符都小，任何运算符的优先级都搞过它，不过在堆栈外却是优先级最高者
        • 当运算符准备进入堆栈内时，必须和堆栈顶端的运算符比较，如果外面的运算符优先级高于或者等于堆栈顶端的运算符，就压入堆栈，如果优先级低于堆栈顶端的运算符，就把堆栈顶端的运算符弹出，直到堆栈顶端的运算符优先级低于外面的运算符或者堆栈为空时，再把外面这个运算符压入堆栈
        • 中序法表达式读完之后，如果运算符堆栈不是空的，就将其内部的运算符逐一弹出，输出到前序法表达式中即可

发表评论

表情：
评论列表 （有 0 条评论，54人围观）

还没有评论，来说两句吧...

相关阅读

    相关 数据结构之堆栈（四）

    栈 什么是栈？ > 栈在实际的例子中有点像手枪的弹夹。你每次添加子弹的时候都是会把你前面添加的子弹给压到最下面。而打出来的子弹都是你最新的。所以就

    末蓝、末蓝、/ 0 赞/ 274 阅读

    相关 数据结构之堆栈与队列

    堆栈与队列是两种重要的基础数据结构，一个是先入后出，一个是先入先出，有着广泛的应用，本文分别使用数组与链表实现堆栈与队列 顺序存储方式实现堆栈 define

    清疚清疚/ 0 赞/ 317 阅读

    相关 数据结构——堆栈和队列

    堆栈和队列都是特殊的线性表，线性表、堆栈和队列三者的数据元素以及数据元素之间的逻辑关系完全相同。 差别：线性表的插入和删除操作不受任何限制，而堆栈只能在栈顶插入和删除，队列

    女爷i女爷i/ 0 赞/ 360 阅读

    相关 数据结构--堆栈(Java版)

    一、栈的介绍 > 栈（stack）又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入

    左手的ㄟ右手左手的ㄟ右手/ 0 赞/ 313 阅读