注：本文如涉及到代码，均经过Python 3.7实际运行检验，保证其严谨性。
本文阅读时间约为5分钟。
什么是线性结构
什么是线性结构Linear Structure？
线性结构是一种有序数据项的集合，其中每个数据项都有唯一的前驱和后继，除了第一个没有前驱，最后一个没有后继。新的数据加入到数据集里面时，只会加入到原有某个数据项之前或之后。
具有以上这种性质的数据集，称为线性结构。
栈Stack、队列Queue、双端队列Deque和列表List都是线性结构，且是最简单但功能强大的线性结构。
栈抽象数据类型及Python实现
什么是栈stack？
栈是一种有次序的数据项集合。在栈中，数据项的加入和移除都仅发生在同一端。
这一端叫栈“顶top”，另一端叫栈“底base”。日常生活中叠加的盘子，书堆都是“栈”。
栈的特性
距离栈底越近的数据项，留在栈中的时间越长，而最新加入栈的数据会被最先移除。这种次序被称为“后进先出”（LIFO，即Last in First out）。因为栈的数据只会从栈顶开始操作。
这种反转次序的特性，如浏览器或Word里的Undo按钮。
栈Stack的Python实现
用Python来实现ADT Stack
Python有列表和字典等常用数据集。这里采用列表来实现。
Stack的两端对应list设置，可以采用list的任意一端(index=0或-1)来设置为栈顶。
这里采用list的末端，即index=-1处作为栈顶，这样，pop()等同于列表的pop，push就等同于列表的append。
栈要用Python中的类进行定义，其具体代码如下：
#stack.py
class Stack:
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def push(self, item):
self.items.append(item)
def pop(self):
return self.items.pop()
def peek(self):
return self.items[len(self.items)-1]
def size(self):
return len(self.items)
定义过后，可以把上述代码形成一个名为stack.py的文件，放在和写的程序文件.py同目录下；也可以直接把上述代码贴在写的程序的篇头。为方便操作和说明，本系列取后者。
栈Stack的操作
- Stack()：创建一个空栈，不包含任何数据项。
- .push(item)：将item加入栈顶，无返回值。
- .pop()：将栈顶数据项移除，并返回被移除的项，此时栈被修改。
- .peek()：“窥视”栈顶数据项，返回栈顶的数据项，但不移除，栈不被修改。即只查不改。
- .isEmpty()：返回栈是否为空栈。
- .size()：返回栈中有多少个数据项。
- .items：查看栈中所有元素，返回列表类型。
测试代码如下：
class Stack:
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def push(self, item):
self.items.append(item)
def pop(self):
return self.items.pop()
def peek(self):
return self.items[len(self.items)-1]
def size(self):
return len(self.items)
s = Stack()
s.push(4)
s.push('dog')
s.peek()
Out[7]: 'dog'
s.push(True)
s.size()
Out[9]: 3
s.isEmpty()
Out[10]: False
s.push(8.4)
s.pop()
Out[12]: 8.4
s.pop()
Out[13]: True
s.size()
Out[14]: 2
s.items #查看栈的所有元素，且返回类型为列表。
Out[15]: [4, 'dog']
To be continued.
