Python3数据结构05 - 栈

  • 原创
  • Madman
  • /
  • /
  • 0
  • 1612 次阅读

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 
                                
                            
未经允许不得转载: LIFE & SHARE - 王颜公子 » Python3数据结构05 - 栈

分享

作者

作者头像

Madman

如需 Linux / Python 相关问题付费解答,请按如下方式联系我

0 条评论

暂时还没有评论.