python队列的实现，,队列是一种抽象数据结

python队列的实现，,队列是一种抽象数据结

队列是一种抽象数据结构，具有以下特点：

（1）具有先进先出的特性（FIFO）

（2）拥有两种基本操作，即加入和删除，而且使用front和rear两个指针来分别指向队列的前端和末尾。

队列的基本操作

create 创建空队列

add 将新数据加入队列的末尾，返回新队列

delete 删除队列前端的数据，返回新队列

front 返回队列前端的值

empty 若队列为空，则返回 ‘真’，否则返回 ‘假’

实现queue有两种方式可以用数组和链表

1.我们先用数组实现队列，数组实现队列的好处在于算法相当简单，但是也有缺点，数组无法根据队列的实际需要动态申请，

只能声明固定的大小。现在我们声明一个有限容量的数组

MAXSIZE=4            #定义队列的大小queue=[0]*MAXSIZEfront=-1rear=-1

（1）开始时，我们将front与rear都设置-1，当front = rear时，为空队列

（2）当加入dataA , front=-1，rear=0，没加入一个元素，将rear值加1：

（3）加入dataB，dataC，front=-1，rear=2：

（4）取出dataA，front=0，rear=2，每取出一个元素，将front的值加1：

（5）加入dataD，front=0，rear=3，此时rear=MAXSIZE-1 ，表示队列已满

（6）取出dataB，front =1，rear=3：

对于以上队列操作，可以用Python语言实现一个队列的操作

import sysMAX=10            #定义队列的大小queue=[0]*MAXfront=rear=-1choice=‘‘while rear<MAX-1 and choice !=‘e‘:    choice=input(‘[a]表示加入一个数值，[d]表示取出一个数值，[e]表示跳出此程序: ‘)    if choice==‘a‘:        val=int(input(‘[请输入数值]: ‘))        rear+=1        queue[rear]=val    elif choice==‘d‘:        if rear>front:            front+=1            print(‘[取出数值为]: [%d]‘ %(queue[front]))            queue[front]=0        else:            print(‘[队列已经空了]‘)            sys.exit(0)    else:        print()print(‘------------------------------------------‘)print(‘[输出队列中的所有元素]:‘)if rear==MAX-1:    print(‘[队列已满]‘)elif front>=rear:    print(‘没有‘)    print(‘[队列已空]‘)else:    while rear>front:        front+=1        print(‘[%d] ‘ %queue[front],end=‘‘)    print()    print(‘------------------------------------------‘)print()

执行结果如下

2用链表实现队列

我们以学生姓名和成绩的结构数据建立队列的节点，加上front和rear指针，这个类的声明如下：

class student:    def __init__(self):        self.name=‘ ‘*20        self.score=0        self.next=None        front=student()rear=student()front=Nonerear=None

在队列中加入新节点等于加入到队列的末端，而删除节点就是将此队列的最前端的节点删除。添加和删除操作如下：

def enqueue(name, score):  # 把数据加入队列    global front    global rear    new_data=student()  # 分配内存给新元素    new_data.name=name  # 给新元素赋值    new_data.score = score    if rear==None:      # 如果rear为None，表示这是第一个元素        front = new_data    else:        rear.next = new_data    # 将新元素连接到队列末尾    rear = new_data         # 将rear指向新元素，这是新的队列末尾    new_data.next = None    # 新元素之后无其他元素def dequeue(): # 取出队列中的数据    global front    global rear    if front == None:        print(‘队列已空！‘)    else:        print(‘姓名：%s\t成绩：%d ....取出‘ %(front.name, front.score))        front = front.next    # 将队列前端移到下一个元素

我们使用链表来设计一个队列的程序

class student:    def __init__(self):        self.name=‘ ‘*20        self.score=0        self.next=None        front=student()rear=student()front=Nonerear=Nonedef enqueue(name, score):  # 把数据加入队列    global front    global rear    new_data=student()  # 分配内存给新元素    new_data.name=name  # 给新元素赋值    new_data.score = score    if rear==None:      # 如果rear为None，表示这是第一个元素        front = new_data    else:        rear.next = new_data    # 将新元素连接到队列末尾    rear = new_data         # 将rear指向新元素，这是新的队列末尾    new_data.next = None    # 新元素之后无其他元素def dequeue(): # 取出队列中的数据    global front    global rear    if front == None:        print(‘队列已空！‘)    else:        print(‘姓名：%s\t成绩：%d ....取出‘ %(front.name, front.score))        front = front.next    # 将队列前端移到下一个元素        def show():     # 显示队列中的数据    global front    global rear    ptr = front    if ptr == None:        print(‘队列已空！‘)    else:        while ptr !=None: # 从front到rear遍历队列            print(‘姓名：%s\t成绩：%d‘ %(ptr.name, ptr.score))            ptr = ptr.nextselect=0while True:    select=int(input(‘(1)加入 (2)取出 (3)显示 (4)离开 => ‘))    if select==4:        break    if select==1:        name=input(‘姓名: ‘)        score=int(input(‘成绩: ‘))        enqueue(name, score)    elif select==2:        dequeue()    else:        show()

执行如下：

python队列的实现