python学习笔记_第29天（栈+列队）

栈

栈（stack）是一种容器，也称为堆栈。特点在于只允许在容器的一端（称为栈顶top）进行压栈（加入数据push）和出栈（输出数据pop）。没有位置概念，确定了默认访问顺序，按照后进先出（LIFO, Last In First Out）的原理运作。
栈可以用顺序表（list）实现，也可以用链表实现。

栈的操作

栈操作具体实现

class Stack:
'''栈只支持数据从一头进出，先进后出'''def __init__(self):self.__list = []def push(self, item):'''添加一个新的元素item到栈顶'''self.__list.append(item)# 用顺序表存储法构造栈时，头部操作的时间复杂度为O(n)，尾部操作的时间复杂度为O(1)# self.__list.insert(0,item)  # 头部操作更优def pop(self):'''弹出栈顶元素'''return self.__list.pop()# 若用链表存储法构造栈时，则头部操作的时间复杂度更低# return self.__list.pop(0)  # 头部操作更优def peek(self):'''返回栈顶元素'''if self.__list:  # 当列表存在且不为空return self.__list[-1]  # 尾部操作，切片操作返回尾部最后一个元素值else:return Nonedef is_empty(self):'''判断栈是否为空'''return self.__list == []  # 0、空字符串、空列表、空字典、空元祖等逻辑值为Falsedef size(self):'''返回栈的元素个数'''return len(self.__list)

测试

if __name__ == "__main__":'''栈先进后出'''stack = Stack()stack.push("hello")stack.push("world")stack.push("python")print(stack.size())print(stack.peek())print(stack.pop())print(stack.pop())print(stack.pop())

执行结果：
3
python
python
world
hello

队列

队列（queue）允许插入的一端为队尾，允许删除的一端为队头。特点在于只允许在一端进行插入操作（enqueue），另一端进行删除操作（dequeue）。按照先进先出（First In First Out）的原理运作，简称FIFO。
队列不允许在中间部位进行操作！ 假设队列是q=（a1，a2，……，an），那么a1就是队头元素，而an是队尾元素。删除时从a1开始，而插入时总是在队列最后。
队列也可以用顺序表（list）或者链表实现。

列队的操作

列队操作具体实现

class Queue:'''队列一端添加，另一端取数，先进先出'''def __init__(self):self.__list = []# 入队操作和出队操作那个使用更频繁，决定了从列表头部操作还是从列表尾部操作def enqueue(self, item):'''往队列中添加一个item元素'''self.__list.append(item)  # 时间复杂度O(1)# self.__list.insert(0,item)  # 时间复杂度O(n)def dequeue(self):'''从队列头部删除一个元素'''return self.__list.pop(0)  # 时间复杂度O(n)# return self.__list.pop()  # 时间复杂度O(1)def is_empty(self):'''判断一个队列是否为空'''return self.__list == []def size(self):'''返回队列的大小'''return len(self.__list)

测试

if __name__ == "__main__":'''队列先进先出'''queue = Queue()queue.enqueue("hello")queue.enqueue("world")queue.enqueue("python")print(queue.size())print(queue.is_empty())print(queue.dequeue())print(queue.dequeue())print(queue.dequeue())

执行结果：
3
False
hello
world
python

双端队列

双端队列（deque，全名double-ended queue），是一种具有队列和栈的性质的数据结构，可以看做两个栈底部相连的情况。
双端队列中的元素可以从两端弹出，其限定插入和删除操作在表的两端进行。双端队列可以在队列任意一端入队和出队。

双端列队的操作

双端列队操作具体实现

class Deque:'''双端队列'''def __init__(self):self.__list = []# 入队操作和出队操作那个使用更频繁，决定了从列表头部操作还是从列表尾部操作def add_front(self, item):'''从队头加入一个item元素'''self.__list.insert(0, item)  # 时间复杂度O(n)def add_rear(self, item):'''从队尾加入一个item元素'''self.__list.append(item)  # 时间复杂度O(1)def remove_front(self):'''从队头删除一个item元素'''return self.__list.pop(0)  # 时间复杂度O(n)def remove_rear(self):'''从队尾删除一个item元素'''return self.__list.pop()  # 时间复杂度O(1)def is_empty(self):'''判断一个队列是否为空'''return self.__list == []def size(self):'''返回队列的大小'''return len(self.__list)