数据结构之栈（python）

🕗 发布于 2024-09-25 03:12 数据结构 python 开发语言

1.栈存储结构

栈和队列，严格意义上来说，也属于线性表，因为它们也都用于存储逻辑关系为 一对一 的数据。使用栈结构存储数据，讲究“先进后出”，即最先进栈的数据，最后出栈；
使用队列存储数据，讲究 “先进先出”，即最先进队列的数据，也最先出队列。既然栈和队列都属于线性表，根据线性表分为顺序表和链表的特点，栈也可分为顺序栈和链栈，队列也分为顺序队列和链队列

1.1栈的基本介绍

同顺序表和链表一样，栈也是用来存储逻辑关系为 “一对一” 数据的线性存储结构，如图1所示：

在这里插入图片描述

栈只能从表的一端存取数据，另一端是封闭的
在栈中，无论是存数据还是取数据，都必须遵循"先进后出"的原则，即最先进栈的元素最后出栈。
拿图1的栈来说，从图中数据的存储状态可判断出，元素 1 是最先进的栈。因此，当需要从栈中取出元素 1 时，根据"先进后出"的原则，需提前将元素 3 和元素 2 从栈中取出，然后才能成功取出元素 1
我们可以给栈下一个定义，即栈是一种只能从表的一端存取数据且遵循 “先进后出” 原则的线性存储结构
通常，栈的开口端被称为栈顶；相应地，封口端被称为栈底。因此，栈顶元素指的就是距离栈顶最近的元素，拿图2 来说，栈顶元素为元素 4；同理，栈底元素指的是位于栈最底部的元素，图2 中的栈底元素为元素 1

在这里插入图片描述

1.2进栈和出栈

向栈中添加元素，此过程被称为"进栈"（入栈或压栈）
从栈中提取出指定元素，此过程被称为"出栈"（或弹栈）

1.3栈的具体实现

顺序栈：采用顺序存储结构可以模拟栈存储数据的特点，从而实现栈存储结构
链栈：采用链式存储结构实现栈结构

两种实现方式的区别，仅限于数据元素在实际物理空间上存放的相对位置，顺序栈底层采用的是数组，链栈底层采用的是链表

1.4栈的应用

例一

我们经常使用浏览器在各种网站上查找信息。假设先浏览的页面 A，然后关闭了页面 A 跳转到页面 B，随后又关闭页面 B 跳转到了页面 C。而此时，我们如果想重新回到页面 A，有两个选择：

重新搜索找到页面 A；
使用浏览器的"回退"功能。浏览器会先回退到页面 B，而后再回退到页面 A。

浏览器 “回退” 功能的实现，底层使用的就是栈存储结构。当你关闭页面 A 时，浏览器会将页面 A入栈；同样，当你关闭页面 B 时，浏览器也会将 B入栈。因此，当你执行回退操作时，才会首先看到的是页面 B，然后是页面 A，这是栈中数据依次出栈的效果。

例二

不仅如此，栈存储结构还可以帮我们检测代码中的括号匹配问题。多数编程语言都会用到括号（小括号、中括号和大括号），括号的错误使用（通常是丢右括号）会导致程序编译错误，而很多开发工具中都有检测代码是否有编辑错误的功能，其中就包含检测代码中的括号匹配问题，此功能的底层实现使用的就是栈结构。

例三

同时，栈结构还可以实现数值的进制转换功能。例如，编写程序实现从十进制数自动转换成二进制数，就可以使用栈存储结构来实现。

2.顺序栈及基本操作（包含入栈和出栈）

2.1顺序栈的基础介绍

如果你仔细观察顺序表（底层实现是数组）和栈结构就会发现，它们存储数据的方式高度相似，只不过栈对数据的存取过程有特殊的限制，而顺序表没有。

在这里插入图片描述
这里给出使用顺序表模拟栈存储结构常用的实现思路，即在顺序表中设定一个实时指向栈顶元素的变量（一般命名为 top），top 初始值为 -1，表示栈中没有存储任何数据元素，及栈是"空栈"。一旦有数据元素进栈，则 top 就做 +1 操作；反之，如果数据元素出栈，top 就做 -1 操作。

2.2顺序栈元素`入栈`

