python使用顺序表实现栈

1. 栈

栈：是一种容器，可以存入数据元素，访问元素，删除元素，特点在于只能允许在容器的一段【栈顶】输入和输出数据。原理运作为后进先出【先进后出】

1.1栈的构造

1.1.1 构造函数

• 使用顺序表list作为栈的容器
• 将list设为私有

def __init__(self):
        # 使用python的list作为栈的容器
        self.__list = []

1.1.2 push函数

• 作用：压栈
• 可以自行选择将列表的头部或尾部作为栈顶
• 但是由于链表的尾部操作时间复杂度更低，因此使用尾部插入【即将尾部作为栈顶】

 def push(self,item):
        """添加一个新元素item到栈顶"""
        self.__list.append(item)

1.1.3 pop函数

• 作用：弹栈
• 使用pop方法，从尾部弹出。返回list的末尾元素

def pop(self):
        """弹出栈顶元素"""
        return self.__list.pop()

1.1.4 peek函数

• 作用：返回栈顶的元素
• 使用__list[-1]将列表的最后一个元素返回
  【注意】
• 由于列表为空时不支持负索引操作，因此需要先判断列表是否为空，如果为空则返回None

def peek(self):
        """返回栈顶元素"""
        if self.__list:
            return self.__list[-1]
        else:
            return None

1.1.5 is_empty函数

• 作用：判断栈是否为空
• 如果self.__list == []，则返回 True

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

1.1.5 size函数

• 作用：返回栈的元素个数
• 使用len即可

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

2.完整代码

class stack(object):
    """栈的实现"""
    def __init__(self):
        # 使用python的list作为栈的容器
        self.__list = []
        
    def push(self,item):
        """添加一个新元素item到栈顶"""
        self.__list.append(item)
        
    def pop(self):
        """弹出栈顶元素"""
        return self.__list.pop()
    def peek(self):
        """返回栈顶元素"""
        if self.__list:
            return self.__list[-1]
        else:
            return None
    
    def is_empty(self):
        """判断栈是否为空"""
        return self.__list == []
    
    def size(self):
        """返回栈的元素个数"""
        return len(self.__list)