Python3数据结构05 - 栈

  • 原创
  • Madman
  • /
  • 2018-09-06 10:21
  • /
  • 0
  • 136 次阅读

Synopsis: 栈(stack)又名堆栈,它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素

代码已上传到 https://github.com/wangy8961/python3-algorithms ,欢迎star

1. 栈

栈(stack)也称为堆栈,堆栈数据结构有两种基本操作:

  • 压入(push): 将数据元素压入栈的顶端
  • 弹出(pop): 将栈的顶端数据元素弹出

它只允许在一端进行操作,因而按照后进先出(LIFO, Last In First Out)的原理运作(类似于枪的弹夹,最先压入的子弹最后被打出)

2. Python实现

栈可以用顺序表或链表来实现,这里使用顺序表,即Python中的列表来实现栈数据结构

class Stack:
    '''用顺序表实现栈'''
    def __init__(self):
        self.__list = []  # 用来存放元素的容器,这里使用列表(顺序表)

    def is_empty(self):
        '''判断栈是否为空'''
        return self.__list == []

    def size(self):
        '''返回栈的元素个数'''
        return len(self.__list)

    def push(self, value):
        ''' 将数据元素压入栈的顶端
        这里假设列表的尾部是栈顶,列表的头部是栈底,因为顺序表的尾部插入时间复杂度是O(1)'''
        self.__list.append(value)

    def pop(self):
        '''将栈的顶端数据元素弹出,这里假设列表的尾部是栈顶'''
        return self.__list.pop()

    def peek(self):
        '''仅返回栈顶元素的值,但不弹出它'''
        if self.__list:  # 栈不为空时
            return self.__list[-1]
        else:
            return None

测试:

if __name__ == '__main__':
    # 创建空栈
    s = Stack()
    print('*' * 20 + ' 空栈时: ' + '*' * 20)
    print('是否为空栈: ', s.is_empty())
    print('栈的元素个数: ', s.size())

    # 压入一些元素
    s.push(10)
    s.push('Python')
    s.push(23.50)
    s.push('Hello')
    s.push(100)
    print('*' * 20 + ' 压入一些元素后: ' + '*' * 20)
    print('是否为空栈: ', s.is_empty())
    print('栈的元素个数: ', s.size())

    # 弹出栈顶元素
    print('*' * 20 + ' 弹出栈顶元素: ' + '*' * 20)
    print(s.pop())

    # 再次弹出栈顶元素
    print('*' * 20 + ' 再次弹出栈顶元素: ' + '*' * 20)
    print(s.pop())

    # 仅返回栈顶元素的值,但不弹出
    print('*' * 20 + ' 仅返回栈顶元素的值,但不弹出: ' + '*' * 20)
    print(s.peek())

    # 再次弹出栈顶元素
    print('*' * 20 + ' 再次弹出栈顶元素: ' + '*' * 20)
    print(s.pop())

    # Output:
    # ******************** 空栈时: ********************
    # 是否为空栈:  True
    # 栈的元素个数:  0
    # ******************** 压入一些元素后: ********************
    # 是否为空栈:  False
    # 栈的元素个数:  5
    # ******************** 弹出栈顶元素: ********************
    # 100
    # ******************** 再次弹出栈顶元素: ********************
    # Hello
    # ******************** 仅返回栈顶元素的值,但不弹出: ********************
    # 23.5
    # ******************** 再次弹出栈顶元素: ********************
    # 23.5

代码已上传到 https://github.com/wangy8961/python3-algorithms ,欢迎star

未经允许不得转载: LIFE & SHARE - 王颜公子 » Python3数据结构05 - 栈

分享

作者

作者头像

Madman

如果博文内容有误或其它任何问题,欢迎留言评论,我会尽快回复; 或者通过QQ、微信等联系我

0 条评论

暂时还没有评论.

发表评论前请先登录