模拟栈存储 {1,2,3,4} 的过程。最初，栈是"空栈"，即数组是空的，top 值为初始值 -1，如图 3 所示：

在这里插入图片描述
首先向栈中添加元素 1，我们默认数组下标为 0 一端表示栈底，因此，元素 1 被存储在数组 a[1] 处，同时 top 值 +1，如图 4 所示：

在这里插入图片描述
采用以上的方式，依次存储元素 2、3 和 4，最终，top 值变为 3，如图 5 所示：

在这里插入图片描述

2.3顺序栈元素`出栈`

其实，top 变量的设置对模拟数据的 “入栈” 操作没有实际的帮助，它是为实现数据的 “出栈” 操作做准备的。

在这里插入图片描述
注意，图 6 数组中元素的消失仅是为了方便初学者学习，其实，这里只需要对 top 值做 -1 操作即可，因为 top 值本身就表示栈的栈顶位置，因此 top - 1 就等同于栈顶元素出栈。并且后期向栈中添加元素时，新元素会存储在类似元素 4 这样的旧元素位置上，将旧元素覆盖。

2.4顺序栈的表示和实现

实现的基本功能：

初始化空栈
判断栈是否为空
返回栈顶元素
返回栈的长度
进栈
出栈
清空栈

代码实现

class sqStack:
    # 初始化栈
    def __init__(self, MAXSIZE):
        self.MAXSIZE = MAXSIZE
        self.data = [None] * self.MAXSIZE
        self.top = -1


    # 判断当前栈是否为空
    def is_empty(self):
        return self.top == -1

    # 返回栈顶元素
    def gettop(self):
        if self.is_empty():
            print("当前顺序栈为空")
            return None
        else:
            return self.data[self.top]



    # 入栈
    def Push(self,item):
        # 判断栈是否满
        if self.top == self.MAXSIZE - 1:
            return "sqStack is full"
        self.data[self.top + 1] = item
        self.top += 1


    # 列表入栈
    def ListPush(self,lst):
        # 判断栈是否满
        if self.top == self.MAXSIZE - 1:
            return "sqStack is full"
        for i in range(len(lst)):
            self.Push(lst[i])


    # 出栈
    def Pop(self):
        # 判断栈是否为空
        if self.is_empty():
            return "sqStack is empty"
        rs = self.data[self.top]
        self.top -= 1
        return rs

    # 计算栈的长度
    def size(self):
        return self.top + 1



    # 输出栈内元素
    def display(self):
        # 判断栈是否为空
        if self.is_empty():
            print("当前顺序栈为空", end=" ")
        else:
            print("当前链表元素为：", end="")
        for i in range(self.top + 1):
            print(self.data[i], end=" ")
        print()


    # 清空栈
    def clear(self):
        self.data = [None] * self.MAXSIZE
        self.top = -1



# 初始化一个长度为20的顺序栈
s = sqStack(20)
print("初始化：", s)
print("----------------------")

# 判断当前栈是否为空
print("当前栈是否为空：", s.is_empty())
print("----------------------")

# 输出栈的元素
s.display()
print("----------------------")
print("入栈前栈内元素：",end="")
s.display()

# 入栈
s.Push(1)
s.Push(10)
s.Push(100)

# 输出当前栈内的元素
print("入栈后栈内元素：", end="")
s.display()
print("----------------------")
print("当前栈的长度为：", s.size())
print("----------------------")
print("队列入栈前栈内元素：", end="")
s.display()
s.ListPush([1,2,3,4])
print("队列入栈后栈内元素：", end="")
s.display()
print("----------------------")
print("当前栈顶元素为：",s.gettop())
print("----------------------")

# 顶端元素出栈
print("出栈前栈内元素：",end="")
s.display()
print("出栈元素为：", s.Pop())
print("出栈后栈内元素：", end="")
s.display()
print("----------------------")

#输出当前栈内的元素
s.display()
print("----------------------")
s.clear()
s.display()
print("----------------------")

