用python实现链式队列

队列

队列也是一种线性的数据结构，和栈相反的是，队列是一种先进先出的线性表。它只允许在表的一端进行插入，而在另一端进行删除元素。与我们现实生活中的排队是一样的：排在队伍最前面的会先完成事情离开队伍。

在数据结构中抽象为一种线性链表，如下所示

链式队列基本数据结构

链式队列即是链表构成，通过指针相连。实现过程如下

链式队列基本单元: 节点(Node)

创建Node类

值域
指针域

class Node:
    def __init__(self, v):
        """
        :param v: the value of node
        """
        self.value = v
        self.pnext = None  # the pointer to point next

链式队列类

创建LinkedQueue类

front: 队头节点
rear: 队尾节点
length: 队列长度

class LinkedQueue:
    def __init__(self):
        self.front = None  # the head node of queue
        self.rear = None   # the rear node of queue
        self.length = 0    # the length of queue

链式队列操作函数

self参数为对象本身，类似于C++中的this指针

判断队列是否为空

创建queue_empty函数

def queue_empty(self):
    """
    if the queue is empty
    :return:
    """
    if self.front is None:
        return True
    else:
        return False

获取队首元素

创建get_head函数

def get_head(self):
    """
    get the value of head node
    :return:
    """
    return self.front.value

入队

创建enqueue函数

val: 节点值

def enqueue(self, val):
    """
    insert value to queue's rear
    :param val:
    :return:
    """
    if self.queue_empty():
        self.front = Node(val)
        self.rear = self.front
        self.length += 1
    else:
        self.rear.pnext = Node(val)
        self.rear = self.rear.pnext
        self.length += 1

出队

创建dequeue函数

def dequeue(self):
    """
    delete the value of head node and return its value
    :return:
    """
    if not self.queue_empty():
        val = self.front.value
        self.front = self.front.pnext
        self.length -= 1
        return val

遍历队列(队首-队尾)

创建queue_traverse函数

def queue_traverse(self):
    """
    traverse the queue
    :return:
    """
    print('队头->|', end=' ')
    tmp = self.front
    while tmp:
        print(tmp.value, '|', end=' ')
        tmp = tmp.pnext
    print("\n")

测试案例

创建程序入口

if __name__ == "__main__":
    my_queue = LinkedQueue()
    my_queue.enqueue([1, 2, 3])
    my_queue.enqueue(456)
    my_queue.enqueue('hello')
    my_queue.queue_traverse()
    my_queue.dequeue()
    my_queue.queue_traverse()

运行结果如下：

1
2
3

队头->| [1, 2, 3] | 456 | hello |

队头->| 456 | hello |

源码

点击此处访问