数据表与链表统称为线性表
栈的进出你可以去联想一下杯子倒水,最后一个进来先出:last in first out(LIFO)
栈可以由顺序表或者链表实现,但是有些特殊因为栈的数据结构只能允许在一端进行操作。
顺序表和列表解决存储具体的应用场合我们要关注容器的操作特性上面。
python中List就是顺序表
压栈(入栈)–对应英文push
出栈(叫弹)–对应英文pop
查当前栈顶元素存储的是谁但是你别出栈–对应英文peek
现在只是把它的功能定义出来了,但是我们需要一个容器把数据存进去。
class Stack(object): def push(self,item): pass def pop(self): pass def peek(self): pass def is_empty(self): pass def size(self): passif __name__=='__main__': s=Stack()
一旦构造我们就需要把容器
但是属性我们给设置成私有,因为我们希望外面的人不能去操作容器。因为把容器交给你,你就可以绕过push,pop方法直接对对头队尾进行操作。
对于这个列表你是把它的头部作为开端还是把尾部作为开端都是你自己决定的。这里我们直接选用的是尾部。尾部添加,尾部直接取。为何选择在尾部呢?因为顺序表对于头部的操作是O(n),对于尾部的操作是O(1),如果使用单链表的方式,我们要做i的是在链表的尾部还是链表的头部呢?此时是头部,因为如果头部的话复杂度是O(1),尾部的话是O(n),
完整代码如下:
class Stack(object): def __init__(self): self.__list=[] def push(self,item): self.__list.append(item) #self.__list.insert(0,item) def pop(self): return self.__list.pop() #self.pop(0) def peek(self): if self.__list: return self.__list[-1] else: return None def is_empty(self): return self.__list==[]#这个返回的是bool值 #return self.__list#这个就是真实的翻译了一下,但是与这个自然语言不符 def size(self): return len(self.__list)if __name__=='__main__': s=Stack() s.push(1) s.push(2) s.push(3) s.push(4) print(s.pop()) print(s.pop()) print(s.pop()) print(s.pop())