前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >图解算法系列(五): 堆栈

图解算法系列(五): 堆栈

作者头像
公众号---人生代码
发布2019-07-24 11:54:48
6390
发布2019-07-24 11:54:48
举报
文章被收录于专栏:人生代码

下压栈(或简称栈)是一种基于后进后出的(LIFO)策咯的集合类型. 其中添加移除新项总发生在同一端。这一端通常称为“顶部”。与顶部对应的端称为“底部”。栈的例子很常见,想象桌上有一堆书., 只有顶部的那本书封面可见,要看到其他书的封面,只有先移除他们上面的书.

下图反应了栈中数据加入和移走的顺序:

栈的抽象数据类型

一个栈一般会实现以下方法:

代码语言:javascript
复制
Stack() 构造方法,创建一个空栈,无参数,返回值是空栈

push(value) 向栈顶压入一个新数据项,需要一个数据项参数,无返回值

pop() 抛出栈顶数据项,无参数,返回被抛出的数据项,栈本身发生变化

is_empty() 测试栈是否空栈。不需要参数,返回布尔值

size() 返回栈内数据项的数目,不需要参数,返回值是整数

peak() 返回栈顶数据项,但不删除。不需要参数,栈不变

栈的python实现(一)

利用.append与.pop方法,我们可以把python内置的列表当作栈来使用(栈是一种特殊的列表),这是一种较为方便的实现方式

代码语言:javascript
复制
class Stack:
    def __init__(self):
        self.values = []

    def push(self, value):       
        self.values.append(value)

    def pop(self):
        return self.values.pop()

    def is_empty(self):
        return self.size() == 0

    def size(self):
        return len(self.values)

    def peak(self):
        return self.values[self.size()-1]

栈的python实现(二)

或者自由定义类似列表的Stack类

代码语言:javascript
复制
class Node:  ➊
    def __init__(self, value):
        self.value = value
        self.next = None


class Stack: ➋
    def __init__(self):
        self.top = None

    def push(self, value):
        node = Node(value)
        node.next = self.top
        self.top = node

    def pop(self):
        node = self.top
        if node is None:
            raise Exception('This is an empty stack')
        self.top = node.next
        return node.value

    def peek(self):
        node = self.top
        if node is None:
            raise Exception('This is an empty stack')
        return node.value

    def is_empty(self):
        return not self.top

    def size(self):
        node = self.top
        count = 0
        if node is None:
            raise Exception('This is an empty stack')
        while node is not None:
            count += 1
            node = node.next
        return count


if __name__ == '__main__':
    stack = Stack()
    stack.push(2)
    stack.push(3)
#    print(stack.pop())
#    print(stack.top.value)
    print(stack.peek())
    print(stack.is_empty())
    print(stack.size())

➊ 定义一个结点

➋ 定义一个栈

top指向栈顶的Node,next之想下一个Node,若没有下一个Node,则指向一个None 栈的应用 十进制转二进制 是一个应用堆栈的典型案例。十进制转二进制 采用“除2取余,逆序排列”的方法,如图所示:! 借助Stack类,可以很方便地实现上述转换算法:

代码语言:javascript
复制
def divideBy2(decNumber):
    remstack = Stack()

    while decNumber > 0:
        rem = decNumber % 2
        # 将余数逐个加入
        remstack.push(rem)
        decNumber = decNumber // 2

    binString = ""
    while not remstack.is_empty():
        binString = binString + str(remstack.pop())

    return binString

if __name__ == '__main__':
    print(divideBy2(42))

运行结果:

代码语言:javascript
复制
$ python dec2bin.py
101010

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2019-07-14,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 CryptoCode 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 栈的抽象数据类型
  • 栈的python实现(一)
  • 栈的python实现(二)
  • ➊ 定义一个结点
  • ➋ 定义一个栈
  • 运行结果:
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档