经典数据结构队列的研究和实现宋钰（山西广播电视大学，太原030027）摘要院介绍了数据结构的基本概念和常见的数据结构如队列、堆栈，在人们的日常生活中，队列是非常有用的数据结构。通过具体的实例，重点讲解了队列的原理及其详细的实现过程，实现了基本的队列和扩展的双端队列。关键词院数据结构；线性逻辑结构；队列；双端队列1数据结构数据结构是计算机组织尧存储数据的一种方式遥数2.2队列抽象数据结构一般来说队列由下面的数据结构和操作定义院据结构指数据元素间存在的一种或多种特定关系的集合遥通常记为渊D,R冤遥其中D是数据结构中所有数据元素的集合袁R是D中元素之间的相互关系的集合遥数据结构通常有逻辑结构和物理结构遥数据的逻辑结构指数据元素之间的逻辑关系袁通常指数据元素之间的前后关系遥逻辑结构包括院图形结构尧树形结构尧线性结构尧集合遥数据的物理结构是指数据存储到计算机时的内部存储结构袁通常有院数组尧链表等遥重点研究数据的线性逻辑结构遥数据的线性结构通常有堆栈和队列遥数据结构院一般基于数组或链表袁在Python中也可以基于list操作院渊1冤Queue()创建一个空队列遥渊队列会改变大小冤遥渊2冤enQueue(item)添加一个元素到队尾袁返回none渊3冤deQueue()从队头移除一个元素袁返回被移除渊4冤isEmpty()测试队列是否为空袁为空返回True遥渊5冤size()返回队列的大小渊队列中元素个数冤遥表1队列操作表QueueOperationq.isEmpty()q.enQueue(11)q.enQueue('fox')q.enQueue(False)q.size()q.isEmpty()q.enQueue(5.6)q.deQueue()q.deQueue()q.size()QueueContents[][11]['fox',11][False,'fox',11][False,'fox',11][False,'fox',11][5.6,False,'fox',11][5.6,False,'fox'][5.6,False][5.6,False]11'fox'23FalseReturnValueTrue的队头元素渊队列会改变大小冤遥2队列队列是一种特殊的线性逻辑结构袁它只允许在后端渊rear冤进行插入操作袁而在前端渊front冤进行删除操作遥进行插入操作的端称为队尾袁进行删除操作的端称为队个元素称为出队遥队列中没有元素时袁称为空队列遥总结院队列特点院先进先出渊FIFO冤袁入队在队尾袁出队在队头遥队列的常见操作院入队尧出队尧判断队列为空尧取队列大小遥2.1队列示意图rear8.4Trueitems\"dog\"4front头遥在队列中插入一个元素称为入队袁从队列中删除一2.3队列实现图1队列示意图classMyQueue(object):def_init_(self):self.elements=[]defis_empty(self):142019.12returnself.elements==[]defen_queue(self,element):self.elements.insert(0,element)defde_queue(self):returnself.elements.pop()defsize(self):returnlen(self.elements)mq=MyQueue()mq.en_queue('dog')mq.is_empty()mq.size()mq.de_queue()print(mq.size())3双端队列双端队列是指允许两端都可以进行入队和出队操作的队列袁其元素的逻辑结构仍是线性结构遥将队列的两端分别称为前端和后端袁两端都可以入队和出队遥addtorearrearfrontaddtofront\"dog\"4\"cat\"Trueremovefromrearitemsremovefromfront图2双端队列示意图3.1一般来说队列由下面的数据结构和操作定义队列抽象数据结构院数据结构院一般基于数组或链表袁在Python中也可以基于list操作院渊1冤渊2冤Deque()addFront创建一个空双端队列(item)添加一个元素到队头遥none渊双端队列会改变大小冤遥袁返回none渊3冤渊双端队列会改变大小addRear(item)添加一个元素到队尾冤遥袁返回移除的队头元素渊4冤removeFront()渊双端队列会改变大小从队头移除一个元素冤遥袁返回被移除的队头元素渊5冤removeRear()渊双端队列会改变大小从队头移除一个元素冤遥袁返回被True遥渊6冤isEmpty()测试双端队列是否为空袁为空返回个数渊7冤冤遥size()返回双端队列的大小渊双端队列中元素表2双端队列操作DequeOperationDequeContentsReturnValued.isEmpty()[]Trued.addRear(4)[4]d.addRear('dog')['dog',4,]d.addFront('cat')['dog',4,'cat']d.addFront(True)['dog',4,'cat',True]d.size()['dog',4,'cat',True]4d.isEmpty()['dog',4,'cat',True]Falsed.addRear(8.4)[8.4,'dog',4,'cat',True]d.removeRear()['dog',4,'cat',True]8.4d.removeFront()['dog',4,'cat']True3.2class双端队列实现MyDeque(object):def_init_(self):self.elements=[]defis_empty(self):returnself.elements==[]definsert_front(self,element):self.elements.append(element)definsert_rear(self,element):self.elements.insert(0,element)defdelete_front(self):returnself.elements.pop()defdelete_rear(self):returnself.elements.pop(0)defsize(self):returnlen(self.elements)dq=MyDeque()dq.insert_front('tomcat')print(dq.size())print(dq.is_empty())dq.insert_rear(55)print(dq.delete_front())print(dq.delete_rear())4结语介绍数据结构的概念和常见的数据结构分类袁并重点研究了线性数据结构院队列和双端队列的原理尧实现过程袁并实现了队列和双端队列袁队列是非常有用的数据结构袁在人们的日常生活中有大量的队列事例如银行叫号尧餐厅排队等袁队列可以有效地应用于生活中的方方面面遥2019.1215
