国务院关于政府网站建设/360优化大师旧版
python-栈的实现
栈(Stack)的定义:只允许在一端进行插入或者删除操作的线性表。
栈顶(Top):线性表允许插入和删除的那一端。
栈底(Bottom):固定的，不允许进行插入和删除的那一端。
空栈：不含任何元素的空表。
这里借用一个百度百科的图片展示入栈和出栈的过程：
栈是后入先出（LIFO，last-in-first-out）的数据结构，假设栈中原始数据为(2,7,1)
该图展示了8和2依次入栈(Push())
以及(2,8,1)依次出栈(Pop())的过程。
栈的基本操作：
IniStack():初始化一个空栈
isempty():判空
isfull():判满
Push():若栈未满，则入栈
Pop():若栈非空，则出栈
GetTop():获取栈顶元素
顺序栈的实现：
# 后进先出
class myStack():def __init__(self,size):self.size=size #栈的大小self.stack=[] #定义一个空栈self.top=-1 #指示栈的存储情况，初始为-1，表示空栈，每入栈一个元素，top增加1，每出栈一个元素，top减少1def push(self, x): # 入栈之前检查栈是否已满if self.isfull():print("stack is full")return Falseelse:self.stack.append(x)self.top = self.top + 1return Truedef pop(self):# 出栈之前检查栈是否为空if self.isempty():print("stack is empty")return Falseelse:self.top = self.top - 1self.stack.pop()return Truedef gettop(self):if self.top!=-1:return self.stack[self.top]def isfull(self):return self.top+1 == self.sizedef isempty(self):return self.top == '-1'def showStack(self):print(self.stack)s=myStack(10)
for i in range(10):s.push(i)
s.showStack()
print(s.gettop())s.push("100")
for i in range(6):s.pop()
s.showStack()输出为：
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
9
stack is full
[0, 1, 2, 3]
需要注意的地方：
1)入栈的时候：元素先入栈,top再增1；出栈时：top先减1，元素后出栈
2)top初值为-1表示空栈，top+1==size表示满栈
共享栈：
利用栈底位置相对不变的特性，可以让两个顺序栈共享一个一维空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸。
两个栈的栈顶指针都指向栈顶元素，top0=-1时0号栈为空，top1=maxSize时1号栈为空，仅当两个栈顶相邻时栈满:top1-top0==1
入栈时，top0先加1再赋值；top1先减1再赋值
定义共享栈：
class myStack():def __init__(self,maxSize):self.stack0=[] self.stack1=[]self.top0=-1self.top1=maxSize
其他方法对照顺序栈即可。
链栈：
采用链式存储结构的栈，不存在栈满溢出的情况，便于节点的插入和删除，通常用单链表实现，并规定所有的操作都是在表头进行的。
下图的链栈没有头结点，Lhead指向栈顶元素。
