栈的Python实现与实例分析

偏执的太偏执、 2022-05-31 10:21 132阅读 0赞

栈是限定只有一端可以进行插入和删除操作的有序线性存储结构，满足先进后出的约束。

生活中典型的实例就是一叠盘子，一般都只是在最上面放置或者拿掉盘子。

计算机中典型的实例就是浏览器的返回操作，你访问的网页地址实际被存放在一个栈中，栈顶是你最近访问的那个

### Python实现 ###

在 Python 中，因为列表的有序机制和自有的一组方法，可以很好的作为栈的底层实现，只需要确定列表的哪一端作为栈的可操作端，也就是栈顶。同时，把栈抽象为类，栈的先进后出操作实现为类的方法。

因为 append 和 pop 的列表方法可以方便地对列表尾部进行操作，因此将列表尾部做为栈顶，将有更低的复杂度，插入和删除操作的复杂度都为 O(1)，而如果将列表头部作为栈顶，插入和删除的同时都需要移动后面的元素，复杂度都为 O(n)。

以下为栈的 Python 实现：

Stack 实现一个栈类，可通过 Stack() 建立一个空栈

is\_empty 操作判断栈是否为空

push 操作将新元素添加到列表的末尾

pop 操作将返回并删除列表末尾的元素

size 操作返回栈的大小

#栈的实现
    class Stack:
        def __init__(self):
            self.items=[]
        def is_empty(self):
            return self.items==[]
        def push(self,item):
            self.items.append(item)
        def pop(self):
            return self.items.pop()
        def size(self):
            return  len(self.items)

以上为栈的最简单实现，在实际应用中，可能还需要限定栈的大小，对 push 和 pop 操作进行异常处理，增加栈的方法如栈的输出和翻转等等，感兴趣的可以自己实现一下。

### 应用实例 ###

我们知道，在计算机中存储的都是0和1，因此二进制在计算机科学中是非常重要的。而生活中常用的都是十进制，使得十进制到二进制的转换在计算机中非常普遍。

以十进制的233为例，

233=1∗27\+1∗26\+1∗25\+0∗24\+1∗23\+0∗22\+0∗21\+1∗20  233 = 1 ∗ 2 7 + 1 ∗ 2 6 + 1 ∗ 2 5 + 0 ∗ 2 4 + 1 ∗ 2 3 + 0 ∗ 2 2 + 0 ∗ 2 1 + 1 ∗ 2 0

得到的11101001即为233的二进制，也可以看出可通过「除2」运算并跟踪余数来得到二进制数。

这里讨论“除 2” 运算从正整数开始。不断迭代的将十进制除以 2，并跟踪余数。第一个除以 2 的余数说明了这个值是偶数还是奇数。偶数有 0 的余数，记为 0。奇数有余数 1，记为1。我们将得到的二进制构建为数字序列，第一个余数实际上是二进制序列中的最后一个数字。见下图 ，我们看到了反转，也即先进后出的属性，表示栈可以作为解决这个问题的数据结构。

![这里写图片描述][70]

注：上图来自[Converting Decimal Numbers to Binary Numbers][]  
下面是在生成 Stack 类的基础下，Python 实现正整数十进制到二进制的转换

#正整数十进制到二进制的转换函数
    def transform(num):
        stack1=Stack()
        while num !=0:
            remainder=num%2
            num=int(num/2)
            stack1.push(remainder)
        s=''
        while not stack1.is_empty():
            s+=str(stack1.pop())
        return s
    #主函数
    if __name__=='__main__':
        s=transform(233)
        print(s)
    #输出结果：
    11101001

[70]: /images/20220531/bae341e6e73b4f11b4a42fc872b6a45c.png
[Converting Decimal Numbers to Binary Numbers]: http://interactivepython.org/runestone/static/pythonds/BasicDS/ConvertingDecimalNumberstoBinaryNumbers.html