一、双端队列的特点：
可以对两端进行操作：队尾入队，队首出队；队尾出队，队首入队；
二、双端队列要实现的操作：
三、代码块（链表实现）
class Node():
def __init__(self,data,_next=None):
self.data=data #数据域
self.next=_next #指针域
class Deque():
def __init__(self):
self.head=None #对头
self.rear=None #队尾
self._length=0 #队列的长度
def is_empty(self):
return self._length==0
def length(self):
return self._length
def items(self):
cur=self.head
while cur:
print(cur.data)
cur=cur.next
print()
def push(self,item):
#队尾添加一个元素item
#队列为空
node=Node(item)
if self.is_empty():
self.head=node
self.rear=node
# 队列不为空
else:
self.rear.next=node
self.rear=node
self._length+=1
def push_left(self,item):
#再队首添加一个节点
node=Node(item)
if self.is_empty():
self.head=node
self.rear=node
else:
node.next=self.head
self.head=node
self._length+=1
def pop(self):
#弹出队首元素
if self.is_empty():
raise ValueError('双端队列为空')
value=self.head.data
self.head=self.head.next
self._length-=1
if self._length==0:
self.rear=None
return value
def pop_right(self):
#弹出队尾元素
if self.is_empty():
raise ValueError('双端队列为空')
if self.length()==1:
return self.pop()
cur=self.head
value=self.rear.data
while cur.next!=self.rear:
cur=cur.next
self.rear=cur
cur.next=None
self._length-=1
return value
def peek(self):
if self.is_empty():
raise ValueError('双端队列为空')
return self.head.data
if __name__ == '__main__':
deque = Deque()
deque.push(1) # 1
deque.push(2) # 1,2
deque.push_left(3) # 3,1,2
deque.push_left(4) # 4,3,1,2
deque.items()
deque.pop() # 3,1,2
deque.pop_right() # 3,1
deque.items()
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/123544.html
