document.write('与实现栈的方法类似，队列的实现也有两种方法，分别为采用数组来实现和采用链表来实现。下面分别详细
介绍这两种方法。
方法一：数组实现
下图给出了一种最简单的实现方式，用front来记录队列首元素的位置，用rear来记录队列尾元素往后一
个位置。入队列的时候只需要将待入队列的元素放到数组下标为rear的位置，同时执行rear+，出队列的时
候只需要执行front+即可。
示例代码如下：
class MyQueue:
def __init__(self):
self.arr=[]
self.front=0 #队列头
self.rear=0 #队列尾
#判断队列是否为空
def isEmpty(self):
return self.front==self.rear
#返回队列的大小
def size(self):
return self.rear-self.front
#返回队列首元素
def getFront(self):
if self.isEmpty():
return None
return self.arr[self.front]
#返回队列尾元素
def getBack(self):
if self.isEmpty():
return None
return self.arr[self.rear-1]
#删除队列头元素
def deQueue(self):
if self.rear＞self.front:
self.front+=1
else:
print "队列已经为空"
#把新元素加入队列尾
def enQueue(self,item):
self.arr.append(item)
self.rear+=1
if __name__=="__main__":
queue=MyQueue()
queue.enQueue(1)
queue.enQueue(2)
print "队列头元素为:"+str(queue.getFront())
print "队列尾元素为:"+str(queue.getBack())
print "队列大小为:"+str(queue.size())
程序的运行结果为：
队列头元素为：1
队列尾元素为：2
队列大小为：2
以上这种实现方法最大的缺点为：出队列后数组前半部分的空间不能被充分地利用，解决这个问题的方法
为把数组看成一个环状的空间(循环队列)。当数组最后一个位置被占用后，可以从数组首位置开始循环利
用，具体实现方法可以参考数据结构的课本。
方法二：链表实现
采用链表实现队列的方法与实现栈的方法类似，分别用两个指针指向队列的首元素与尾元素，如下图所
示。用pHead来指向队列的首元素，用pEnd来指向队列的尾元素。
在上图中，刚开始队列中只有元素1、2和3，当新元素4要进队列的时候，只需要上图中(1)和(2)两步，就
可以把新结点连接到链表的尾部，同时修改pEnd指针指向新增加的结点。出队列的时候只需要步骤(3)，改
变pHead指针使其指向pHead.next，此外也需要考虑结点所占空间释放的问题。在入队列与出队列的操作
中也需要考虑队列尾空的时候的特殊操作，实现代码如下所示：
class LNode:
def __new__(self,x):
self.data=x
self.next=None
class MyQueue:
#分配头结点
def __init__(self):
self.pHead=None
self.pEnd=None
#判断队列是否为空,如果为空返回true,否则返回false
def empty(self):
if self.pHead=None:
return True
else:
return False
#获取栈中元素的个数
def size(self):
size=()
p=self.pHead
while p!=None:
p=p.next
size+=1
return size
#入队列: 把元素e加到队列尾
def enQueue(self,e):
p=LNode()
p.data=e
p.next=None
if self.pHead==None:
self.pHead=self.pEnd=p
else:
self.pEnd.next=p
selfpEnd=p
#出队列,删除队列首元素
def deQueue(self):
if self.pHead==None:
print "出队列失败,队列已经为空"
self.pHead=self.pHead.next
if self.pHead==None:
self.pEnd=None
#取得队列首元素
def getFront(self):
if self.pHead==None:
print "获取队列首元素失败,队列已经为空"
return None
return self.pHead.data
#取得队列尾元素
def getBack(self):
if self.pEnd==None:
print "获取队列尾元素失败,队列已经为空"
return None
return self.pEnd.data
if __name__="__main__":
queue=MyQueue()
queue.enQueue(1)
queue.enQueue(2)
print "队列头元素为: "+str(queue.getFront())
print "队列尾元素为: "+str(queue.getBack())
print "队列大小为: "+str(queue.size())
程序的运行结果为：
队列头元素为：1
队列尾元素为：2
队列大小为：2
显然用链表来实现队列有更好的灵活性，与数组的实现方法相比，它多了用来存储结点关系的指针空间。
此外，也可以用循环链表来实现队列，这样只需要一个指向链表最后一个元素的指针即可，因为通过指向链
表尾元素可以非常容易地找到链表的首结点。
');
![\"360截图20190815222652015.jpg\"](\"http://www.alatiku.com/d/file/shiti/5974400e906d1668d0dfbc189eaed765.jpg\")
![\"360截图20190815222724806.jpg\"](\"http://www.alatiku.com/d/file/shiti/17dc588730cf0c6ea43e684d89dc300d.jpg\")