初始化： <__main__.sqStack object at 0x000002A011B38460>
----------------------
当前栈是否为空： True
----------------------
当前顺序栈为空 
----------------------
入栈前栈内元素：当前顺序栈为空 
入栈后栈内元素：当前链表元素为：1 10 100 
----------------------
当前栈的长度为： 3
----------------------
队列入栈前栈内元素：当前链表元素为：1 10 100 
队列入栈后栈内元素：当前链表元素为：1 10 100 1 2 3 4 
----------------------
当前栈顶元素为： 4
----------------------
出栈前栈内元素：当前链表元素为：1 10 100 1 2 3 4 
出栈元素为： 4
出栈后栈内元素：当前链表元素为：1 10 100 1 2 3 
----------------------
当前链表元素为：1 10 100 1 2 3 
----------------------
当前顺序栈为空 
----------------------

3.链栈及基本操作（包含入栈和出栈）

3.1链栈的基本介绍

通常我们将链表的头部作为栈顶，尾部作为栈底

在这里插入图片描述
将链表头部作为栈顶的一端，可以避免在实现数据 “入栈” 和 “出栈” 操作时做大量遍历链表的耗时操作。

链表的头部作为栈顶，意味着：
- 在实现数据"入栈"操作时，需要将数据从链表的头部插入
- 在实现数据"出栈"操作时，需要删除链表头部的首元节点

因此，链栈实际上就是一个只能采用头插法插入或删除数据的链表。

3.2链栈元素入栈

例如，将元素 1、2、3、4 依次入栈，等价于将各元素采用头插法依次添加到链表中，每个数据元素的添加过程如图 2 所示：

在这里插入图片描述

3.3链栈元素出栈

例如，图2 所示的链栈中，若要将元素 3 出栈，根据"先进后出"的原则，要先将元素 4 出栈，也就是从链表中摘除，然后元素 3 才能出栈，整个操作过程如图 3 所示：

在这里插入图片描述

3.4链栈的表示和实现

实现基本功能：

初始化空栈
判断栈是否为空
返回栈顶元素
进栈
出栈
清空栈

代码实现

# 定义链栈节点
class Node:
    # 初始化链栈
    def __init__(self, data):
        self.data = data
        self.next = None


class linkstack:
    # 初始化链栈
    def __init__(self):
        self.top = None


    # 判断链栈是否为空
    def is_empty(self):
        return self.top == None


    # 清空链栈
    def clear(self):
        self.top = None


    # 返回当前栈的长度
    def size(self):
        i = 0
        tempnode = self.top
        while tempnode is not None:   # 从头开始遍历
            tempnode = tempnode.next
            i += 1
        return i


    # 元素入栈
    def push(self, item):
        node = Node(item)
        node.next = self.top
        self.top = node

    # 栈顶元素出栈
    def pop(self):
        x = self.top.data
        self.top = self.top.next
        return x


    # 获取栈顶元素
    def gettop(self):
        return self.top.data


    # 输出当前栈内元素
    def display(self):
        if self.top == None:
            print("当前栈内元素为空", end="")
        else:
            print("当前栈内元素为：", end="")
        tempnode = self.top
        while tempnode is not None:
            print(tempnode.data, end=" ")
            tempnode = tempnode.next
        print()


s1 = linkstack()
print("初始化的栈为：", s1)
print("------------------------")
print("入栈前的链栈元素为：", end="")
s1.display()
s1.push(1)
s1.push(2)
s1.push(3)
s1.push(4)
s1.push(5)
s1.push(6)
print("入栈后的链栈元素为：", end="")
s1.display()
print("------------------------")
print("当前栈顶元素为：",s1.gettop())
print("------------------------")
print("当前链栈的长度为：", s1.size())
print("------------------------")
print("出栈前的链栈元素为：", end="")
s1.display()
print("出栈元素为：", s1.pop())
print("出栈后的链栈元素为：", end="")
s1.display()
print("------------------------")
print("清空前的链栈元素为：", end="")
s1.display()
s1.clear()
print("清空后的链栈元素为：", end="")
s1.display()
print("------------------------")
print("当前链栈是否为空：", s1.is_empty())
print("------------------------")

