Python实现--队列的顺序存储和链式存储

75 阅读 0 评论 50 点赞

我是靠谱客的博主单薄香氛，最近开发中收集的这篇文章主要介绍Python实现--队列的顺序存储和链式存储，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

队列：允许插入的一端为队头front，允许删除的一端为队尾rear，先进先出的原则。
顺序队列：sequential queue
队尾指针指示队尾元素在一维数组中的当前位置，队头指针指示队头元素在一维数组中当前位置的前一个位置，空队列self.front= self.rear = 0
链式队列：linked queue 不需要指定长度,一般不会产生队满
一个同时带有头指针和尾指针的单链表，头指针指向头结点，尾指针指向尾结点

class SequenceSqueue(object):
	def __init__(self,maxsize):
		self.maxsize = maxsize
		self.data = [None for _ in range(maxsize)]
		#self.data = list(None for x in range(maxsize))
		self.front = 0
		self.rear = 0

	def isEmpty(self):
		if self.front == self.rear:
			print True
		else:
			print False


	def getLength(self):
		print self.rear - self.front


	def En_Queue(self,x):
		if self.rear < self.maxsize:
			self.rear = self.rear + 1
			self.data[self.rear] = x
		else:
			print 'queue is full!'

	def init_queue(self):
		element = input('please input a element,# for end:')
		while element != '#':
			self.En_Queue(element)
			element = input('please input a element,# for end:')

	def show_queue(self):
		if self.front == self.rear:
			print 'queue is empty!'
		else:
			index = self.front + 1
			store = []
			while index < self.rear + 1:
				store.append(self.data[index])
				index  = index + 1
			print store

	def Del_Queue(self):
		if self.front == self.rear:
			print 'queue is empty!'
		else:
			self.front = self.front + 1
			print self.data[self.front]

	def Queue_Head(self):
		if self.front == self.rear:
			print 'queue is empty!'
		else:
			print self.data[self.front + 1]
	def clear_queue(self):
		self.front = self.rear
		print 'clear over!'

if __name__ == '__main__':
	q= SequenceSqueue(100)
	q.isEmpty()
	q.init_queue()
	q.show_queue()
	q.Queue_Head()
	q.En_Queue('new')
	q.Del_Queue()
	q.show_queue()
	q.getLength()

输出：
True
please input a element,# for end:1
please input a element,# for end:2
please input a element,# for end:3
please input a element,# for end:’#’
[1, 2, 3]
1
1
[2, 3, ‘new’]
3

class Node(object):
#must give a param data = None, En_Queue will use
	def __init__(self,data = None):
		self.data = data
		self.next = None

class LinkedQueue(object):
	def __init__(self):
		self.front = Node()
		self.rear = Node()
		self.length = 0

	def isEmpty(self):
		if self.length == 0:
			print True
		else:
			print False
	def getLength(self):
		print self.length

	def En_Queue(self,item):
		temp = Node(item)
		#if use self.isEmpty.everyrtime init will print True or False
		if self.length == 0:
			self.front = temp
			self.rear = temp
		else:
			self.rear.next = temp
			self.rear = temp
		self.length = self.length + 1

	def init_queue(self):
		data = input('please input item, # for end:')
		while data != '#':
			self.En_Queue(data)
			#self.length = self.length + 1
			data = input('please input item, # for end:')

	def Del_Queue(self):
		if self.length == 0 :
			print 'queue is null!'
		else:
			temp = self.front.data
			self.front = self.front.next
			self.length = self.length - 1
			print temp

	def Queue_Head(self):
		if self.length == 0 :
			print 'queue is null!'
		else:
			print self.front.data

	def show_queue(self):
		if self.length == 0 :
			print 'queue is null!'
		else:
			store = []
			temp, count = self.front, self.length
			while count > 0:
				store.append(temp.data)
				temp = temp.next
				count =  count - 1
			print store



if __name__ == '__main__':
	q= LinkedQueue()
	q.isEmpty()
	q.init_queue()
	q.show_queue()
	q.Queue_Head()
	q.En_Queue('ennew')
	q.Del_Queue()
	q.show_queue()
	q.getLength()

输出
True
please input item, # for end:1
please input item, # for end:2
please input item, # for end:3
please input item, # for end:4
please input item, # for end:’#’
[1, 2, 3, 4]
1
1
[2, 3, 4, ‘ennew’]
4
参考连接：https://blog.csdn.net/lqzhouxx/article/details/40863749