栈抽象数据类型由下面的结构和操作定义。栈是元素的有序集合，添加操作与移除操作都发生在其顶端。栈的操作顺序是 LIFO，它支持以下操作：
-
Stack() 创建一个空栈。它不需要参数，且会返回一个空栈。
-
push(item) 将一个元素添加到栈的顶端。它需要一个参数 item，且无返回值。
-
pop() 将栈顶端的元素移除。它不需要参数，但会返回顶端的元素，并且修改栈的内容。
-
peek() 返回栈顶端的元素，但是并不移除该元素。它不需要参数，也不会修改栈的内容。
-
isEmpty() 检查栈是否为空。它不需要参数，且会返回一个布尔值。
-
size() 返回栈中元素的数目。它不需要参数，且会返回一个整数。
抽象数据类型的实现常被称为数据结构
和其他面向对象编程语言一样，每当需要在 Python 中实现像栈这样的抽 象数据类型时，就可以创建新类。栈的操作通过方法实现。更进一步地说，因为栈是元素的集合， 所以完全可以利用 Python 提供的强大、简单的原生集合来实现。这里，我们将使用列表。
Python 列表是有序集合，它提供了一整套方法。举例来说，对于列表 [2, 5, 3, 6, 7, 4]， 只需要考虑将它的哪一边视为栈的顶端。一旦确定了顶端，所有的操作就可以利用 append 和 pop 等列表方法来实现。
栈的实现，它假设列表的尾部是栈的顶端。当栈增长时（即进行 push 操作），新的元素会被添加到列表的尾部。pop 操作同样会修改这一端。
# 用 Python实现栈
class Stack:
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def push(self, item):
self.items.append(item)
def pop(self):
if not self.items:
return None
else:
return self.items.pop()
def peek(self):
if not self.items:
return None
else:
return self.items[-1]
def size(self):
return len(self.items)
值得注意的是，也可以选择将列表的头部作为栈的顶端。
不过在这种情况下，便无法直接使用 pop 方法和 append 方法，而必须要用 pop 方法和 insert 方法显式地访问下标为 0 的元素， 即列表中的第 1 个元素。
# 栈的另一种实现方式，选择将列表的头部作为栈的顶端
class Stack2:
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def push(self, item):
self.items.insert(0, item)
def pop(self):
return self.items.pop(0)
def peek(self):
return self.items[0]
def size(self):
return len(self.items)
改变抽象数据类型的实现却保留其逻辑特征，这种能力体现了抽象思想。
尽管上述两 种实现都可行，但是二者在性能方面肯定有差异：
-
append() 方法和 pop() 方法的时间复杂度都是 O(1)
- 这意味着不论栈中有多少个元素，第一种实现中的 push 操作和 pop 操作都会在恒定的时间内完成
-
第二种实现的性能则受制于栈中的元素个数
- 因为 insert(0) 和 pop(0) 的时间复杂度都是 O(n)，元素越多就越慢