栈的实现

——直接用顺序表（列表list）进行

栈结构实现

栈可以用顺序表实现，也可以用链表实现。

栈的操作

Stack() 创建一个新的空栈
push(item) 添加一个新的元素item到栈顶
pop() 弹出栈顶元素
peek() 返回栈顶元素——不出栈
is_empty() 判断栈是否为空
size() 返回栈的元素个数

添加元素，称为“压栈”（“入栈”），英文中成为push
弹出元素，在栈顶pop出元素

• 逻辑值真假总结：
  假：空字符串，0，空列表，空元组

数据类型	False	True
整型	0	其他
浮点型	0.0	其他
字符串	‘’	其他
字典	{}	其他
元组	()	其他
列表	[]	其他
None	None	空格

不同逻辑运算符的优先级：

not > and > or

代码实现：

# coding:utf-8

class Stack(object):
    """栈"""
    """Stack() 创建一个新的空栈
push(item) 添加一个新的元素item到栈顶
pop() 弹出栈顶元素
peek() 返回栈顶元素
is_empty() 判断栈是否为空
size() 返回栈的元素个数"""

    def __init__(self):
        # 不希望把容器直接给使用者，否则别人可以绕过以下功能直接操作
        self.__list = []  # 一开始没有元素，空列表

    def push(self, item):
        """添加新的元素"""
        # 根据容器不同，选择头尾
        self.__list.append(item)
        # self.__list.insert(0, item)  # 用顺序表的话，尾部为O（1）

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

    def peek(self):
        """返回栈顶元素"""
        # 空列表不支持-1操作，所以要有判断
        if self.__list:
            return self.__list()
        else:
            return None

    def is_empty(self):
        """判断是否为空"""
        # 遇到return的时候，先计算右边的值，如果是逻辑值就返回
        # 判断空，如果是空的，就返回真，否则返回假
        return self.__list == []
        # return not self.__list 等同的效果

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

if __name__ == "__main__":
    s = Stack()
    s.push(1)
    s.push(2)
    s.push(3)
    s.push(4)
    print(s.pop())
    print(s.pop())
    print(s.pop())
    print(s.pop())

实现结果：

结果