自建网站代理服务器,电子商务有哪些职业,粉红色的网站首页,网站备案登录密码找回本节讲解的队列与栈#xff0c;如果你对之前的线性和链式结构顺利掌握了#xff0c;那么下边的队列和栈就小菜一碟了。因为我们会用前两节讲到的东西来实现队列和栈。 之所以放到一起讲是因为这两个东西很类似#xff0c;队列是先进先出结构(FIFO, first in first out)… 本节讲解的队列与栈如果你对之前的线性和链式结构顺利掌握了那么下边的队列和栈就小菜一碟了。因为我们会用前两节讲到的东西来实现队列和栈。 之所以放到一起讲是因为这两个东西很类似队列是先进先出结构(FIFO, first in first out) 栈是后进先出结构(LIFO, last in first out)。 一队列 队列Queue是计算机科学中一种基础的数据结构它遵循先进先出First In First Out, FIFO的原则即最早进入队列的元素也将是最先离开队列的元素。这个概念类似于现实生活中的排队场景比如在超市结账先到达收银台的顾客会先完成结账离开。 1.线式队列
线式队列就是线性表队列性质组成的数据结构
代码实现
class Array():def __init__(self,size):self.__size sizeself.__item [None]*sizeself.__length 0def __setitem__(self,key,value):self.__item[key] valueself.__length 1def __getitem__(self, index):return self.__item[index]def __len__(self):return self.__lengthdef __iter__(self):for value in self.__item:yield valueclass Linear_Queue():def __init__(self,size4):self.size sizeself.items Array(size)self.head 0self.end 0def push(self,value):self.items[self.head % self.size] valueself.head 1def pop(self):temp self.items[self.end % self.size]self.end 1return tempif __name__ __main__:lq Linear_Queue()lq.push(11)lq.push(12)lq.push(13)lq.push(14)print(lq.pop())print(lq.pop())print(lq.pop())print(lq.pop())2.链式队列
链式队列就是链表队列性质组成的数据结构
代码实现
class Node():def __init__(self,valueNone,prevNone,nextNone):self.value valueself.next nextself.prev prevdef __str__(self):return Node:{}.format(self.value)class DoubleLinkedList():def __init__(self):self.size 0self.root Node()self.end Nonedef append(self,value):node Node(valuevalue)#无节点if not self.end:self.root.next node # root节点指向新节点node.prev self.root#新节点指向根节点self.end node#末节点指针指向新节点#有节点else:self.end.next node#末节点指向新节点node.prev self.end # 新节点指向末节点self.end node#末节点移动到新节点self.size 1def append_first(self,value):node Node(valuevalue)#无节点if not self.end:self.root.next node # root节点指向新节点node.prev self.root # 新节点指向根节点self.end node # 末节点指针指向新节点else:node.prev self.root#新节点指向根节点temp self.root.next#保存原来的第一个节点self.root.next node#将新节点替换为第一个节点node.next temp#让新节点的下一个节点为原来的第一个节点temp.prev node#将原来的第一个节点的上一个节点设置为新节点self.size 1def __iter__(self):current self.root.nextif current:while current is not self.end:yield currentcurrent current.nextreturn currentelse:print(LinkedList is empty)#逆向迭代def inverse_iter(self):current self.endif current:while current is not self.root:yield currentcurrent current.prevelse:print(LinkedList is empty)def find(self,value):passdef find_count(self,value):passdef remove_first(self):if self.end:temp self.root.nextself.root.next temp.nextif temp.next:temp.next.prev self.rootreturn tempdef remove_all(self,value):passclass Queue():def __init__(self,size4):self.items DoubleLinkedList()self.size sizeself.length 0def push(self,value):self.items.append(value)self.size 1def pop(self):if self.length 0:returnself.length - 1return self.items.remove_first()def empty(self):pass 二栈
1.双端队列
from collections import deque# 初始化队列
queue deque()# 入队操作
queue.append(1)
queue.append(2)
queue.append(3)print(初始队列:, queue)# 出队操作
print(出队元素:, queue.popleft()) # 输出并移除队首元素
print(出队后队列:, queue)# 再次入队
queue.append(4)# 查看队列状态
print(当前队列:, queue)
print(队列长度:, len(queue))
根据双端队列的性质可以模仿出栈的效果先进后出其实就是
from collections import deque
d deque([1,2,3,4])print(d.pop())print(d.pop())print(d.pop())print(d.pop())输出结果 4 3 2 1
这就类似栈的性质但是这里只是用双端了队列模拟的。
