【Python数据结构系列】☀️《队列(顺序队列、链式队列、双端队列)》——知识点讲解+代码实现☀️

天道Vax的时间宝藏

发布于 2021-08-12 14:31:47

9430

发布于 2021-08-12 14:31:47

灵魂拷问：为什么要学数据结构？数据结构，直白地理解，就是研究数据的存储方式。数据存储只有一个目的，即为了方便后期对数据的再利用。因此，数据在计算机存储空间的存放，决不是胡乱的，这就要求我们选择一种好的方式来存储数据，而这也是数据结构的核心内容。可以说，数据结构是一切编程的基本。学习数据结构是学习一种思想：如何把现实问题转化为计算机语言的表示。对于学计算机的朋友来说，学习数据结构是基本功。而对于非计算机专业，但是未来想往数据分析、大数据方向发展、或者在Python的使用上能有一个大的跨越的朋友来说，学习数据结构是一种非常重要的逻辑思维能力的锻炼，在求职、职业发展、问题解决等方面都能有潜移默化的大帮助。

数据结构之栈和队列

1. 队列存储结构

1.1 队列的基本介绍

队列，和栈一样，也是一种对数据的"存"和"取"有严格要求的**线性存储结构。

与栈结构不同的是，队列的两端都"开口"，要求数据只能从一端进，从另一端出，如图 1 所示：

通常，称进数据的一端为 “队尾”，出数据的一端为 “队头”，数据元素进队列的过程称为 “入队”，出队列的过程称为 “出队”。

不仅如此，队列中数据的进出要遵循 “先进先出” 的原则，即最先进队列的数据元素，同样要最先出队列。拿图 1 中的队列来说，从数据在队列中的存储状态可以分析出，元素 1 最先进队，其次是元素 2，最后是元素 3。此时如果将元素 3 出队，根据队列 “先进先出” 的特点，元素 1 要先出队列，元素 2 再出队列，最后才轮到元素 3 出队列。

注：栈和队列不要混淆，栈结构是一端封口，特点是"先进后出"；而队列的两端全是开口，特点是"先进先出"。

因此，数据从表的一端进，从另一端出，且遵循 “先进先出” 原则的线性存储结构就是队列。

1.2 队列的实现方式

队列存储结构的实现有以下两种方式：

（1）顺序队列：在顺序表的基础上实现的队列结构；

（2）链队列：在链表的基础上实现的队列结构；

两者的区别仅是顺序表和链表的区别，即在实际的物理空间中，数据集中存储的队列是顺序队列，分散存储的队列是链队列。

实际生活中，队列的应用随处可见，比如排队买XXX、医院的挂号系统等，采用的都是队列的结构。

拿排队买票来说，所有的人排成一队，先到者排的就靠前，后到者只能从队尾排队等待，队中的每个人都必须等到自己前面的所有人全部买票成功并从队头出队后，才轮到自己买票。这是典型的队列结构。

2. 顺序队列

2.1 顺序队列的基本介绍

顺序队列，即采用顺序表模拟实现的队列结构。

　　我们知道，队列具有以下两个特点：

　　　(1) 数据从队列的一端进，另一端出；

　　　(2) 数据的入队和出队遵循"先进先出"的原则；

　　因此，只要使用顺序表按以上两个要求操作数据，即可实现顺序队列。首先来学习一种最简单的实现方法。

2.2 顺序队列的简单实现

由于顺序队列的底层使用的是数组，因此需预先申请一块足够大的内存空间初始化顺序队列。除此之外，为了满足顺序队列中数据从队尾进，队头出且先进先出的要求，我们还需要定义两个指针（top 和 rear）分别用于指向顺序队列中的队头元素和队尾元素，如图 1 所示：

由于顺序队列初始状态没有存储任何元素，因此 top 指针和 rear 指针重合，且由于顺序队列底层实现靠的是数组，因此 top 和 rear 实际上是两个变量，它的值分别是队头元素和队尾元素所在数组位置的下标。

在图 1 的基础上，当有数据元素进队列时，对应的实现操作是将其存储在指针 rear 指向的数组位置，然后 rear+1；当需要队头元素出队时，仅需做 top+1 操作。

例如，在图 1 基础上将 {1,2,3,4} 用顺序队列存储的实现操作如图 2 所示：

在图 2 基础上，顺序队列中数据出队列的实现过程如图 3 所示：

代码实现：队列的顺序表示和实现（难度：★）

实现基本功能：（包括但不限于，可以根据自己能力继续扩展）

（1）初始化队列

（2）判断队列是否为空

（3）返回队头元素