初始化的栈为： <__main__.linkstack object at 0x0000023734D08460>
------------------------
入栈前的链栈元素为：当前栈内元素为空
入栈后的链栈元素为：当前栈内元素为：6 5 4 3 2 1 
------------------------
当前栈顶元素为： 6
------------------------
当前链栈的长度为： 6
------------------------
出栈前的链栈元素为：当前栈内元素为：6 5 4 3 2 1 
出栈元素为： 6
出栈后的链栈元素为：当前栈内元素为：5 4 3 2 1 
------------------------
清空前的链栈元素为：当前栈内元素为：5 4 3 2 1 
清空后的链栈元素为：当前栈内元素为空
------------------------
当前链栈是否为空： True
------------------------

4.栈的应用

4.1括号匹配问题

括号匹配问题：给一个字符串，其中包含小括号、中括号、大括号，求该字符串中的括号是否匹配。

思路：

如果遇到左括号，都进栈；遇到右括号，查看栈顶是否为对应左括号，如果是对应左括号则该对应左括号出栈，如果是空栈则false，如果是不对应左括号则false。等遍历完整个字符串后，查看栈是否为空，如果为空则括号匹配成功，如果不为空则括号匹配失败。

# 定义顺序栈
class sqStack:
    # 初始化栈
    def __init__(self, MAXSIZE):
        self.MAXSIZE = MAXSIZE
        self.data = [None] * self.MAXSIZE
        self.top = -1

    # 判断当前栈是否为空
    def is_empty(self):
        return self.top == -1

    def gettop(self):
        if self.is_empty():
            print("当前顺序栈为空")
            return None
        else:
            return self.data[self.top]

    # 入栈
    def Push(self, item):
        # 判断栈是否已满
        if self.top == self.MAXSIZE - 1:
            return "sqStack is full."
        self.data[self.top + 1] = item
        self.top += 1

    # 列表入栈
    def ListPush(self, x):
        # 判断栈是否已满
        if self.top == self.MAXSIZE - 1:
            return "sqStack is full."
        for i in range((len(x))):
            self.Push(x[i])

    # 出栈
    def Pop(self):
        # 判断栈是否为空
        if self.is_empty():
            return "sqStack is empty"
        rs = self.data[self.top]
        self.top -= 1
        return rs

    # 输出栈的长度
    def size(self):
        return self.top + 1

    # 输出栈内元素
    def display(self):
        # 判断栈是否为空
        if self.is_empty():
            print("当前顺序栈为空", end=" ")
        else:
            print("当前链表元素为：", end="")
        for i in range(self.top + 1):
            print(self.data[i], end=" ")
        print()

    # 清空栈
    def clear(self):
        self.data = [None] * self.MAXSIZE
        self.top = -1


def matching(strings):  # 输入是一串字符
    bktStack = sqStack(60)  # 创建类实例
    flag = 1
    opens = "{[("
    closes = "}])"
    # 对于每个输入字符
    for i in strings:
        # 遇到左括号，就将其压栈
        if i in opens:
            bktStack.Push(i)
        # 遇到右括号
        elif i in closes:
            # 若已没左括号与之匹配
            if bktStack.is_empty():
                # 不匹配，结束
                return False
            # 左括号按什么顺序入，右括号应按相反顺序消掉。
            # 如果匹配，右括号消的始终是栈顶括号。
            # 弹栈bktStack.pop()，判断栈顶左括号与当前右括号是否匹配
            if closes.index(i) != opens.index(bktStack.Pop()):
                # 不匹配，结束
                return False
    # 若一直没有return而是遍历了一遍，且没有多余左括号留在栈中，则说明匹配。反之不匹配。
    return bktStack.is_empty()


# 判断返回的是True还是False
def check(strings):
    if matching(strings):
        print("%s 匹配正确!" % strings)
    else:
        print("%s 匹配错误！" % strings)

if __name__ == "__main__":
    # 测试函数
    for i in range(4):
        stringa = input()
        check(stringa)

{{([][])}()}
{{([][])}()} 匹配正确!
[[{{(())}}]]
[[{{(())}}]] 匹配正确!
[[(()(()))])]{}
[[(()(()))])]{} 匹配错误！

4.2十进制转二进制

当将一个十进制整数M转换为二进制数时，在计算过程中，把M与2求余得到的二进制数的各位依次进栈，计算完毕后将栈中的二进制数依次出栈输出，输出结果就是待求得的二进制数。

测试案例：
[200, 254, 153, 29, 108, 631, 892]

