概念

栈（stack），也称为“堆栈”，是一种容器，可以存入数据元素、访问数据元素、删除数据元素。其特点是只能在容器的一端（成为栈顶，top）进行数据的添加（push）和输出（pop）运算。栈结构只允许在容器一端进行操作，因此按照后进先出（LIFO，last in first out）的原理进行运作。

上图就是栈结构的示意图，出栈入栈的操作都是在栈顶进行。

栈结构的实现

栈结构可以使用顺序表实现，也可以使用链表实现。该类型数据结构的相关操作如下，

方法	说明
Stack()	创建一个栈对象
push(item)	将一个元素添加到栈顶
pop()	弹出栈顶元素
peek()	返回栈顶元素
is_empty()	判断栈是否为空
size()	返回栈中元素个数

顺序表实现

class Stack:
    def __init__(self):
        self.__list = []

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

    def pop(self):
        """弹出栈顶元素"""
        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)

单向链表实现

访问私有变量方式(不推荐)

使用顺序表专题中单向链表中定义的单向链表，

from single_link_list import SingleLinkList

class Stack:
    def __init__(self):
        self.__link = SingleLinkList()

    def is_empty(self):
        return self.__link.is_empty()

    def size(self):
        return self.__link.length()

    def push(self, item):
        # 使用头插法添加在头部
        self.__link.add(item)

    def pop(self):
        if self.__link.is_empty():
            return 
        # 这是因为Python中私有变量实际上是伪私有，所以可以这样访问，但是不推荐
        self.__link_SingleLinkList__head = self.__link_SingleLinkList__head.next

    def peek(self):
        if self.__link.is_empty():
            return None
        else:
            return self.__link_SingleLinkList__head

上面的代码中，SingleLinkList类的 __head是私有变量，访问私有变量是不安全的。

重新定义栈节点

# 节点类
class Node:
    def __init__(self, item):
        self.item = item
        self.next = None

class Stack:
    def __init__(self):
        self.__top = None
        self.__count = 0

    def is_empty(self):
        return self.__top == None

    def size(self):
        return self.__count

    def push(self, item):
        node = Node(item)
        if self.is_empty():
            self.__top = node
        else:
            node.next = self.__top
            self.__top = node
        self.__count += 1

    def pop(self):
        if not self.is_empty():
            self.__top = self.__top.next
            self.__count -= 1

    def peek(self):
        if self.is_empty():
            return None
        return self.__top.item