（4）返回队列的长度

（5）入队 : 添加元素到队尾

（6）出队 : 删除队头元素

（7）遍历队列

（8）清空队列

【注】：栈是先进后出，后进先出，队列是先进先出，后进后出！

#!/usr/bin/env python
# -*- coding: utf-8 -*- 
# @Time : 2021/7/27 16:09 
# @Author : vaxtiandao
# @File : ds_queue.py
# coding=utf-8

"""
本次顺序队列定义及相关函数较多使用Python自身所带的列表的函数
"""
class Queue(object):
    """队列"""
    # 队列初始化
    def __init__(self):
        self.items = []

    # 判断队列是否为空
    def is_empty(self):
        return self.items == []

    # 元素入队
    def enqueue(self, item):
        """进队列"""
        self.items.insert(0,item)

    # 队首元素出队
    def dequeue(self):
        """出队列"""
        return self.items.pop()

    # 返回队列长度
    def size(self):
        """返回大小"""
        return len(self.items)

    # 清空队列
    def clear(self):
        self.items.clear()

    # 获取队首元素
    def getTop(self):
        return self.items[self.size()-1]

    # 遍历队列
    def display(self):
        return self.items

if __name__ == "__main__":
    q = Queue()
    print("---------------------")
    print("初始化后的队列：", q)
    print("---------------------")
    print("当前队列是否为空：", q.is_empty())
    print("---------------------")
    print("入队前队内元素为：", q.display())
    q.enqueue(5)
    q.enqueue(9)
    q.enqueue(14)
    print("入队后队内元素为：", q.display())
    print("---------------------")
    print("当前队首元素为：", q.getTop())
    print("---------------------")
    print("出队前队内元素为：", q.display())
    q.dequeue()
    print("出队后队内元素为：", q.display())
    print("---------------------")
    print("当前队列长度为：", q.size())
    print("---------------------")
    print("清空前队内元素为：", q.display())
    q.clear()
    print("清空后队内元素为：", q.display())
    print("---------------------")

实现效果：

3. 链式队列及基本操作

3.1 链式队列的基本介绍

链式队列，简称"链队列"，即使用链表实现的队列存储结构。

链式队列的实现思想同顺序队列类似，只需创建两个指针（命名为 top 和 rear）分别指向链表中队列的队头元素和队尾元素，如图 1 所示:

图 1 所示为链式队列的初始状态，此时队列中没有存储任何数据元素，因此 top 和 rear 指针都同时指向头节点。

在创建链式队列时，强烈建议初学者创建一个带有头节点的链表，这样实现链式队列会更简单。

3.2 链式队列数据入队

链队队列中，当有新的数据元素入队，只需进行以下 3 步操作：

（1）将该数据元素用节点包裹，例如新节点名称为 elem；

（2）与 rear 指针指向的节点建立逻辑关系，即执行 rear->next=elem；

（3）最后移动 rear 指针指向该新节点，即 rear=elem；

由此，新节点就入队成功了。

例如，在图 1 的基础上，我们依次将 {1,2,3} 依次入队，各个数据元素入队的过程如图 2 所示:

3.3 链式队列数据出队

当链式队列中，有数据元素需要出队时，按照 “先进先出” 的原则，只需将存储该数据的节点以及它之前入队的元素节点按照原则依次出队即可。这里，我们先学习如何将队头元素出队。

　　链式队列中队头元素出队，需要做以下 3 步操作：

(1) 通过 top 指针直接找到队头节点，创建一个新指针 p 指向此即将出队的节点；

(2) 将 p 节点（即要出队的队头节点）从链表中摘除；

(3) 释放节点 p，回收其所占的内存空间；

　　例如，在图 2b) 的基础上，我们将元素 1 和 2 出队，则操作过程如图 3 所示：

代码实现：队列的链式表示和实现（难度：★★）

实现基本功能：（跟顺序队列的实现功能一样，只不过改成链表形式）

（1）初始化队列

（2）判断队列是否为空

（3）返回队头元素

（4）返回队列的长度

（5）入队 : 添加元素到队尾

（6）出队 : 删除队头元素

（7）遍历队列

（8）清空队列

【注】：栈是先进后出，后进先出，队列是先进先出，后进后出！

链式队列的表示及实现，用Python编程完成！

#!/usr/bin/env python
# -*- coding: utf-8 -*- 
# @Time : 2021/7/28 8:10 
# @Author : vaxtiandao
# @File : ds_liqueue.py

'''
1. 队列特点：先进先出，队尾入队操作，队头出队操作
2. 使用单链表实现：尾部添加节点(入队),头部删除节点(出队)操作
'''


