欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数据结构与算法-Python实现(二)栈

程序员文章站 2022-03-29 08:20:12
...

数据结构与算法-Python实现(二)栈

一、线性结构(Linear Structure)

概念:线性结构是一种有序数据项的集合,除了第一个元素没有前驱,最后一个没有后继新都数据项加入到数据集中时,只会加入到原有某个数据项之前或者之后,具有这种性质到数据集,就称为线性结构;常见的线性结构有:线性表,栈,队列,双队列,数组等,不同线性结构的关键区别在于数据项增减的方式。

二、栈 (Stack)

  • 什么是栈?栈是一种有次序的数据项集合,在栈中,数据项的加入和移除都仅发生在同一端,这一端叫 “顶 top”,另一端叫 “底 base”,距离栈底越近都数据项,留在栈中都时间越长,既:新加入都数据会最先被移除,这种次序通常称为:后进先出(Last in First out)
  • 使用 Python 自己实现一个 “栈”
class Stack:
    def __init__(self):
        self.items = []

    def isEmpty(self):
        """
        判断“栈”是否为空
        """
        return self.items == []

    def size(self):
        """
        返回”栈“的大小
        """
        return len(self.items)

    def push(self, item):
        """
        向栈里添加数据
        """
        self.items.append(item)

    def peek(self):
        """
        返回“栈”最顶端数据,不做修改或删除
        """
        return self.items[len(self.items) - 1]

    def pop(self):
        """
        从栈顶取出一个数据
        """
        return self.items.pop()

使用Python面向对象编程配合列表可以很容易实现 “栈” 的数据结构

  • 使用栈做案例:识别括号,有许多编程语言都来依据括号来判断作用域的,我们现在要做的案例就是基于栈准确识别括号的程序,例如:(()()())✔️ ((())❌ Stack() 调用的是上面实现栈的代码,案例如下:
def par_check(par_string):
    """
    识别括号格式是否正确
    :param par_string:
    :return:
    """
    S, balanced, index = Stack(), True, 0
    while index < len(par_string) and balanced:
        symbol = par_string[index]
        if symbol == "(":
            S.push(symbol)
        else:
            if S.isEmpty():
                balanced = False
            else:
                S.pop()
        index += 1

    if balanced and S.isEmpty():
        return True
    else:
        return False


print(par_check("((()))"))
print(par_check("(()))"))
  • 使用栈来做十进制转换:
  1. 二进制概述:我们日常生活中使用的是十进制,而计算机中全部采用的是二进制只有:0、1两个数,逢二进一
  2. 将十进制转换为二进制,下面的例子数将12转换为二进制,整除二取余数:12 / 2 = 6 余数为 0、6 / 2 = 3 余数为0、3 / 2 = 1 余数为1、1 / 2 = 1 余数为1;12的二进制结果为:1100 我们发现先计算出来的数,最后取出,刚好符合栈的结构,下面我们使用栈来实现一个二进制转换函数
  3. 十进制转换二进制代码实现(结合刚才实现的Stack):
def divide_by2(dec_num):
    S = Stack()
    while dec_num > 0:
        S.push(dec_num % 2)
        dec_num = dec_num // 2

    return int("".join([str(S.pop()) for i in range(S.size())]))


print(divide_by2(12))
  1. 十进制转换十六进制以下任意进制代码(原理都一样接着来尝试吧):
def base_converter(dec_num, base):
    digits = "0123456789ABCDEF"
    stack = Stack()
    while dec_num > 0:
        stack.push(dec_num % base)
        dec_num = dec_num // base

    return "".join([str(digits[stack.pop()]) for i in range(stack.size())])


print(base_converter(233, 16))
相关标签: 数据结构与算法