Python数据结构之队列详解

目录
  • 0. 学习目标
  • 1. 队列的基本概念
    • 1.1 队列的基本概念
    • 1.2 队列抽象数据类型
    • 1.3 队列的应用场景
  • 2. 队列的实现
    • 2.1 顺序队列的实现
    • 2.2 链队列的实现
    • 2.3 队列的不同实现对比
  • 3. 队列应用
    • 3.1 顺序队列的应用
    • 3.2 链队列的应用
    • 3.3 利用队列基本操作实现复杂算法

0. 学习目标

栈和队列是在程序设计中常见的数据类型,从数据结构的角度来讲,栈和队列也是线性表,是操作受限的线性表,它们的基本操作是线性表操作的子集,但从数据类型的角度来讲,它们与线性表又有着巨大的不同。本节将介绍队列的定义及其不同实现,并且给出队列的一些实际应用。
通过本节学习,应掌握以下内容:

  • 队列的基本概念及不同实现方法
  • 队列基本操作的实现及时间复杂度
  • 利用队列的基本操作实现复杂算法

1. 队列的基本概念

1.1 队列的基本概念

队列 (Queue) 是插入和删除操作分别被限制在序列两端的线性表(新元素从一段插入其中,则只能从另一端删除已有元素),对于队列而言,允许插入元素的一端称为队尾 (rear),而允许取出元素的一段则称为队头 (front)。

在队列中,数据到达的顺序很重要。最新添加的元素位于必须在队尾,在队列中时间最长的元素则排在最前面,这种排序原则被称作先进先出 (first in first out,FIFO),或后进后出 (last in first out, LILO)。

队列在现实中的例子随处可见,我们生活中就餐所需要进行的排队就是一个队列的现实例子,最早进入队列的人可以首先就餐,而后来者需要排于队尾等待。假设队列为 Q=(a0,a1,...,an),则队头元素为a0,an为队尾元素,队列中元素按a0,a1,...,an的顺序入队 (enqueue),出队 (dequeue) 也只能按照这个顺序依次退出,队头元素是第一个出队 (dequeue) 的元素,而只有a0,a1,...,an-1在都出队后,才an 能退出队列。下图是一个简单的队列示例:

通过观察元素的添加和移除顺序,就可以快速理解队列所蕴含的思想。下图展示了队列元素的入队和出队过程,队列中元素的插入顺序和移除顺序是完全相同的。

1.2 队列抽象数据类型

除了主要的操作(入队和出队)外,队列还具有初始化、判队空和求队长度等辅助操作。具体而言,队列的抽象数据类型定义如下:

1.3 队列的应用场景

队列具有广泛的应用场景,例如:

  • 在作业具有相同优先级的前提下,操作系统会按照作业的到达顺序安排作业;
  • 击键操作被放入一个类似于队列的缓冲区,以便对应的字符按正确的顺序显示;
  • 模拟现实世界的队列;
  • 多道程序设计;
  • 异步数据传输;

除了以上应用外,我们在之后的学习中还将看到队列用作许多算法的辅助数据结构。

2. 队列的实现

和线性表一样,队列同样有顺序存储和链式存储两种存储表示方式。

2.1 顺序队列的实现

类似于顺序栈,队列的顺序存储结构利用一组地址连续的存储单元依次存放从队列头到队列尾依次存放,同时需要用两个指针 front 和 rear 分别指示队列头元素和队列尾元素的位置。初始化空队列时,front=rear=0,当元素入队时,rear 加 1,而元素出队时,front 加 1,如下所示:

从以上示例中,可以很清楚地看到位于队头之前的空间被浪费了,为了解决这一问题,我们可以假设顺序队列为环状空间,将最后一个元素和第一个元素视为连续的,如下图所示:

从上图可以看出,当队列满时与队列空时,都有front=rear,因此无法通过 front==rear 来判断队列是否已满。针对这一问题,有两种解决方法:1) 设置标志来指示队列中是否还有空闲空间;2) 放弃一个元素空间,即当 front 指针在 rear 指针的下一位时 ((rear+1)%max_size=front) 队列为满。以下实现使用第二种方案。

同样顺序队列可以是固定长度和动态长度,当队列满时,定长顺序队列会抛出栈满异常,动态顺序队列则会动态申请空闲空间。

2.1.1 队列的初始化

