本文主要是介绍python学习笔记_第29天（栈+列队），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
文章目录
- 栈
- 栈的操作
- 栈操作具体实现
- 队列
- 列队的操作
- 列队操作具体实现
- 双端队列
- 双端列队的操作
- 双端列队操作具体实现
顺序表（list）与链表解析存储模式，栈、队列、树是具体应用场景。
队列一端添加，另一端取数，先进先出
栈
栈（stack）是一种容器，也称为堆栈。特点在于只允许在容器的一端（称为栈顶top）进行压栈（加入数据push）和出栈（输出数据pop）。没有位置概念，确定了默认访问顺序，按照后进先出（LIFO, Last In First Out）的原理运作。
栈可以用顺序表（list）实现，也可以用链表实现。
栈的操作
| 操作 | 说明 |
|---|---|
| Stack() | 创建一个新的空栈 |
| push(item) | 添加一个新的元素item到栈顶 |
| pop() | 弹出栈顶元素 |
| peek() | 返回栈顶元素 |
| is_empty() | 判断栈是否为空 |
| size() | 返回栈的元素个数 |
栈操作具体实现
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）或者链表实现。
列队的操作
| 操作 | 说明 |
|---|---|
| Queue() | 创建一个空的队列 |
| enqueue(item) | 往队列尾添加一个item元素 |
| dequeue() | 从队列头部删除一个元素 |
| is_empty() | 判断一个队列是否为空 |
| size() | 返回队列的大小 |
列队操作具体实现
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），是一种具有队列和栈的性质的数据结构，可以看做两个栈底部相连的情况。
双端队列中的元素可以从两端弹出，其限定插入和删除操作在表的两端进行。双端队列可以在队列任意一端入队和出队。
双端列队的操作
| 操作 | 说明 |
|---|---|
| Deque() | 创建一个空的双端队列 |
| add_front(item) | 从队头加入一个item元素 |
| add_rear(item) | 从队尾加入一个item元素 |
| remove_front() | 从队头删除一个item元素 |
| remove_rear() | 从队尾删除一个item元素 |
| is_empty() | 判断双端队列是否为空 |
| size() | 返回队列的大小 |
双端列队操作具体实现
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)
这篇关于python学习笔记_第29天（栈+列队）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
