当前位置：物联沃-IOTWORD物联网 > 技术教程 > 数据结构之队列（python）
代码收藏家代码收藏家 技术教程

数据结构之队列（python）

华子目录

  • 1.队列存储结构
  • 1.1队列基本介绍
  • 1.2队列的实现方式
  • 2.顺序队列
  • 2.1顺序队列的介绍
  • 2.2顺序队列的简单实现
  • 2.3代码实现
  • 3.链式队列和基本操作
  • 3.1链式队列数据入队
  • 3.2链式队列数据出队
  • 3.3队列的链式表示和实现

    • 1.队列存储结构

    1.1队列基本介绍

  • 队列的两端都"开口"，要求数据只能从一端进，从另一端出，如图 1 所示：

  • 进数据的一端为 “队尾”，出数据的一端为 “队头”，数据元素进队列的过程称为 “入队”，出队列的过程称为 “出队”。
  • 队列中数据的进出要遵循 “先进先出” 的原则，即最先进队列的数据元素，同样要最先出队列。
  • 拿图1中的队列来说，从数据在队列中的存储状态可以分析出，元素1 最先进队，其次是元素2，最后是元素3。此时如果将元素3出队，根据队列 “先进先出” 的特点，元素1 要先出队列，元素2 再出队列，最后才轮到元素3 出队列。
  • 因此，数据从表的一端进，从另一端出，且遵循 “先进先出” 原则的线性存储结构就是队列。
  • 实际生活中，队列的应用随处可见，比如排队买XXX、医院的挂号系统等，采用的都是队列结构。

    • 1.2队列的实现方式

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

  • 顺序队列：在顺序表的基础上实现的队列结构
  • 链队列：在链表的基础上实现的队列结构

    • 2.顺序队列

    2.1顺序队列的介绍

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

  • 我们知道，队列具有以下两个特点：
  • 数据从队列的一端进，另一端出
  • 数据的入队和出队遵循"先进先出"的原则

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

    2.2顺序队列的简单实现

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

  • 由于顺序队列初始状态没有存储任何元素，因此 top指针和 rear指针重合，且由于顺序队列底层实现靠的是数组，因此 top 和 rear 实际上是两个变量，它的值分别是队头元素和队尾元素所在数组位置的下标。
  • 在图1 的基础上，当有数据元素进队列时，对应的实现操作是将其存储在指针rear 指向的数组位置，然后 rear+1；当需要队头元素出队时，仅需做 top+1 操作。

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


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

    2.3代码实现

    实现基本功能：

  • 初始化队列
  • 判断队列是否为空
  • 返回队头元素
  • 返回队列的长度
  • 入队 : 添加元素到队尾
  • 出队 : 删除队头元素
  • 遍历队列
  • 清空队列
    • # 本次顺序队列定义及相关函数较多使用python自身所带的列表和函数
class Queue:
    #队列初始化
    def __init__(self):
        self.items = []

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

    #元素入队
    def enter_queue(self, item):
        self.items.insert(0, item)

    #队首元素出队
    def go_queue(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.enter_queue(5)
    q.enter_queue(10)
    q.enter_queue(11)
    print("入队后队内元素为：", q.display())
    print("---------------------")
    print("当前队首元素为：", q.getTop())
    print("---------------------")
    print("出队前队内元素为：", q.display())
    q.go_queue()
    print("出队后队内元素为：", q.display())
    print("---------------------")
    print("当前队列长度为：", q.size())
    print("---------------------")
    print("清空前队内元素为：", q.display())
    q.clear()
    print("清空后队内元素为：", q.display())

    ---------------------
初始化后的队列： <__main__.Queue object at 0x0000017D90EB8460>
---------------------
当前队列是否为空： True
---------------------
入队前队内元素为： []
入队后队内元素为： [11, 10, 5]
---------------------
当前队首元素为： 5
---------------------
出队前队内元素为： [11, 10, 5]
出队后队内元素为： [11, 10]
---------------------
当前队列长度为： 2
---------------------
清空前队内元素为： [11, 10]
清空后队内元素为： []

    3.链式队列和基本操作

  • 使用链表实现的队列存储结构
  • 需要创建两个指针（命名为 top 和 rear）分别指向链表中队列的队头元素和队尾元素，如图 1 所示：

  • 图1 所示为链式队列的初始状态，此时队列中没有存储任何数据元素，因此 top 和 rear 指针都同时指向头节点。
  • 在创建链式队列时，强烈建议初学者创建一个带有头节点的链表，这样实现链式队列会更简单。

    • 3.1链式队列数据入队

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

  • 将该数据元素用节点包裹，例如新节点名称为 elem；
  • 与 rear指针指向的节点建立逻辑关系，即执行 rear->next=elem；
  • 最后移动 rear指针指向该新节点，即 rear=elem；

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

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

    3.2链式队列数据出队

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

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

  • 通过 top 指针直接找到队头节点，创建一个新指针p 指向此即将出队的节点；
  • 将 p 节点（即要出队的队头节点）从链表中摘除；
  • 释放节点p，回收其所占的内存空间；

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

    3.3队列的链式表示和实现

    实现基本功能：

  • 初始化队列
  • 判断队列是否为空
  • 返回队头元素
  • 返回队列的长度
  • 入队: 添加元素到队尾
  • 出队: 删除队头元素
  • 遍历队列
  • 清空队列
    • '''
1. 队列特点：先进先出，队尾入队操作，队头出队操作
2. 使用单链表实现：尾部添加节点(入队),头部删除节点(出队)操作
3. 这是一个带有头节点的队列，front指针始终指向头节点
'''

#定义链式队列节点
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 is_empty(self):
        return 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 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


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("-----------------------------")

    -----------------------------
初始化的链式队列： <__main__.Queue object at 0x000001BA943A9A00>
-----------------------------
当前队列是否为空： True
-----------------------------
入队前队列元素为：队列为空
入队后队列元素为：1 47 tr 
-----------------------------
当前队列长度为： 3
-----------------------------
当前队列头部元素为： 1
-----------------------------
出队前队列元素为：1 47 tr 
出队后队列元素为：47 tr 
-----------------------------
当前队列是否为空： False
-----------------------------
清空后队列元素为：47 tr 
出队后队列元素为：队列为空
-----------------------------

    作者：^～^前行者～～～

    物联沃分享整理
    物联沃-IOTWORD物联网 » 数据结构之队列（python）

    代码收藏家 普通

    分享到：

    相关推荐

    发表回复