顺序队列的初始化需要 4 部分信息:queue 列表用于存储数据元素,max_size 用于存储 queue 列表的最大长度,以及 front 和 rear 分别用于记录队头元素和队尾元素的索引:

class Queue:
    def __init__(self, max_size=5):
        self.max_size = max_size
        self.queue = [None] * self.max_size
        self.front = 0
        self.rear = 0

2.1.2 求队列长度

由于 front 和 rear 分别用于记录队头元素和队尾元素的索引,因此我们可以方便的计算出队列的长度;同时我们需要考虑队列为循环队列,front 可能大于 rear,不能直接通过 rear-front,我们需要利用公式计算解决此问题:

Python 实现如下:

    def size(self):
        return (self.rear-self.front+self.max_size) % self.max_size

2.1.3 判队列空

根据 front 和 rear 的值可以方便的判断队列是否为空:

    def isempty(self):
        return self.rear==self.front

2.1.4 判队列满

根据 front 和 rear 的值可以方便的判断队列是否还有空余空间:

    def isfull(self):
        return ((self.rear+1) % self.max_size == self.front)

2.1.5 入队

入队时,需要首先判断队列中是否还有空闲空间,然后根据队列为定长顺序队列或动态顺序队列,入队操作稍有不同:

[定长顺序队列的入队操作] 如果队满,则引发异常:

    def enqueue(self, data):
        if not self.isfull():
            self.queue[self.rear] = data
            self.rear = (self.rear+1) % self.max_size
        else:
            raise IndexError("Full Queue Exception")

[动态顺序队列的入队操作] 如果队列满,则首先申请新空间,然后再执行入队操作:

    def resize(self):
        new_size = 2 * self.max_size
        new_queue = [None] * new_size
        for i in range(self.max_size):
            new_queue[i] = self.queue[i]
        self.queue = new_queue
        self.max_size = new_size

    def enqueue(self, data):
        if self.isfull():
            self.resize()
        self.queue[self.rear] = data
        self.rear = (self.rear+1) % self.max_size

入队的时间复杂度为O(1)。这里需要注意的是,虽然当动态顺序队列满时,原队列中的元素需要首先复制到新队列中,然后添加新元素,但参考《顺序表及其操作实现》中顺序表追加操作的介绍,由于 n 次入队操作的总时间T(n) 与)O(n) 成正比,因此队栈的摊销时间复杂度可以认为是O(1)。

2.1.6 出队

若队列不空,则删除并返回队头元素:

    def dequeue(self):
        if not self.isempty():
            result = self.queue[self.front]
            self.front = (self.front+1) % self.max_size
            return result
        else:
            raise IndexError("Empty Queue Exception")

2.1.7 求队头元素

若队列不空,则返回队头元素:

    def head(self):
        if not self.isempty():
            result = self.queue[self.front]
            return result
        else:
            raise IndexError("Empty Queue Exception")

2.2 链队列的实现

队列的另一种存储表示方式是使用链式存储结构,因此也常称为链队列,其中 enqueue 操作是通过在链表尾部插入元素来实现的,dequeue 操作是通过从头部删除节点来实现的。

2.2.1 队列结点

队列的结点实现与链表并无差别:

class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None
    def __str__(self):
        return str(self.data)

2.2.2 队列的初始化

队列的初始化函数中,使其队头指针 front 和 rear 均指向 None,并初始化队列长度:

class Queue:
    def __init__(self):
        self.front = None
        self.rear = None
        self.num = 0

2.2.3 求队列长度

返回 size 的值用于求取队列的长度,如果没有 size 属性,则需要遍历整个链表才能得到队列长度:

    def size(self):
        return self.num

2.2.4 判队列空

根据队列的长度可以很容易的判断队列是否为空队列:

    def isempty(self):
        return self.num <= 0

2.2.5 入队

入队时,在队尾插入新元素,并且需要将队尾指针 rear 指向新元素,如果队列为空,需要将队头指针 front 也指向此元素:

    def enqueue(self, data):
        node = Node(data)
        if self.front is None:
            self.rear = node
            self.front = self.rear
        else:
            self.rear.next = node
            self.rear = node
        self.num += 1

2.2.6 出队

