<big>编译环境：python v3.5.0, mac osx 10.11.4</big>
什么是队列
- 具有一定操作约束的线性表，只能在一端插入，在另一端删除。
- 数据插入（入队列，AddQ），数据删除（DeleteQ）
-
先入先出（FIFO）
如同生活中的排队买票，排在队头的先买票，排在队尾的最后一个最后才能买票。
队列的抽象数据类型描述
队列的顺序存储（数组）实现
- 基础实现：由一个数组和两个指针构成，插入元素则是指向后的指针（rear）后移一位，删除元素则把指向前的元素（front）后移一位，当队列为空时两个指针指向同一个位置。(queue.py)
# -- coding: utf-8 --
class Queue():
def init(self, maxSize): # 初始化队列,头和尾都指向-1
self._front = -1
self._rear = -1
self._q = [None] * maxSize
def addElem(self, element):
if self._rear == len(self._q)-1: # 如果rear指向了队列的最后一个元素,则队列满了
print('it is a full queue!')
else:
self._rear += 1
self._q[self._rear] = element
print('add ' + str(element) + ' in Queue')
def deleteElem(self): # 删除front指向的元素,并放回被删除的元素
if self._front == self._rear: # 如果front 和 rear指向同一个元素,则队列为空
print('it is an empty queue!')
else:
self._front += 1
value = self._q[self._front]
print('add ' + str(value) + ' in Queue')
self._q[self._front] = None # 删除元素
return value - 顺环队列：显然当上述队列的实现不能充分的利用存储空间，即当每个存储单元只能存储一次元素，当进行delete操作后，就一直空着了。这并不是我们想要的结果，所以为了高效的利用计算机存储空间，我们一般利用顺环队列进行实现。
实现关键：对front和rear都采用<big>“加一取余”</big>的办法来实现顺序存储的循环利用，且rear和front起始都指向位置0而不是1。(queue.py)
# -- coding: utf-8 --
class Queue():
def init(self, maxSize): # 初始化队列,头和尾都指向0
self._front = 0
self._rear = 0
self._q = [None] * maxSize
def addElem(self, element):
if (self._rear + 1) % len(self._q) == self._front: # 对rear进行加一取余数(实现循环利用),但到达最大数时归到起始位置即0,1,2,3,4,0,1,2,3,4依次循环
print('it is a full queue!')
else:
self._q[self._rear] = element
self._rear = (self._rear + 1) % len(self._q)
#print(str(self._rear)+'----'+str(self._front))
print('add ' + str(element) + ' in Queue')
def deleteElem(self): # 删除front指向的元素,并放回被删除的元素
if self._front == self._rear: # 如果front 和 rear指向同一个元素,则队列为空
print('it is an empty queue!')
else:
value = self._q[self._front]
self._q[self._front] = None # 删除元素
self._front = (self._front + 1) % len(self._q) # 对rear进行加一取余数(实现循环利用),但到达最大数时归到起始位置
print('delete ' + str(value) + ' out of Queue')return value
队列的链式存储（链表）实现
队列的链式存储结构也可以由单向链表实现。由于删除操作作用在front头，所以front指向头节点。(queue_chain.py)
class Note():
def __init__(self,value=None,next=None):
self.value = value
self.next = next
class queueChain:
def __init__(self,front=None,rear=None):
self.front = front # fron指向表头的指针
self.rear = rear # rear指向表尾的指针
def inQue(queue, value): # 入队操作
newNote = Note(value)
if queue.front is None: # 链表为空,将front 赋值给表头
queue.front = queue.rear = newNote
else:
queue.rear.next = newNote
queue.rear = newNote
print('add '+str(value)+' in the queue' )
def outQue(queue): # 出队操作
if queue.front is None : # 如果front指向为空,则链表为空
print('it is an empty queue!')
else:
p = queue.front
element = p.value
if queue.front == queue.rear: # 如果前后指针指向一个元素,则全部重置为None
queue.front = queue.rear = None
else:
queue.front = p.next
del p # 释放空间
print('delete ' + str(element) +' out of Queue')
return element
网友评论