--从尾入头出

功能实现：

入队：建立两个变量做为头(front)尾(rear)的指针.

self.front=self.rear=Node(None)

初始化时同时指向一个空的结点Node(None),入队开始新建一个有用结点，把front的指针指向这个结点，然后再移动到该结点位置。

例如：幼儿园老师组织孩子们排队放学。两个老师同时到教室门口，一个做队头一个做队尾。开始两个老师都在一个位置，等学生出来，尾老师把第一个学生的手拉过来交给首老师，然后尾老师和第一个学生站在一起，在把第二个学生拉过来交给第一个学生，尾老师又和第二个学生站在一起，以此类推最后尾老师和最后入队的学生站在一起。

出队：出队时只要首老师站在第一个学生位置，第一个学生就出队了。

'''

队列的链式栈

重点代码

思路分析：

1、源于链表结构

2、封装队列的操作方法（入队，出队，是否为空，队顶元素）

3、用链表的开头作为队头，队列的尾部作队列的队尾

4、单独对队尾作标记，避免遍历

5、当除头队尾标记重合的时候认为队列是空

'''

#自定义异常

class StackError(Exception):

pass

#创建节点类

class Node:

'''

思路：将自定义的类视为节点生成类，实例对象中包含

数据部分和指向下一个节点的next

'''

def __init__(self,val,next=None):

self.val=val

self.next=next

#链式队列

class Queue:

def __init__(self):

#定义队头和队尾的变量

self.front=self.rear=Node(None)

def is_empty(self):#判断是否为空

return self.front==self.rear

def enqueue(self, val):#入队rear向后动。

self.rear.next=Node(val)#把新节点挂在rear后面同时也就挂在front上面

self.rear=self.rear.next#把rear向后移动到新节点上

def dequeue(self):#出队

if self.is_empty():

raise StackError("Stack is empty")

else:

#value= self.front.next.val

self.front=self.front.next#认为front指向的节点已经出队，

return self.front.val

def top(self):

if self.is_empty():

raise StackError("Stack is empty")

return self.front.next.val

def show(self):#输出队列(测试有问题）

p = self.front.next

while not self.is_empty():

print(p.val,end=" ")

p = p.next

#测试：

if __name__=="__main__":

l=Queue()

l.enqueue(1)

l.enqueue(2)

l.enqueue(3)

l.enqueue(4)

l.enqueue(5)

print(l.dequeue())

print(l.top())