python数据结构中实现队列的几种方法
1.list实现 enqueue append() dequeue pop(0) 或 enqueue insert(0,item) dequeue pop()
MAX_SIZE = 100
class MyQueue1(object):
"""模拟队列"""
def __init__(self):
self.items = []
self.size = 0
def is_empty(self):
"""判断是否为空"""
return self.size == 0
def size(self):
"""返回队列的大小"""
return self.size
def enqueue(self, item):
"""入队(加入元素)"""
self.items.append(item)
self.size += 1
def dequeue(self):
"""出队(弹出元素)"""
if self.size < MAX_SIZE and self.size >= 0:
self.size -= 1
return self.items.pop(0)
else:
print("队列已经为空")
return None
def getFront(self):
if not self.is_empty():
return self.items[0]
else:
return None
def getRear(self):
if not self.is_empty():
return self.items[self.size-1]
else:
return None
def __str__(self):
return str(self.items)
class MyQueue2(object):
"""模拟队列"""
def __init__(self):
self.items = []
self.size = 0
def is_empty(self):
"""判断是否为空"""
return self.size == 0
def size(self):
"""返回队列的大小"""
if self.size <= MAX_SIZE:
return self.size
def enqueue(self, item):
"""入队(加入元素)"""
if self.size <= MAX_SIZE:
self.items.insert(0, item)
self.size += 1
def dequeue(self):
"""出队(弹出元素)"""
if self.size > 0 and self.size <= MAX_SIZE:
self.size -= 1
return self.items.pop()
else:
print("队列已经为空")
return None
def getFront(self):
"""返回队头元素"""
if not self.is_empty():
return self.items[0]
else:
return None
def getRear(self):
if not self.is_empty():
return self.items[self.size-1]
else:
return None
def __str__(self):
return str(self.items)
def test(obj):
i = obj()
for x in range(0,6):
i.enqueue(x)
print(i)
i.dequeue()
print(i, i.getFront(), i.getRear(), i.size)
if __name__ == "__main__":
test(MyQueue1)
test(MyQueue2)
运行结果：
2.链队 前文已介绍
首尾指针实现
链队 首尾指针实现链队
class Node():
def __init__(self, value=None):
self.value = value
self.next = None
class StcakQueue():
def __init__(self):
self.front = Node()
self.rear = Node()
self.size = 0
def enqueue(self, value):
node = Node(value)
if self.size == 0:
self.front = node
self.rear = node
else:
self.rear.next = node
self.rear = node
self.size += 1
def dequeue(self):
if self.size == 0:
raise Exception('queue is empty')
else:
temp = self.front.value
self.front = self.front.next
self.size -= 1
return temp
def is_empty(self):
if self.size == 0 :
return False
else:
return True
def top(self):
if self.size == 0 :
raise LookupError('queue is empty')
else:
return self.front.value
def size(self):
return self.size
def __str__(self):
if self.size == 0:
return None
else:
stack_list = []
temp, count = self.front, self.size
while count > 0 :
stack_list.append(temp.value)
temp = temp.next
count -= 1
return str(stack_list)
if __name__ == "__main__":
i = StcakQueue()
for x in range(0,6):
i.enqueue(x)
print(i)
i.dequeue()
print(i, i.size)
尾插有头结点实现链队
链队 尾插法 有头结点实现链队
class Node(): #结点类
def __init__(self,elem):
self.elem = elem # 数据域，用来存放数据元素
self.next = None # 指针域，指向下一个结点
def __str__(self):
return str(self.elem)
class Queue(): # 队列
def __init__(self): # 队列初始化
self.head = None # 构造私有头结点
def is_empty(self):
return self.head == None
def enqueue(self,elem): # 进队列（正常向后填元素）
node = Node(elem) # 创建新结点
if self.is_empty(): # 如果为空, 新建head结点
self.head = Node
self.head.next = node
node = self.head
else:
current = self.head
while current.next is not None:
current = current.next
current.next = node
def dequeue(self): # 出队列（头出）
if not self.is_empty():
current = self.head.next
self.head.next = self.head.next.next
return current.elem
else:
raise IndexError('pop from a empty stack')
def size(self):
current = self.head
count = 0
while current.next is not None:
current = current.next
count += 1
return count
def __repr__(self):
stack_list = []
current = self.head
while current.next is not None:
stack_list.append(current.next.elem)
current = current.next
return str(stack_list)
__str__ = __repr__
if __name__ == "__main__":
i = Queue()
for x in range(0, 6):
i.enqueue(x)
print(i)
i.dequeue()
print(i, i.size())
3.两个栈实现一个队列 O(1)
两个栈实现一个队列 list栈
class CQueue:
def __init__(self):
self.stack1 = []
self.stack2 = []
def append_tail(self, elem):
self.stack1.append(elem)
def delete_head(self):
if not self.stack2:
if self.stack1:
while self.stack1:
elem = self.stack1.pop()
self.stack2.append(elem)
else:
raise Exception("Queue is empty.")
elem = self.stack2.pop()
return elem
#学习中遇到问题没人解答？小编创建了一个Python学习交流群：711312441
def unitest():
# Create an instance of class CQueue
que = CQueue()
print("Push 1, 2, 3 successively into CQueue.")
for i in range(1, 4):
que.append_tail(i)
print("Pop the head of the queue:", que.delete_head())
print("Pop the head of the queue:", que.delete_head())
print("Push 4, 5, 6 successively into CQueue.")
for i in range(4, 7):
que.append_tail(i)
# Pop the rest elements in the queue
for i in range(4):
print("Pop the head of the queue:", que.delete_head())
if __name__ == '__main__':
unitest()