一：栈

先进后出

1.栈的应用：

• 算法中的辅助存储结构，临时保存信息供后面操作中使用。函数调用

• 颠倒数组的元素顺序。

• 括号匹配问题

• 递归

• 表达式求值 3+5*4-9 （两个栈 一个存符号一个存数字）

2.栈的python实现

class Stack(object):def __init__(self):self.__list = []
​def push(self,item):"""添加一个元素item到栈顶"""self.__list.append(item)
​def pop(self):"""弹出栈顶元素"""return self.__list.pop()
​def peek(self):"""返回栈顶元素"""if self.__list:return self.__list[-1]else:return None
​def is_empty(self):"""判空"""return self.__list == []# return not 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())

3.栈与递归：

递归一般需要调用栈。

阶乘函数：n！

def fact(n):if n == 0 :return 1else:return  n*fact(n-1)

任何一个递归函数都可以引入一个栈保存中间结果改为非递归函数：

def norec_fact(n):res = 1st = SStack()while n > 0:st.push(n)n -= 1while not st.is_empty():res *= st.pop()return res

二：队列

先进先出

入队O(1), 出队用pop(0)所有元素前移，所以是O(N).

1.队列的应用：

• 打印机管理系统。

• 万维网服务器处理请求

• 消息队列：不同处理器或处理进程（线程）之间的通信可能需要消息队列作为缓冲，称为异步通信。分布式消息队列，如 kafka 也是一种队列。

• 1.阻塞队列 1）在队列的基础上增加阻塞操作，就成了阻塞队列。 2）阻塞队列就是在队列为空的时候，从队头取数据会被阻塞，因为此时还没有数据可取，直到队列中有了数据才能返回；如果队列已经满了，那么插入数据的操作就会被阻塞，直到队列中有空闲位置后再插入数据，然后在返回。 3）从上面的定义可以看出这就是一个“生产者-消费者模型”。这种基于阻塞队列实现的“生产者-消费者模型”可以有效地协调生产和消费的速度。当“生产者”生产数据的速度过快，“消费者”来不及消费时，存储数据的队列很快就会满了，这时生产者就阻塞等待，直到“消费者”消费了数据，“生产者”才会被唤醒继续生产。不仅如此，基于阻塞队列，我们还可以通过协调“生产者”和“消费者”的个数，来提高数据处理效率，比如配置几个消费者，来应对一个生产者。

• 2.并发队列 1）在多线程的情况下，会有多个线程同时操作队列，这时就会存在线程安全问题。能够有效解决线程安全问题的队列就称为并发队列。 2）并发队列简单的实现就是在enqueue()、dequeue()方法上加锁，但是锁粒度大并发度会比较低，同一时刻仅允许一个存或取操作。 3）实际上，基于数组的循环队列利用CAS原子操作，可以实现非常高效的并发队列。这也是循环队列比链式队列应用更加广泛的原因。

• 3.线程池资源枯竭的处理 在资源有限的场景，当没有空闲资源时，基本上都可以通过“队列”这种数据结构来实现请求排队。

2.队列的python实现

class Queue(object):"""队列"""def __init__(self):self.__list = []
​def enqueue(self,item): # 入队"""往队列中添加一个item元素"""self.__list.append(item)
​def dequeue(self): # 出队"""从队列中删除一个元素"""return self.__list.pop(0)
​def is_empty(self):"""判断一个队列是否为空"""return self.__list == []
​def size(self):"""返回队列的大小"""return len(self.__list)
​
if __name__ == "__main__":s = Queue()s.enqueue(1)s.enqueue(2)s.enqueue(3)s.enqueue(4)print(s.dequeue())print(s.dequeue())print(s.dequeue())
​

3. 双端队列的python实现

class DoubleEndQueue(object):"""双端队列"""
​def __init__(self):self.__list = []
​def add_front(self, item):self.__list.insert(0,item)
​def add_rear(self,item):self.__list.append(item)
​def pop_front(self):  # 出队"""从队首中删除一个元素"""return self.__list.pop(0)
​def pop_rear(self):  # 出队"""从队尾中删除一个元素"""return self.__list.pop()
​def is_empty(self):"""判断一个队列是否为空"""return self.__list == []
​def size(self):"""返回队列的大小"""return len(self.__list)
​
​
if __name__ == "__main__":s = DoubleEndQueue()s.add_front(1)s.add_rear(2)print(s.pop_front())print(s.pop_rear())
​

