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减少1
def push(self, x): # 入栈之前检查栈是否已满
if self.isfull():
print("stack is full")
return False
else:
self.stack.append(x)
self.top = self.top + 1
return True
def pop(self):# 出栈之前检查栈是否为空
if self.isempty():
print("stack is empty")
return False
else:
self.top = self.top - 1
self.stack.pop()
return True
def gettop(self):
if self.top!=-1:
return self.stack[self.top]
def isfull(self):
return self.top+1 == self.size
def 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()
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
输出为:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
9
stack is full
[0, 1, 2, 3]
- 1
- 2
- 3
- 4
需要注意的地方:
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=-1
self.top1=maxSize
- 1
- 2
- 3
- 4
- 5
- 6
其他方法对照顺序栈即可。
链栈:
采用链式存储结构的栈,不存在栈满溢出的情况,便于节点的插入和删除,通常用单链表实现,并规定所有的操作都是在表头进行的。
下图的链栈没有头结点,Lhead指向栈顶元素。