[python队列]用链表实现队列

48 阅读 0 评论 32 点赞

我是靠谱客的博主聪明斑马，最近开发中收集的这篇文章主要介绍[python队列]用链表实现队列，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

队列是一种先进先出的线性表
在这里插入图片描述
我们定义如下的链表来实现队列数据结构：

在这里插入图片描述
定义一个头结点，左边指向队列的开头，右边指向队列的末尾，这样就可以保证我们插入一个元素和取出一个元素都是O(1)的操作。

方法一，用链表实现程序如下：

# 定义一个头结点，左边指向队列的开头，
# 右边指向队列的末尾，保证我们插入一个元素和取出一个元素都是O(1)的操作
class Head:
    def __init__(self):
        self.left = None
        self.right = None


class Node:
    def __init__(self, value):
        self.value = value
        self.next = None


class Queue:
    def __init__(self):
        # 初始化节点
        self.head = Head()

    def enqueue(self, value):
        # 插入元素，先新建一个结点
        newnode = Node(value)
        p = self.head
        if p.right:
            # 如果head结点的右边不为None
            # 说明队列中已经有元素了

            temp = p.right
            p.right = newnode
            temp.next = newnode
        else:
            # 队列为空，插入第一个元素
            p.right = newnode
            p.left = newnode

    def dequeue(self):
        p = self.head
        if p.left and (p.left == p.right):
            # 这说明队列中已经有元素
            # 但是这是最后一个元素
            temp = p.left
            p.left = p.right = None
            return temp.value
        elif p.left and (p.left != p.right):
            # 说明队列中有元素，而且不止一个
            temp = p.left
            p.left = temp.next
            return temp.value

        else:
            # 队列为空，抛出查询错误
            raise LookupError('queue is empty')

    def is_empty(self):
        if self.head.left:
            return False
        else:
            return True

    def top(self):
        # 查询目前队列中最早入队的元素
        if self.head.left:
            return self.head.left.value
        else:
            raise LookupError('queue is empty')


if __name__ == '__main__':
    queue = Queue()
    print(queue.is_empty())
    queue.enqueue(1)
    queue.enqueue(2)
    queue.enqueue(3)
    queue.enqueue(4)
    queue.enqueue(5)
    print(queue.is_empty())
    print(queue.dequeue())
    print(queue.dequeue())
    
    print(queue.top())

方法二：Python内置函数实现。单纯地实现先入先出结构，使用Python内置函数更简单一些。

class Queue:
    def __init__(self):
        self.items = []

    def is_empty(self):
        return len(self.items) == 0

    def enqueue(self, item):
        self.items.insert(0, item)

    def dequeue(self):
        return self.items.pop()

    def size(self):
        return len(self.items)


if __name__ == '__main__':
    q = Queue()
    q.enqueue(1)
    q.enqueue(2)
    q.enqueue(3)
    q.enqueue(4)
    print(q.items)
    q.dequeue()
    q.dequeue()
    print(q.items)

参考文章：
https://www.cnblogs.com/yiduobaozhiblog1/p/9272556.html