关于栈的介绍，请参考：https://blog.csdn.net/weixin_43790276/article/details/104033337
栈的数据存储结构可以是顺序表，也可以是链表，本篇使用 Python 来分别实现顺序栈和链栈。
一、实现顺序栈
顺序栈是使用顺序表存储数据的栈，Python 中的列表元组都属于顺序表，选用列表会更方便，所以下面使用列表来存储数据。
# coding=utf-8
class SequenceStack(object):
def __init__(self):
self.__members = list()
def is_empty(self):
return not len(self.__members)
def show(self):
if self.is_empty():
print('空栈')
return
for member in self.__members:
print('|' + member, end='')
print()
def push(self, data):
self.__members.append(data)
def pop(self):
if self.is_empty():
return
return self.__members.pop()
def length(self):
return len(self.__members)
def check(self):
if self.is_empty():
return
return self.__members[len(self.__members)-1]定义一个 SequenceStack() 类，实例化的时候会创建一个空列表，这就有了一个空的顺序栈。 Python 中的列表有很多自带的方法，所以在初始化一个顺序栈时，将存储数据的列表设置成私有属性，避免用户在类外面链式调用列表的其他方法。如果用户直接在类外面操作列表，则栈“后进先出”的规则可能会被破坏。
下面是顺序栈的各个方法实现：
is_empty(): 判断顺序栈是否为空。如果存储数据的列表长度为零(对应布尔值False)，则顺序栈为空(is_empty为True)，反之。
show(): 展示顺序栈中的数据，也就是将栈中所有的数据依次打印输出。对存储数据的列表遍历输出即可，为了展示得更形象一点，我在栈底(封闭的一端)打印竖线，表示不能从这一端取数据。
push(data): 压栈，也就是将数据添加到栈中。如果将列表的结尾当成栈顶，则压栈可以直接调用列表的 append(data) 方法。如果将列表的开头当做栈顶，则调用列表的 insert(0, data) 方法来实现压栈。
pop(): 出栈，也就是将数据从栈中取出，并将取出的数据返回。如果将列表的结尾当成栈顶，则出栈可以直接调用列表的 pop() 方法，pop() 方法默认就是弹出并返回列表的最后一个数据。如果将列表的开头当做栈顶，则调用列表的 pop(0) 方法时弹出第一个数据。
length(): 返回顺序栈的长度。顺序栈的长度就是存储数据的列表长度。
check(): 返回顺序栈栈顶位置的数据。在从顺序栈中取数据之前，如果要先知道栈顶位置的数据是什么，可以使用此方法。如果将列表的结尾当成栈顶，则返回列表最后一个位置的数据，如果将列表的头当成栈顶，则返回列表的第一个数据。
if __name__ == '__main__':
ss = SequenceStack()
print("is_empty: ", ss.is_empty())
ss.show()
ss.push('a')
ss.push('b')
ss.push('c')
ss.push('d')
ss.push('e')
ss.show()
print(ss.pop())
ss.show()
print("sequence stack length: ", ss.length())
print("top member is: ", ss.check())运行结果：
is_empty: True
空栈
|a|b|c|d|e
e
|a|b|c|d
sequence stack length: 4
top member is: d二、实现链栈
链栈是使用链表存储数据的栈，链表是逻辑有序的，由一个一个的节点构成，所以要先声明一个可以创建节点的类。
class Node(object):
def __init__(self, data):
self.data = data
self.next = None
下面按照单向链表的方式来实现链栈。
class LinkStack(object):
def __init__(self):
self.__head = None
def is_empty(self):
return not self.__head
def show(self):
if self.is_empty():
print('空栈')
return
cur = self.__head
while cur is not None:
if cur.next is not None:
print('|' + cur.data, end='')
else:
print('|' + cur.data)
cur = cur.next
def push(self, data):
node = Node(data)
if self.is_empty():
self.__head = node
return
cur = self.__head
while cur.next is not None:
cur = cur.next
cur.next = node
def pop(self):
if self.is_empty():
return
cur = self.__head
prev = None
while cur.next is not None:
prev = cur
cur = cur.next
if cur == self.__head:
self.__head = self.__head.next
return
prev.next = cur.next
return cur.data
def length(self):
length = 0
cur = self.__head
while cur is not None:
length += 1
cur = cur.next
return length
def check(self):
if self.is_empty():
return
cur = self.__head
while cur.next is not None:
cur = cur.next
return cur.data定义一个 LinkStack() 类，实例化的时候会创建一个空链表，这就有了一个空的链栈。
下面是链栈的各个方法实现：
is_empty(): 判断链栈是否为空。如果存储数据的链表头指向空(对应布尔值False)，则链栈为空(is_empty为True)，反之。
show(): 展示链栈中的数据，也就是将栈中所有的数据依次打印输出。对存储数据的链表遍历输出即可，为了展示得更形象一点，我在栈底(封闭的一端)打印竖线，表示不能从这里取数据。
push(data): 压栈，也就是将数据添加到栈中。如果将链表的结尾当成栈顶，则压栈就是在链表结尾添加节点。如果将链表的头当做栈顶，则压栈就是在链表头添加节点。
pop(): 出栈，也就是将数据从栈中取出，并返回取出的数据。如果将链表的结尾当成栈顶，则出栈就是删除并返回链表尾节点的数据。如果将链表的开头当做栈顶，则出栈就是删除并返回链表头节点的数据。
length(): 返回链栈的长度。链栈的长度就是存储数据的单向链表的长度，也就是链表中有多少个数据。
check(): 返回链栈栈顶位置的数据。在从链栈中取数据之前，如果要先知道栈顶位置的数据是什么，可以使用此方法。如果将链表的结尾当成栈顶，则返回链表尾节点的数据，如果将链表的头当成栈顶，则返回链表头节点的数据。
ls = LinkStack()
print("is_empty: ", ls.is_empty())
ls.show()
ls.push('A')
ls.push('B')
ls.push('C')
ls.push('D')
ls.push('E')
ls.show()
print(ls.pop())
ls.show()
print("link stack length: ", ls.length())
print("top member is: ", ls.check())运行结果：
is_empty: True
空栈
|A|B|C|D|E
E
|A|B|C|D
link stack length: 4
top member is: D以上就是用 Python 实现的顺序栈及链栈。
