栈：又名堆栈，是一种运算受限的线性表，仅允许在线性表的一端进行插入(push)和移除(pop)运算，可以进行运算的一端称为栈顶，另一端称为栈底。遵循先进后出原理。先进入的数据被压入栈底，后放入的数据置于栈顶。桟的插入数据、删除数据操作都是实现在栈顶当中：读取数据的时候从栈顶开始弹出数据（最后一个插入的数据被第一个读出来）。栈具有记忆作用，对栈的插入与删除操作中，不需要改变栈底指针。向栈中插入新元素称为进栈、压栈、入栈（PUSH），即把新元素放入栈顶元素的上面，使之成为新的栈顶元素。从栈中删除元素成为出栈、退栈（POP），即将栈顶元素删除，让其相邻的元素成为新的栈顶元素。允许进行插入和移除操作的一端称为栈顶(top)，另一端为栈底(bottom)；栈底固定，而栈顶浮动；栈中元素个数为零时称为空栈，栈也称为后进先出表。举个栗子：一群人挤电梯时，先进电梯的人想要出来，必须让后进电梯的人出去之后，先进电梯的人才能出去。
堆栈常用一维数组或链表来实现。包括推入（压栈，push）和弹出（弹栈，pop）：
桟的应用场景
### 列表实现桟 class Stack(object): def __init__(self): self._li = list() def peek(self): """获取栈顶元素""" if not self._li: return None else: return self._li[-1] def push(self, item): """推送新元素 """ self._li.append(item) return self._li[-1] def pop(self): """ 弹出栈顶元素""" if not self._li: return None else: return self._li.pop() ### 链表实现桟 class Node(object): def __init__(self, elem): self.elem = elem # 保存着结点对象的真正元素 self.next = None # 保存着当前元素的下一指向 class Stack(object): def __init__(self): self._top = None # 栈顶元素的指向 def peek(self): """返回栈顶元素""" if not self._top: # 如果栈顶元素的指向为空,代表是个空桟 return None else: # self._top相当于是一个结点对象; self._top.elem取出结点对象的元素 return self._top.elem # 若不是空桟,就返回当前栈顶所指向的元素 def push(self, item): """推送新元素""" node = Node(item) # 创建新结点对象 node.next = self._top # 将新结点对象下一指向原先的栈顶元素，新结点对象变为栈顶元素 self._top = node # 将栈顶元素指向新创建的结点对象 return node.elem # 返回新结点对象的elem属性中保存的元素 def pop(self): """弹出栈顶元素""" if not self._top: return None else: node = self._top.elem # 获取栈顶元素 self._top = self._top.next # 改变新栈顶元素的指向； 新栈顶元素=原栈顶元素的下一指向 return node # 弹出原栈顶元素 In [66]: s = Stack() In [67]: s.push(1) Out[67]: 1 In [68]: s.push(2) Out[68]: 2 In [69]: s.pop() Out[69]: 2 In [70]: s.pop() Out[70]: 1 In [72]: print(s.peek()) None
基本概念
队列：是一种特殊的线性表，特殊之处在于它只允许在线性表的前端（front）进行删除操作，在线性表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。遵循先进先出（FIFO, First-In-First-Out）原则。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队；当队列中没有元素时，称为空队列。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）线性表。在具体应用中通常用链表或者数组来实现。举个栗子：现有一只队伍需要过马路，总共有22人，你是最后一个，你为了能够顺利过马路必须等待前面所有人过去之后，你才能过马路，排在第一位的人最先过马路，然后的第二个、第三个 ... 对应着：最先插入线性表的元素，最先被删除/读取。
订单系统：用户下单后，在订单系统中将调用库存系统接口的操作放入到消息队列，订单系统中不再阻塞等待库存系统的返回结果。并将订单下单成功返回给用户。
库存系统：在消息队列中订阅下单的消息，采用拉/推的方式，获取下单信息，库存系统根据下单信息，进行库存操作。
假如：在下单时库存系统不能正常使用。也不影响正常下单，因为下单后，订单系统写入消息队列就不再关心其他的后续操作了。实现订单系统与库存系统的应用解耦。
秒杀业务根据消息队列中的请求信息，再做后续处理。
### 列表实现队列 class Queues(object): def __init__(self): self._li = list() def is_empty(self): """队列判空""" if len(self._li) == 0: return True else: return False def length(self): """返回队列长度""" return len(self._li) def enqueue(self, item): """队尾插入元素""" self._li.append(item) return self._li[-1] def dequeue(self): """队头删除元素""" if not self.is_empty(): return None else: return self._li.pop(0) ### 链表实现队列
原文：https://www.cnblogs.com/hsmwlyl/p/10612672.html