运行结果

在这里插入图片描述
代码实现：

class sqStack:
    # 初始化栈
    def __init__(self, MAXSIZE):
        self.MAXSIZE = MAXSIZE
        self.data = [None] * MAXSIZE
        self.top = -1


    # 判断当前栈是否为空
    def is_empty(self):
        return self.top == -1


    # 返回栈顶元素
    def gettop(self):
        if self.is_empty():
            print("当前顺序栈为空")
            return None
        else:
            return self.data[self.top]


    # 入栈
    def Push(self, item):
        # 判断栈是否已满
        if self.top == self.MAXSIZE - 1:
            return "sqStack is full"
        self.data[self.top + 1] = item
        self.top += 1

    # 列表入栈
    def ListPush(self, x):
        # 判断栈是否已满
        if self.top == self.MAXSIZE - 1:
            return "sqStack is full"
        for i in range(len(x)):
            self.Push(x[i])


    # 出栈
    def Pop(self):
        # 判断栈是否为空
        if self.is_empty():
            return "sqStack is empty"
        rs = self.data[self.top]
        self.top -= 1
        return rs


    # 输出栈的长度
    def size(self):
        return self.top + 1


    # 输出栈内元素
    def display(self):
        # 判断栈是否为空
        if self.is_empty():
            print("当前顺序栈为空", end=" ")
        else:
            print("当前链表元素为：", end="")
        for i in range(self.top + 1):
            print(self.data[i], end=" ")
        print()


    # 清空栈
    def clear(self):
        self.data = [None] * self.MAXSIZE
        self.top = -1



s = sqStack(20)
data = int(input("请输入十进制数："))
while data != 0:
    ys = data % 2
    s.Push(ys)
    data = data // 2

while s.top != -1:
    print(s.Pop(), end="")

请输入十进制数：200
11001000

请输入十进制数：254
11111110

请输入十进制数：153
10011001

请输入十进制数：29
11101

请输入十进制数：108
1101100

请输入十进制数：631
1001110111

请输入十进制数：892
1101111100

4.3十进制转N进制

当将一个十进制整数M转换为N进制数时，在计算过程中，把M与N求余得到的N进制数的各位依次进栈，计算完毕后将栈中的N进制数依次出栈输出，输出结果就是待求得的N进制数。

测试案例：

测试数：[200, 254, 153, 29, 108, 631, 892]
进制：[4, 8, 16]

自由搭配即可，这里我主要使用了random.choice()来对测试数要转换的进制随机取数

代码实现：

class sqStack:
    # 初始化栈
    def __init__(self, MAXSIZE):
        self.MAXSIZE = MAXSIZE
        self.data = [None] * MAXSIZE
        self.top = -1


    # 判断当前栈是否为空
    def is_empty(self):
        return self.top == -1


    # 返回栈顶元素
    def gettop(self):
        if self.is_empty():
            print("当前顺序栈为空")
            return None
        else:
            return self.data[self.top]


    # 入栈
    def Push(self, item):
        # 判断栈是否已满
        if self.top == self.MAXSIZE - 1:
            return "sqStack is full"
        self.data[self.top + 1] = item
        self.top += 1

    # 列表入栈
    def ListPush(self, x):
        # 判断栈是否已满
        if self.top == self.MAXSIZE - 1:
            return "sqStack is full"
        for i in range(len(x)):
            self.Push(x[i])


    # 出栈
    def Pop(self):
        # 判断栈是否为空
        if self.is_empty():
            return "sqStack is empty"
        rs = self.data[self.top]
        self.top -= 1
        return rs


    # 输出栈的长度
    def size(self):
        return self.top + 1


    # 输出栈内元素
    def display(self):
        # 判断栈是否为空
        if self.is_empty():
            print("当前顺序栈为空", end=" ")
        else:
            print("当前链表元素为：", end="")
        for i in range(self.top + 1):
            print(self.data[i], end=" ")
        print()


    # 清空栈
    def clear(self):
        self.data = [None] * self.MAXSIZE
        self.top = -1



def divideByN(number, base):
    digits = "0123456789ABCDEF"
    remstack = sqStack(100)
    while number > 0:
        rem = number % base
        remstack.Push(rem)
        number = number // base
    newString = ""
    while not remstack.is_empty():
        newString = newString + digits[remstack.Pop()]
    return newString


