Python3数据结构05 - 栈

原创

Madman

7968 次阅读

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