Python实现双端队列数据结构及其基本方法

队列是一种特殊的线性表,是一种先进先出(FIFO)的数据结构。它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作。进行插入操作的端称为队尾,进行删除操作的端称为队头,队列中没有元素时,称为空队列。

队列可由线性表来实现,包括列表和链表都可实现队列,不过在安全性上来说链表比较安全,但是增加额外的内存开销,一般考虑列表来实现队列。

查看Python队列库queue提供的队列源码如下:

Queue提供了一些基本方法:task_done、join、qsize、empty、full、put、get、put_nowait、get_nowait,但是他的实现依旧是通过操作内部的私有方法,而这些私有方法是队列的本质。

包括最后的初始化创建一个列表、获取列表长度返回队列大小、以及对列表进行元素操作等,这一切本质上都是对liest操作。

什么是双端队列?双端队列是在普通队列的基础上,既可以在前端弹出元素也可以在前端插入元素,既可以在后端插入元素也可以在后端弹出元素,下面来实现这一基本模型。

双端队列分类:

输出受限的双端队列:允许在一端进行插入和删除,但在另一端只允许插入的双端队列称为输出受限的双端队列。

输入受限的双端队列:允许在一端进行插入和删除,但在另一端只允许删除的双端队列称为输入受限的双端队列,而如果限定双端队列从某个端点插入的元素只能从该端点删除,则该双端队列就蜕变为两个栈底相邻接的栈了。

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20190409A0NAYD00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励