# 定义链式队列节点
class Node:
    def __init__(self, value):
        self.data = value
        self.next = None


# 定义队列函数
class Queue:

    # 队列初始化
    def __init__(self):
        self.front = Node(None)
        self.rear = self.front

    # 元素入队
    def enQueue(self, element):
        n = Node(element)
        self.rear.next = n
        self.rear = n

    # 队列元素出队
    def deQueue(self):
        if self.is_empty():
            print('队列为空')
            return
        temp = self.front.next
        self.front.next = self.front.next.next
        if self.rear == temp:
            self.rear = self.front
        del temp

    # 获取队首元素
    def gettop(self):
        if self.is_empty():
            print('队列为空')
            return
        return self.front.next.data

    # 判断队列是否为空
    def is_empty(self):
        return self.rear == self.front

    # 遍历队列
    def display(self):
        if self.is_empty():
            print('队列为空')
            return
        cur = self.front.next
        while cur != None:
            print(cur.data, end=" ")
            cur = cur.next
        print()

    # 清空队列
    def clear(self):
        while self.front.next != None:
            temp = self.front.next
            self.front.next = temp.next
        self.rear = self.front

    # 返回队列长度
    def size(self):
        cur = self.front.next
        count = 0
        while cur != None:
            count += 1
            cur = cur.next
        return count


if __name__ == '__main__':
    queue = Queue()
    print("-----------------------------")
    print("初始化的链式队列：", queue)
    print("-----------------------------")
    print("当前队列是否为空：", queue.is_empty())
    print("-----------------------------")
    print("入队前队列元素为：", end="")
    queue.display()
    queue.enQueue(1)
    queue.enQueue(47)
    queue.enQueue("tr")
    print("入队后队列元素为：", end="")
    queue.display()
    print("-----------------------------")
    print("当前队列长度为：", queue.size())
    print("-----------------------------")
    print("当前队列头部元素为：", queue.gettop())
    print("-----------------------------")
    print("出队后队列元素为：", end="")
    queue.display()
    queue.deQueue()
    print("出队后队列元素为：", end="")
    queue.display()
    print("-----------------------------")
    print("当前队列是否为空：", queue.is_empty())
    print("-----------------------------")
    print("清空后队列元素为：", end="")
    queue.display()
    queue.clear()
    print("出队后队列元素为：", end="")
    queue.display()
    print("-----------------------------")

实现效果：

4. 双端队列

4.1 定义

双端队列（deque）是指允许两端都可以进行入队和出队操作的队列，其元素的逻辑结构仍是线性结构，将队列的两端分别称为前端和后端，两端都可以入队和出队，使用双链表实现双端队列。deque 是 “double ended queue” 的简称。

4.2 双端队列的原型

对于双端队列的原型，可以还用排队的例子来说明，这里主要以此说明从队头入队和从队尾出队的例子：

（1）如果一个排在队头的顾客进了餐厅却发现暂无空桌，则其再次回到队头的行为就相当于从队头入队操作；

（2）如果一个排在队尾的顾客嫌队伍太长离开了队伍，则其行为就相当于从队尾出队操作。

4.3 双端队列的ADT

为了能够提供上述双端队列所支持的所有操作，则其ADT必然需要至少包含下列4个方法：

（1）D.add_first(e)：在队头插入元素e；

（2）D.add_last(e)：在队尾插入元素e；

（3）D.delete_first()：删除并返回队头元素且当双端队列为空时抛出异常；

（4）D.delete_last()：删除并返回队尾元素且当双端队列为空时抛出异常。

代码实现：双端队列的顺序表示和实现（难度：★★）

实现基本功能：（包括但不限于，可以根据自己能力继续扩展）

（1）同顺序队列和链式队列一样（8个函数均要实现，不同之处在于，见下）

（2）队头入队 : 添加元素到队头

（3）队尾入队 : 添加元素到队尾

（4）队头出队 : 删除队头元素

（5）队尾出队 : 删除队尾元素

【注】：双端队列是指首尾都能进出元素的线性数据结构。尽管进出是任意的，但数据在双端队列中的排列顺序却是不能改变的，这一点与普通队列是一样的;

**双端队列的表示及实现，**用Python编程完成！

#!/usr/bin/env python
# -*- coding: utf-8 -*- 
# @Time : 2021/7/28 9:28 
# @Author : vaxtiandao
# @File : dou_queue.py

