数据结构之队列 Python实现

队列

队列简称队，它是一种操作受限的线性表，其限制为仅允许在表的一端进行插入，在表的另一端进行删除。可进行插入的一端称为队尾（Rear），可进行删除的一端称为队头（Front），向队列中插入新的元素称为进队，新元素进队后就成为新的队尾元素：从队列中删除元素称为出队，元素出队后，其后继元素就成为新的队头元素。

队列的特点

队列的特点概括起来就是先进先出（FIFO），打个比方，队列就好像开进隧道的一列火车，各节车用就是队中的元素，最先开进隧道的车用总是最先驶出隧道，队列的存储结构可用顺序表和链表来存储队列，队列按存储结构可分为顺序队和链队两种。

顺序队

c语言的顺序队用数组实现，由于数组大小是提前分配好的，所以会出现“假溢出”问题。（在顺序队中，通常让队尾指针rear指向刚进队的元素位置，让队首指针front指向刚出队的元素位置。元素进队的时候，rear要向后移动；元素出队的时候，front也要向后移动，这样经过一系列的出队和进队操作以后，两个指针最终会达到数组末端maxsize-1处）。所以需要循环队列，把数组弄成一个环，让指针沿着环走。

Python的顺序队用列表实现，可以动态增长，类似于C语言的链表，不会出现假溢出问题，所以可以不用实现循环队列的功能。

在这里插入图片描述

队列初始化

queue = []

判断队空

def is_empty(queue):
    return queue==[]

判断队满——无队满情况
入队

def enQueue(queue,x):
	queue.append(x)

出队

def deQueue(queue):
	queue.pop(0)

队列长度

def length(queue):
    return len(queue)

链队

链队就是采用链式存储结构存储队列，这里采用单链表来实现。链队的特点就是不存在队列满上溢的情况。
在这里插入图片描述
下面是代码实现

# 定义链表结点
class Node(object):
    def __init__(self, data, next=None):
        self.data = data
        self.next = next


# 定义一个链队
class lkQueue(object):
    def __init__(self):
        # 初始化队列的头指针和尾指针
        self.front = None
        self.rear = None
        self.length = 0

    # 入队
    def enQueue(self, newitem):
        if self.front == None and self.rear == None:
            self.rear = Node(newitem, None)
            self.front = self.rear
        else:
            self.rear.next = Node(newitem, None)
            self.rear = self.rear.next
        self.length += 1

    # 出队
    def deQueue(self):
        if self.front == None and self.rear == None:
            print("the LinkedQueue is None")
        else:
            temp = self.front
            self.front = self.front.next
            removeitem = temp.data
            if self.rear == temp:
                self.rear = None
        self.length -= 1
        return removeitem
    # 判断队空
    def is_empty(self):
        if self.front == None and self.rear == None:
            print("the LinkedQueue is None")
            return True

    # 打印队列
    def printLkQ(self):
        if self.front == None and self.rear == None:
            print("the LinkedQueue is None")
        else:
            temp = self.front
            while temp != None:
                print(temp.data)
                temp = temp.next
        print("length is ", self.length)

核心操作

# 判断队空
self.front == None and self.rear == None
# 入队
self.rear.next = Node(newitem, None)
self.rear = self.rear.next
# 出队
temp = self.front
self.front = self.front.next

Python内置Queue模块

Python的Queue模块中提供了同步的、线程安全的队列类，包括先入先出队列Queue，后入先出队列（栈）LifoQueue，优先级队列PriorityQueue和双边队列deque。这些队列都实现了锁原语，能够在多线程中直接使用。可以使用队列来实现线程间的同步。

常用方法：

方法	用法说明
put	放数据，Queue.put( )默认有block=True和timeout两个参数。当block=True时，写入是阻塞式的，阻塞时间由timeout确定。当队列q被（其他线程）写满后，这段代码就会阻塞，直至其他线程取走数据。Queue.put（）方法加上 block=False 的参数，即可解决这个隐蔽的问题。但要注意，非阻塞方式写队列，当队列满时会抛出 exception Queue.Full 的异常
get	取数据(默认阻塞),Queue.get(block, timeout)获取队列，timeout等待时间
empty	如果队列为空，返回True,反之False
full	如果队列满了，返回True,反之False
qsize	显示队列中真实存在的元素长度
maxsize	最大支持的队列长度,使用时无括号
join	实际上意味着等到队列为空，再执行别的操作
task_done	在完成一项工作之后，Queue.task_done()函数向任务已经完成的队列发送一个信号

from queue import Queue #先进先出队列

q = Queue(maxsize=5)
q.put(1) #队尾入队
q.put(2) #队尾入队
q.put(3) #队尾入队
a = q.get() #队首出队
print(a)

>>> 1

from queue import LifoQueue #栈

lq = LifoQueue(maxsize=5)
lq.put(1) #元素入栈
lq.put(2) #元素入栈
lq.put(3) #元素入栈
a = q.get() #元素出栈
print(a)

>>> 3

————————————————
参考链接：
1、https://blog.csdn.net/weixin_43533825/article/details/89155648
2、https://blog.csdn.net/brucewong0516/article/details/84025027

原文链接：https://blog.csdn.net/weixin_51760563/article/details/119862571