Leetcode 622 数组实现循环队列：

class MyCircularQueue(object):
​def __init__(self, k):self.queue = [0]*kself.headIndex = 0self.count = 0self.capacity = k​def enQueue(self, value):if self.count == self.capacity:return False# 找到队列中尾节点对应count的位置self.queue[(self.headIndex + self.count) % self.capacity] = valueself.count += 1return True
​def deQueue(self):if self.count == 0:return False# 保证headIndex第一次越界时的下标调整到count范围内self.headIndex = (self.headIndex + 1) % self.capacityself.count -= 1return True​def Front(self):if self.count == 0:return -1return self.queue[self.headIndex]​def Rear(self):if self.count == 0:return -1return self.queue[(self.headIndex + self.count - 1) % self.capacity] #尾节点减1​def isEmpty(self):return self.count == 0​def isFull(self):return self.count == self.capacity

复杂度分析

时间复杂度 : O(1)。该数据结构中，所有方法都具有恒定的时间复杂度。

空间复杂度: O(N)，其中 N 是队列的预分配容量。循环队列的整个生命周期中，都持有该预分配的空间

加锁实现并发安全：

from threading import Lock
​
class MyCircularQueue:
​def __init__(self, k: int):"""Initialize your data structure here. Set the size of the queue to be k."""self.queue = [0]*kself.headIndex = 0self.count = 0self.capacity = k# the additional attribute to protect the access of our queueself.queueLock = Lock()
​def enQueue(self, value: int) -> bool:# automatically acquire the lock when entering the blockwith self.queueLock:if self.count == self.capacity:return Falseself.queue[(self.headIndex + self.count) % self.capacity] = valueself.count += 1# automatically release the lock when leaving the blockreturn True

解法二：

1、定义循环变量 front 和 rear 。

front：指向队列头部第 1 个有效数据的位置； rear：指向队列尾部（即最后 1 个有效数据）的下一个位置，即下一个从队尾入队元素的位置。

（说明：这个定义是依据“动态数组”的定义模仿而来。）

2、为了避免“队列为空”和“队列为满”的判别条件冲突，我们有意浪费了一个位置。

浪费一个位置是指：循环数组中任何时刻一定至少有一个位置不存放有效元素。

判别队列为空的条件是：front == rear;

判别队列为满的条件是：(rear + 1) % capacity == front;。可以这样理解，当 rear 循环到数组的前面，要从后面追上 front，还差一格的时候，判定队列为满。

class MyCircularQueue:
​def __init__(self, k: int):self.front = 0self.rear = 0self.capacity = k + 1self.arr = [0 for _ in range(self.capacity)]
​def enQueue(self, value: int) -> bool:if self.isFull():return Falseself.arr[self.rear] = valueself.rear = (self.rear + 1) % self.capacityreturn True
​def deQueue(self) -> bool:if self.isEmpty():return False
​self.front = (self.front + 1) % self.capacityreturn True
​def Front(self) -> int:if self.isEmpty():return -1return self.arr[self.front]
​def Rear(self) -> int:if self.isEmpty():return -1return self.arr[(self.rear - 1 ) % self.capacity]
​def isEmpty(self) -> bool:return self.front == self.rear
​def isFull(self) -> bool:return (self.rear + 1) % self.capacity == self.front
​

python提供的库deque（双端）支持元素两端的插入和删除，包括append, appendleft, pop, popleft。queue

from collections import dequedq = deque([1,2,3,4,5])
​
print(1 in q) 
res = dq.pop() 
print(res)
res = dq.popleft()
print(res)结果：  51​
from queue import Queue#如果maxsize设置为小于0或者不设置，队列为无限长
que = Queue(maxsize=2)#进队列
que.put(1)#出队列
result = que.get()