队列是一种先进先出的数据结构, python 中有 queue 模块来实现队列
数组实现队列:
- class Queue():
- def __init__(self):
- self.entries = [] #表示队列内的参数
- self.length = 0 #表示队列的长度
- self.front=0 #表示队列头部位置
- def enqueue(self, item):# 入队列
- self.entries.append(item)
- self.length = self.length + 1 #队列长度增加 1
- def dequeue(self):# 出队列
- self.length = self.length - 1 #队列的长度减少 1
- dequeued = self.entries[self.front] #队首元素为 dequeued
- self.front-=1 #队首的位置减少 1
- self.entries = self.entries[self.front:] #更新队列
- return dequeued
- def peek(self):# 获取队列第一个元素
- return self.entries[0]
- if __name__ == "__main__":
- q=Queue()
- q.enqueue(7)
- q.enqueue(89)
- print(q.peek())#7
- print(q.dequeue())#7
- print(q.peek())#89
- 7 7 89
链表实现队列:
- class Node(object):
- def __init__(self,elem,next=None):
- self.elem = elem #表示对应的元素值
- self.next=next #表示下一个链接的链点
- class Queue(object):
- def __init__(self):
- self.head = None #头部链点为 None
- self.rear = None #尾部链点为 None
- def is_empty(self):
- return self.head is None #判断队列是否为空
- def enqueue(self, elem):
- p = Node(elem) #初始化一个新的点
- if self.is_empty():
- self.head = p #队列头部为新的链点
- self.rear = p #队列尾部为新的链点
- else:
- self.rear.next = p #队列尾部的后继是这个新的点
- self.rear =p #然后让队列尾部指针指向这个新的点
- def dequeue(self):
- if self.is_empty(): #判断队列是否为空
- print('Queue_is_empty') #若队列为空, 则退出 dequeue 操作
- else:
- result = self.head.elem #result 为队列头部元素
- self.head = self.head.next #改变队列头部指针位置
- return result #返回队列头部元素
- def peek(self):
- if self.is_empty(): #判断队列是否为空
- print('NOT_FOUND') #为空则返回 NOT_FOUND
- else:
- return self.head.elem #返回队列头部元素
- def print_queue(self):
- print("queue:")
- temp=self.head
- myqueue=[] #暂时存放队列数据
- while temp is not None:
- myqueue.append(temp.elem)
- temp=temp.next
- print(myqueue)
- if __name__=="__main__":
- q=Queue()
- q.enqueue(1)
- q.enqueue(2)
- print(q.peek())#1
- print(q.dequeue())#1
- print(q.peek())#2
- 1 1 2
来源: http://www.bubuko.com/infodetail-3361059.html