栈

栈是一种操作受限的线性表只允许从一端插入和删除数据。栈有两种存储方式，即线性存储和链接存储（链表）。栈的一个最重要的特征就是栈的插入和删除只能在栈顶进行，所以每次删除的元素都是最后进栈的元素，故栈也被称为后进先出（LIFO）表。

栈的应用场景

• 递归
• Ctrl+Z
• 括号匹配

栈的实现(Python)

栈的常见操作：

Stack()         创建栈
push(item)      将数据item放在栈的顶部
pop()             返回栈顶部数据，并从栈中移除该数据
peek()           返回栈顶部数据，但不移除
size()            返回栈的大小
is_empty()       返回栈是否为空

实现：

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

    def is_empty(self):
        return self.__items == []

    def size(self):
        return len(self.__items)

    def push(self,val):
        self.__items.append(val)
        return

    def pop(self):
        self.__items.pop()

    def peek(self):
        return self.__items[len(self.__items)-1]