若队列不空,则删除并返回队头元素,并且需要更新队头指针 front 指向原队头结点的后继结点,若出队元素尾队中最后一个结点,则更新队尾指针 rear:

    def dequeue(self):
        if self.isempty():
            raise IndexError("Empty Queue Exception")
        result = self.front.data
        self.front = self.front.next
        self.num -= 1
        if self.isempty():
            self.rear = self.front
        return result

2.2.7 求队头元素

若队列不空,则返回队头元素:

    def head(self):
        if self.isempty():
            raise IndexError("Empty Queue Exception")
        result = self.front.data
        return result

2.3 队列的不同实现对比

队列的不同实现对比与栈的不同实现类似,可以参考《栈及其操作实现》。

3. 队列应用

接下来,我们首先测试上述实现的队列,以验证操作的有效性,然后利用实现的基本操作来解决实际算法问题。

3.1 顺序队列的应用

首先初始化一个顺序队列 queue,然后测试相关操作:

# 初始化一个最大长度为5的队列
q = Queue(5)
print('队列空?', q.isempty())
for i in range(4):
    print('入队元素:', i)
    q.enqueue(i)
print('队列满?', q.isfull())
print('队头元素:', q.head())
print('队列长度为:', q.size())
while not q.isempty():
    print('出队元素:', q.dequeue())

测试程序输出结果如下:

队列空? True
入队元素: 0
入队元素: 1
入队元素: 2
入队元素: 3
# 队列中弃用一个空间,因此队列中有4个元素即满
队列满? True
队头元素: 0
队列长度为: 4
出队元素: 0
出队元素: 1
出队元素: 2
出队元素: 3

3.2 链队列的应用

首先初始化一个链队列 queue,然后测试相关操作:

# 初始化新队列
q = Queue()
print('队列空?', q.isempty())
for i in range(4):
    print('入队元素:', i)
    q.enqueue(i)
print('队头元素:', q.head())
print('队列长度为:', q.size())
while not q.isempty():
    print('出队元素:', q.dequeue())

测试程序输出结果如下:

队列空? True
入队元素: 0
入队元素: 1
入队元素: 2
入队元素: 3
队头元素: 0
队列长度为: 4
出队元素: 0
出队元素: 1
出队元素: 2
出队元素: 3

3.3 利用队列基本操作实现复杂算法

考虑经典的约瑟夫斯环问题,n 个人围成一圈,从第 1 个人开始报数,第 m 个将被淘汰,重复上述过程,直到只剩下一个人,其余人都将被淘汰。

我们使用队列来模拟一个环,如下图所示,从队列的头部开始,将位于队首的人移出队列并立刻将其插入队列的尾部,之后此人会一直等待,直到其再次到达队列的头部。在出列和入列 m-1 次之后,位于队列头部的人出局(即第 m 个人),然后新一轮游戏开始;如此反复,直到队列中只剩下一个人(队列的大小为 1 )。

def Josephus(name_list, m):
    queue = Queue()
    for name in name_list:
        queue.enqueue(name)
    while queue.size() > 1:
        for i in range(m-1):
            queue.enqueue(queue.dequeue())
        queue.dequeue()
    return queue.head()
# n=6, m=5
result = Josephus(["A", "B", "C", "D", "E", "F"], 5)
print('幸存的人为', result)

程序输出结果如下:

幸存的人为 A

以上就是Python数据结构之队列详解的详细内容,更多关于Python队列的资料请关注我们其它相关文章!

(0)