class Queue(object):
    def __init__(self):
        # 队列初始化 
        self.items = []

    # 判断队列是否为空
    def is_empty(self):
        # 判断是否为空
        return len(self.items) == 0

    # 将原来的push、pop两个函数改为了一下四个函数
    # 分别用于实现头部插入、尾部插入、头部删除、尾部删除
    # 队首入队
    def en_front(self, item):
        self.items.insert(0, item)

    # 队尾入队
    def en_back(self, item):
        self.items.append(item)

    # 队首出队
    def de_front(self):
        print("队首{}出队!".format(self.items[0]))
        self.items.pop(0)

    # 队尾出队
    def de_back(self):
        print("队尾{}出队!".format(self.items[self.size()-1]))
        self.items.pop()

    # 查看队列长度
    def size(self):
        # 返回队列长度
        return len(self.items)

    # 遍历队列
    def display(self):
        if self.is_empty():
            print("队列为空", end=' ')
        # 遍历
        for i in self.items:
            print(i, end=' ')
        print('')

    # 清空队列
    def clear(self):
        self.items = []

    # 获取队首元素
    def getTop(self):
        return self.items[0]

    # 获取队尾元素
    def getTail(self):
        return self.items[self.size()-1]


if __name__ == '__main__':
    # 初始化一个队列对象
    q = Queue()
    print("------------------------")
    print("初始化双端队列：", q)
    print("------------------------")
    print("当前队列是否为空：", q.is_empty())
    print("------------------------")
    print("入队前对内元素为：", end="")
    q.display()
    for i in range(5):
        if i % 2 == 0:
            q.en_front(i)
        else:
            q.en_back(i)
    print("入队后对内元素为：", end="")
    q.display()      # 打印出0-5
    print("------------------------")
    print("当前队列长度为：", q.size())
    print("------------------------")
    print("出队前对内元素为：", end="")
    q.display()
    q.de_front()
    q.de_back()     # 进行2次出队的操作
    print("出队后对内元素为：", end="")
    q.display()
    print("------------------------")
    print("当前队首元素为：", q.getTop())
    print("------------------------")
    print("当前队尾元素为：", q.getTail())
    print("------------------------")
    print("当前队列长度为：", q.size())
    print("------------------------")
    print("清空前对内元素为：", end="")
    q.display()
    q.clear()
    print("清空后对内元素为：", end="")
    q.display()
    print("------------------------")

实现效果：

5. 队列的应用

应用1：回文词检验

回文词检查是数据结构中的常见任务，这一任务可以应用双端队列直观有效地完成。将待检查的字符串按顺序载入队列，首尾两侧弹出并比较，出现不一致时则判断为不是回文数。当队列为空或只剩一个元素是可以判断为回文数。

测试案例：

　　案例1：abcgcba

　　案例2：refer

　　案例3：reference

运行结果：

代码实现

#!/usr/bin/env python
# -*- coding: utf-8 -*- 
# @Time : 2021/7/28 10:39 
# @Author : vaxtiandao
# @File : ds_palCheck.py

class Queue(object):
    def __init__(self):
        # 队列初始化
        self.items = []

    # 判断队列是否为空
    def is_empty(self):
        # 判断是否为空
        return len(self.items) == 0

    # 将原来的push、pop两个函数改为了一下四个函数
    # 分别用于实现头部插入、尾部插入、头部删除、尾部删除
    # 队首入队
    def en_front(self, item):
        self.items.insert(0, item)

    # 队尾入队
    def en_back(self, item):
        self.items.append(item)

    # 队首出队
    def de_front(self):
        self.items.pop(0)
        return self.items[0]

    # 队尾出队
    def de_back(self):
        self.items.pop()
        return self.items[self.size() - 1]

    # 查看队列长度
    def size(self):
        # 返回队列长度
        return len(self.items)

    # 遍历队列
    def display(self):
        if self.is_empty():
            print("队列为空", end=' ')
        # 遍历
        for i in self.items:
            print(i, end=' ')
        print('')

    # 清空队列
    def clear(self):
        self.items = []

    # 获取队首元素
    def getTop(self):
        return self.items[0]

    # 获取队尾元素
    def getTail(self):
        return self.items[self.size() - 1]


def palChecker(aString):
    de = Queue()

    for i in aString:
        de.en_back(i)

    stillEqual = True

    while de.size() > 1 and stillEqual:
        first = de.de_front()
        last = de.de_back()
        if first != last:
            stillEqual = False

    return stillEqual


def check(stro):
    if palChecker(stro):
        print(stro, "是一个回文词！")
    else:
        print(stro, "不是一个回文词！")


if __name__ == "__main__":
    s = ['abcgcba', 'refer', 'reference']
    for i in range(3):
        check(s[i])

实现效果：