import random
numbers = [200,254,153,29,108,631,892]
bases = [4,8,16]
for number in numbers:
    base = random.choice(bases)
    print(f"{number} 的 {base}进制数为：{divideByN(number, base)}")

200 的 16进制数为：C8
254 的 4进制数为：3332
153 的 4进制数为：2121
29 的 4进制数为：131
108 的 16进制数为：6C
631 的 8进制数为：1167
892 的 8进制数为：1574

原文地址：https://blog.csdn.net/huaz_md/article/details/142305849

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：全面加速量产节奏！移远通信5G RedCap模组RG255C-GL顺利通过全球及欧美澳认证
下一篇：vue3中使用vue3-scroll-seamless插件

MoneyPrinterTurbo - AI自动生成高清短视频
MoneyPrinterTurbo是一款基于AI大模型的开源软件，旨在通过一键操作帮助用户自动生成高清短视频。只需提供一个视频主题或 **关键词** ，就可以全自动生成视频文案、视频素材、视频字幕、
阅读更多2024-11-18
跨平台WPF框架Avalonia教程五
在 Avalonia 11 之前，控件主题是使用标准样式创建的。然而，这种方法存在一个根本性的问题：一旦样式被应用到控件上，就没有办法移除它。因此，如果你想为特定的控件实例或用户界面（UI）部分更改
阅读更多2024-11-18
Linux 下网络套接字(Socket) 与udp和tcp 相关接口
Linux下套接字的介绍与使用
阅读更多2024-11-18
react 中 useReducer Hook 作用
useState`是最基本的状态管理钩子。`useReducer`提供了一种更可预测的状态管理方式。
阅读更多2024-11-18
【自学笔记】推荐系统
（Retrieval）步骤的目的是从庞大的候选集合中快速筛选出一小部分最有可能满足用户需求的项目。这样做可以简化梯度计算，更显著的变化是，如果人没有为任何样本打分，那代入TA的初始参数。我们需要做的是
阅读更多2024-11-18
【jvm】方法区是否存在GC
6.在Hotspot虚拟机中，方法区对应的是持久代（PermGen space，在JDK 8及之后被元空间Metaspace取代），尽管持久代上的GC较少，但并不代表完全没有。2.在JVM（Java虚
阅读更多2024-11-18
2411rust,异步函数
2411rust,异步函数
阅读更多2024-11-18
用 Python 从零开始创建神经网络（八）：梯度、偏导数和链式法则
在我们继续编写我们的神经网络代码之前，最后两个需要解决的难题是梯度和偏导数的相关概念。我们到目前为止解决的导数案例都是函数中只有一个独立变量的情况——也就是说，结果完全依赖于xx（在我们的案例中）。然
阅读更多2024-11-18
深度学习之One Stage目标检测算法2
YOLO（You Only Look Once: Unified, Real-Time Object Detection）是one-stage detection的开山之作。之前的物体检测方法首先需要
阅读更多2024-11-18
TCP协议的代理IP是什么？
对于需要大量数据传输和高效通信的场景，代理IP技术提供了至关重要的支持。TCP协议作为互联网通信中最基础和最常用的协议之一，与代理IP技术的结合成为了许多企业和开发者进行网络操作时不可或缺的一部分。那
阅读更多2024-11-18

数据结构之栈（python）

栈（顺序栈与链栈）

1.栈存储结构

1.1栈的基本介绍

1.2进栈和出栈

1.3栈的具体实现

1.4栈的应用

例一

例二

例三

2.顺序栈及基本操作（包含入栈和出栈）

2.1顺序栈的基础介绍

2.2顺序栈元素入栈

2.3顺序栈元素出栈

2.4顺序栈的表示和实现

3.链栈及基本操作（包含入栈和出栈）

3.1链栈的基本介绍

3.2链栈元素入栈

3.3链栈元素出栈

3.4链栈的表示和实现

4.栈的应用

4.1括号匹配问题

4.2十进制转二进制

4.3十进制转N进制

相关文章

2.2顺序栈元素`入栈`

2.3顺序栈元素`出栈`