# 原宝宝
# 编程时间2022/7/3 15:57
# 双端队列---链表实现
#from collections import deque #python自带的双端循环队列
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 != None:
print(cur.data, "->", end=" ")
cur = cur.next
print()
def push(self, 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('双端队列为空！')
else: # 队列不为空
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.next == self.rear时 二者都指向队尾 此时cur即为最后一个节点的前一个节点
cur = cur.next
self.rear = cur
cur.next = None
self._length -= 1
return value
def peek(self):
#获取队头
if self.is_empty() == 1:
raise ValueError("双端队列为空")
else:
return self.head.data
if __name__ == "__main__":
deque = Deque()
deque.push(1) # 从队尾进入队列
deque.push(2)#1,2
deque.push_left(3)# 从队头进入队列
deque.push_left(4)#4 3 1 2
deque.items()
deque.pop() # 从队头弹出
deque.items()
deque.pop_right() # 从队尾弹出
deque.items()
结果
