document.write('栈的实现有两种方法，分别为采用数组来实现和采用链表来实现。下面分别详细介绍这两种方法。
方法一：数组实现
在采用数组来实现栈的时候，栈空间是一段连续的空间。实现思路如下图所示。
从上图中可以看出，可以把数组的首元素当做栈底，同时记录栈中元素的个数size，假设数组首地址为
arr，从上图可以看出，压栈的操作其实是把待压栈的元素放到数组arr[size]中，然后执行size+操作；同
理，弹栈操作其实是取数组arr[size-1]元素，然后执行size-操作。根据这个原理可以非常容易实现栈，示例
代码如下：
class MyStack:
# 模拟栈
def __init__(self):
self.items=[]
#撑判断栈是否为空
def isEmpty(self):
return len(self.items)==0
# 返回栈的大小
def size(self):
return len(self.items)
#返回栈顶元素
def top(self):
if not self.isEmpty():
return elf.items[len(self.items)-1]
else:
return None
#弹栈
def pop(self):
if len(self.items)＞0:
return self.items.pop()
else:
print "栈已经为空"
return None
#压栈
def push(self,item):
self.items.append(item)
if __name__=="__main__":
s=MyStack()
s.push(4)
print "栈顶元素为:"+str(s.top())
print "栈大小为:"+str(s.size())
s.pop()
prmt "弹栈成功"
s.pop()
方法二：链表实现
在创建链表的时候经常采用一种从头结点插入新结点的方法，可以采用这种方法来实现栈，最好使用带头
结点的链表，这样可以保证对每个结点的操作都是相同的，实现思路如下图所示。
在上图中，在进行压栈操作的时候，首先需要创建新的结点，把待压栈的元素放到新结点的数据域中，然
后只需要(1)和(2)两步就实现了压栈操作(把新结点加到了链表首部)。同理，在弹栈的时候，只需要进行(3)
的操作就可以删除链表的第一个元素，从而实现弹栈操作。实现代码如下：
class LNode:
def __new__(self,x):
self.data=x
self.next=None
class MyStack:
def __init__(self):
#pHead=LNode()
self.data=None
self.nexFNone
#判断stack是否为空,如果为空返回true,否则返回false
def empty(self):
if self.next==None:
return True
else:
return False
#获取栈中元素的个数
def size(self):
size=0
p=self.next
while p!=None:
p=p.next
size+=1
return size
#入栈: 把e放到栈顶
def push(self,e):
p=LNode
p.data=e
p.next=self.next
self.next=p
#出栈,同时返回栈顶元素
def pop(self):
tmp=self.next
if tmp!=None:
self.next=tmp.next
return tmp.data
print "栈已经为空"
return None
#取得栈顶元素
def top(self):
if self.next!=None:
return self.next.data
print "栈已经为空"
return None
if __name__=="__main__":
stack=MyStack()
stack.push(1)
print "栈顶元素为:"+str(stack.top())
print "栈大小为:"+str(stack.size())
stack.pop()
print "弹栈成功"
stack.pop()
程序的运行结果为：
栈顶元素为：1
栈大小为：1
弹栈成功
栈已经为空
两种方法的对比：
采用数组实现栈的优点是：一个元素值占用一个存储空间；它的缺点为：如果初始化申请的存储空间太
大，会造成空间的浪费，如果申请的存储空间太小，后期会经常需要扩充存储空间，扩充存储空间是个费时
的操作，这样会造成性能的下降。
采用链表实现栈的优点是：使用灵活方便，只有在需要的时候才会申请空间。它的缺点为：除了要存储元
素外，还需要额外的存储空间存储指针信息。
算法性能分析：
这两种方法压栈与弹栈的时间复杂度都为O(1)。
');
![\"360截图20190815222450785.jpg\"](\"http://www.alatiku.com/d/file/shiti/0e37f73eefc08b3898b7802a80ea0be0.jpg\")
![\"360截图20190815222519801.jpg\"](\"http://www.alatiku.com/d/file/shiti/875a63d29beb5d5f54b205a6937604ad.jpg\")