5.栈Stack

目录:
1.栈的定义
2.栈的图解
3.栈定义操作
4.栈的实现

1. 栈的定义

1.一种有次序的数据项集合,在栈中,数据项的加入和移除都仅发生在同一端
2.距离栈底越近的数据项,留在栈中的时间就越长
3.这种次序被称为"后进先出LIFO,Last in First out",这是一种基于数据项保存时间的次序,时间越短的离栈顶越近,而时间越长的离栈底越近

2. 栈的图解

栈.jpg

3. "栈"定义的操作

Stack(): 创建一个空栈,不包含任何数据项
push(item): 将item加入栈顶,无返回值
pop(): 将栈顶数据项移除,并返回,栈被修改
peek(): 获取栈顶数据,并返回该数据,栈不被修改
isEmpty(): 返回栈是否为空栈
size(): 返回栈中有多少个数据项

4. 栈的具体实现

1.Stack为一个数据集,故选用Python原生的数据集List实现
2.可以将List的任意一端(index=0或者-1)设置为栈顶

4.1 选用List末端(index = -1)作为栈顶

模型1.jpg

class Stack:
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []

    def push(self,item):
        self.items.append(item)

    def pop(self):
        self.items.pop()

    def peek(self):
        return self.items[len(self.items)-1]

    def size(self):
        return len(self.items)

测试:
s = Stack()
print(1,s.isEmpty())
s.push('stone')
s.push('abc')
print(2,s.peek())
print(3,s.size())
print(4,s.isEmpty())
s.pop()
print(5,s.size())
s.pop()
print(6,s.size())
print(7,s.isEmpty())

运行结果:
1 True
2 abc
3 2
4 False
5 1
6 0
7 True

4.2 选用List初始端(index = 0)作为栈顶

模型2.jpg

class Stack:
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []

    def push(self,item):
        self.items.insert(0,item)

    def pop(self):
        self.items.pop(0)

    def peek(self):
        return self.items[0]

    def size(self):
        return len(self.items)

测试:
s = Stack()
print(1,s.isEmpty())
s.push('stone')
s.push('abc')
print(2,s.peek())
print(3,s.size())
print(4,s.isEmpty())
s.pop()
print(5,s.size())
s.pop()
print(6,s.size())
print(7,s.isEmpty())

运行结果:
1 True
2 abc
3 2
4 False
5 1
6 0
7 True

4.3 两种方式比较

不同的实现方式保持了ADT接口的稳定性,但性能有所不同,栈顶首端的版本,其push/pop的复杂度为O(n),而栈顶尾端的实现方式,其push/pop的复杂度为O(1)