相关推荐

  • Python数据结构与算法中的队列详解(2)

    目录 传土豆 总结 传土豆 队列的一个典型方法是模拟需要以 FIFO 方式管理数据的真实场景.考虑这样一个游戏:传土豆.在这个游戏中,成员们围成一圈,并依次尽可能快地传递一个土豆.在某个时刻,大家停止传递,此时手里有土豆的成员就得退出游戏. 重复上述过程,直到只剩下一个成员. 我们将针对传土豆游戏实现通用的模拟程序.该程序接受一个名字列表和一个用于计数的常量 num ,并且返回最后剩下的那个人的名字. 我们使用队列来模拟一个环.即假设握着土豆的人位于队列的头部.在模拟传土豆的过程中,程序将这个人

  • Python数据结构与算法中的队列详解(1)

    目录 什么是队列? 构建一个队列 总结 什么是队列? 队列,与栈类似,是有序集合.添加操作发生在 “尾部”,移除操作只发生在 “头部”.新元素只从尾部进入队列,然后一直向前移动到头部,直到成为下一个被移除的元素.​ 最新添加的元素必须在队列的尾部等待,在队列中时间最长的元素则排在最前面.这种排序原则被称作FIFO(first-in first-out),即先进先出,也称先到先得.在日常生活中,我们经常排队,这便是最简单的队列例子.进电影院要排队,在超市结账要排队,买咖啡也要排队.好的队列只允许一

  • Python 数据结构之队列的实现

    Python 队列 Queue 队列是一种先进先出(FIFO)的数据类型, 新的元素通过 入队 的方式添加进 Queue 的末尾, 出队 就是从 Queue 的头部删除元素. 用列表来做 Queue: queue = [] # 初始化一个列表数据类型对象, 作为一个队列 def enQ(): # 定义一个入栈方法 queue.append(raw_input('Enter New String: ').strip()) # 提示输入一个入队的 String 对象, 调用 Str.strip()

  • Python实现的数据结构与算法之队列详解

    本文实例讲述了Python实现的数据结构与算法之队列.分享给大家供大家参考.具体分析如下: 一.概述 队列(Queue)是一种先进先出(FIFO)的线性数据结构,插入操作在队尾(rear)进行,删除操作在队首(front)进行. 二.ADT 队列ADT(抽象数据类型)一般提供以下接口: ① Queue() 创建队列 ② enqueue(item) 向队尾插入项 ③ dequeue() 返回队首的项,并从队列中删除该项 ④ empty() 判断队列是否为空 ⑤ size() 返回队列中项的个数 队

  • 详解python数据结构之队列Queue

    一.前言 队列Queue是一种先进先出(FIFO,First In First Out)的线性表.允许一端进行插入(rear),对应的另一段进行删除(front). 本篇包含以下内容: (1)Queue的基本格式 (2)入队列en_queue (3)删除数据函数 de_queue 二.Queue的基本格式 class Queue(): def __init__(self,size): self.size = size self.front = -1 #设置front初始值,每出队列一个数据就加

  • Python的数据结构与算法之队列详解

    目录 模拟打印机任务队列过程 主要模拟步骤: ​构建队列程序 模拟打印程序 模拟打印过程(有注释) 总结 模拟打印机任务队列过程 计算机科学中也有众多的队列例子.比如计算机实验室有10台计算机,它们都与同一台打印机相连.当学生需要打印的时候,他们的打印任务会进入一个队列.该队列中的第一个任务就是即将执行的打印任务.如果一个任务排在队列的最后面,那么它必须等到所有前面的任务都执行完毕后才能执行.​ 学生向共享打印机发送打印请求,这些打印任务被存在一个队列中,并且按照先到先得的顺序执行.这样的设定可

  • Python数据结构之队列详解

    目录 0. 学习目标 1. 队列的基本概念 1.1 队列的基本概念 1.2 队列抽象数据类型 1.3 队列的应用场景 2. 队列的实现 2.1 顺序队列的实现 2.2 链队列的实现 2.3 队列的不同实现对比 3. 队列应用 3.1 顺序队列的应用 3.2 链队列的应用 3.3 利用队列基本操作实现复杂算法 0. 学习目标 栈和队列是在程序设计中常见的数据类型,从数据结构的角度来讲,栈和队列也是线性表,是操作受限的线性表,它们的基本操作是线性表操作的子集,但从数据类型的角度来讲,它们与线性表又有

  • Python数据结构之栈详解

    目录 0.学习目标 1.栈的基本概念 1.1栈的基本概念 1.2栈抽象数据类型 1.3栈的应用场景 2.栈的实现 2.1顺序栈的实现 2.1.1栈的初始化 2.2链栈的实现 2.3栈的不同实现对比 3.栈应用 3.1顺序栈的应用 3.2链栈的应用 3.3利用栈基本操作实现复杂算法 0. 学习目标 栈和队列是在程序设计中常见的数据类型,从数据结构的角度来讲,栈和队列也是线性表,是操作受限的线性表,它们的基本操作是线性表操作的子集,但从数据类型的角度来讲,它们与线性表又有着巨大的不同.本节将首先介绍

  • Python数据结构之双向链表详解

    目录 0. 学习目标 1. 双向链表简介 1.1 双向链表介绍 1.2 双向链表结点类 1.3 双向链表优缺点 2. 双向链表实现 2.1 双向链表的初始化 2.2 获取双向链表长度 2.3 读取指定位置元素 2.4 查找指定元素 2.5 在指定位置插入新元素 2.6 删除指定位置元素 2.7 其它一些有用的操作 3. 双向链表应用 3.1 双向链表应用示例 3.2 利用双向链表基本操作实现复杂操作 0. 学习目标 单链表只有一个指向直接后继的指针来表示结点间的逻辑关系,因此可以方便的从任一结点

  • Python数据结构之循环链表详解

    目录 0. 学习目标 1. 循环链表简介 2. 循环单链表实现 2.1 循环单链表的基本操作 2.2 简单的实现方法 2.3 循环单链表应用示例 2.4 利用循环单链表基本操作实现复杂操作 3. 循环双链表实现 3.1 循环双链表的基本操作 3.2 循环双链表应用示例 0. 学习目标 循环链表 (Circular Linked List) 是链式存储结构的另一种形式,它将链表中最后一个结点的指针指向链表的头结点,使整个链表头尾相接形成一个环形,使链表的操作更加方便灵活.我们已经介绍了单链表和双向

  • Python数据结构之递归方法详解

    目录 1.学习目标 2.递归 2.1递归的基本概念 2.2递归的重要性 2.3递归三原则 2.4递归的应用 3.递归示例 3.1列表求和 3.2汉诺塔(Towers of Hanoi)问题 1.学习目标 递归函数是直接调用自己或通过一系列语句间接调用自己的函数.递归在程序设计有着举足轻重的作用,在很多情况下,借助递归可以优雅的解决问题.本节主要介绍递归的基本概念以及如何构建递归程序. 通过本节学习,应掌握以下内容: 理解递归的基本概念,了解递归背后蕴含的编程思想 掌握构建递归程序的方法 2.递归

  • C++数据结构的队列详解

    目录 前言 1. 队列的概念及结构 2. 队列的实现 2.1 queue.h 2.2 queue.c 2.3 test.c 总结 前言 hello,大家好,这期文章我们来分享数据结构关于队列的知识.希望对大家有所帮助,闲言少叙,现在开始. 1. 队列的概念及结构 队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出FIFO(First In First Out) 入队列:进行插入操作的一端称为队尾 出队列:进行删除操作的一端称为队头 2. 队列的实现 2.1

  • python数据结构之链表详解

    数据结构是计算机科学必须掌握的一门学问,之前很多的教材都是用C语言实现链表,因为c有指针,可以很方便的控制内存,很方便就实现链表,其他的语言,则没那么方便,有很多都是用模拟链表,不过这次,我不是用模拟链表来实现,因为python是动态语言,可以直接把对象赋值给新的变量. 好了,在说我用python实现前,先简单说说链表吧.在我们存储一大波数据时,我们很多时候是使用数组,但是当我们执行插入操作的时候就是非常麻烦,看下面的例子,有一堆数据1,2,3,5,6,7我们要在3和5之间插入4,如果用数组,我

  • c语言数据结构之栈和队列详解(Stack&Queue)

    目录 简介 栈 一.栈的基本概念 1.栈的定义 2.栈的常见基本操作 二.栈的顺序存储结构 1.栈的顺序存储 2.顺序栈的基本算法 3.共享栈(两栈共享空间) 三.栈的链式存储结构 1.链栈 2.链栈的基本算法 3.性能分析 四.栈的应用——递归 1.递归的定义 2.斐波那契数列 五.栈的应用——四则运算表达式求值 1.后缀表达式计算结果 2.中缀表达式转后缀表达式 队列 一.队列的基本概念 1.队列的定义 2.队列的常见基本操作 二.队列的顺序存储结构 1.顺序队列 2.循环队列 3.循环队列

  • C++调用Python基础功能实例详解

    c++调用Python首先安装Python,以win7为例,Python路径为:c:\Python35\,通过mingw编译c++代码. 编写makefile文件,首先要添加包含路径: inc_path += c:/Python35/include 然后添加链接参数: ld_flag += c:/Python35/libs/libpython35.a 在源文件中添加头文件引用: #include "Python.h" Python解释器需要进行初始化,完成任务后需要终止: void s

随机推荐

其他