数据结构 4. 队列_# 如果head节点的右边不为none # 说明队列中已经有元素了 # 就执行下列的操作-程序员宅基地

技术标签: Leetcode刷题  

一、队列

1. 队列的定义

队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。队列中没有元素时,称为空队列。
队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队,从队列中删除一个队列元素称为出队。因为队列只允许在一端插入,在另一端删除,所以只有最早进入队列的元素才能最先从队列中删除,故队列又称为先进先出(FIFO—first in first out)线性表。

队列分为顺序存储和链式存储两种方式。

顺序存储就是用数组实现,比如有一个n个元素的队列,数组下标0的一端是队头,入队操作就是通过数组下标一个个顺序追加,不需要移动元素,但是如果删除队头元素,后面的元素就要往前移动,对应的时间复杂度就是O(n),性能自然不高。

为了提高出队的性能,就有了循环队列,什么是循环队列呢?就是有两个指针,front指向队头,rear指向对尾元素的下一个位置,元素出队时front往后移动,如果到了对尾则转到头部,同理入队时rear后移,如果到了对尾则转到头部,这样通过下标front出队时,就不需要移动元素了。

在这里插入图片描述
同时规定,当队列为空时,front和rear相等,那么队列什么时候判断为满呢?按照循环操作rear依次后移,然后再从头开始,也是出现rear和front相等时,队列满。这样跟队列空的情况就相同了,为了区分这种情况,规定数组还有一个空闲单元时,就表示队列已满,因为rear 可能在front后面,也可能循环到front前面,所以队列满的条件就变成了(rear+1)%maxsize = front ,同时队列元素个数的计算就是(rear -front+maxsize)%maxsize。

循环队列要事先申请好空间,整个过程都不能释放,而且要有固定的长度,如果长度事先无法估计,这种方式显然不够灵活;所以就引入了链式存储队列,其实就是线性表的单链表,只是它只能对尾进,队头出。并且规定队头指针指向链队列的头结点,对尾指针指向终端节点,当队列为空时,front和rear都指向头结点。

入队操作,就是在链表尾部插入结点;出队操作就是头结点的后继结点出队,然后将头结点的后继后移。如果最后除了头结点外,只剩一个元素了,就把rear也指向头结点。

在这里插入图片描述

2. 队列的实现

2.1 用数组实现一个顺序队列

class QueueUnderflow(ValueError):
    pass

class SQueue():
    def __init__(self, init_len = 8):
        self._len = init_len          # 存储区长度
        self._elems = [0]*init_len    # 元素存储
        self._head = 0                # 表头元素下标
        self._num = 0                 # 元素个数
        
    def is_empty(self):               # 判断队列是否为空
        return self._num == 0
    
    def peek(self):
        if self._num ==0:
            raise QueueUnderflow
        return self._elems[self._head]
    
    def dequeue(self):                # 删除队首元素
        if self._num == 0:
            raise QueueUnderflow
        e = self._elems[self._head]
        self._head = (self._head+1) % self._len
        self._num -= 1
        return e
    
    def enqueue(self, e):             # 在队尾插入元素
        if self._num == self._len:
            self.__extend()
        self._elems[(self._head+self._num) % self._len] = e
        self._num += 1
        
    def __extend(self):               # 扩展队列
        old_len = self._len 
        self._len *=2
        new_elems = [0]*self._len
        for i in range(old_len):
            new_elems[i] = self._elems[(self._head+1)%old_len]
        self._elems, self._head = new_elems, 0

2.2 用链表实现一个链式队列

class Head(object):
    def __init__(self):
        self.left = None
        self.right = None

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

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

    def enqueue(self
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_41725746/article/details/90239434

智能推荐

如果有人能力不如你工资比你高怎么看?_比你菜工资比你高-程序员宅基地

文章浏览阅读5.1k次,点赞3次,收藏3次。你在公司里工作,如果同办公室里的一个人,能力没有你强,但工资却高于你,你会不会有想法,心理能平衡吗?1. 错误回答:1) 我当然不平衡,那我还干的什么意思?2) 如果他的能力比我强,我不会有想法。如果没有我强,我肯定心理不平衡。(路健就是这样回答的)3) 如果公司对待员工是这样的不公平,肯定企业文化有问题,这样的公司只有走人。2. 正确回答:(别忘了换位思考原则)工资是员工最敏感的问题,公司一般都会尽量处理好,如果那个同事的能力不如我,工资还高于我,肯定是他在其他方面强于我。或者,他能为公司解决_比你菜工资比你高

获取对话框当前cfont_VC调用系统字体对话框-程序员宅基地

文章浏览阅读474次。1、通过MFC类调用字体对话框2、通过win32API函数调用字体对话框通过MFC类调用字体对话框CFontDialog构造函数CFontDialog(LPLOGFONTlplfInitial=NULL,DWORDdwFlags=CF_EFFECTS|CF_SCREENFONTS,CDC*pdcPrinter=NULL,CWnd*pParentWnd=NULL..._vc++如何获取当前计算中的系统字体

《树莓派Python编程入门与实战》——3.2 检查你的Python环境-程序员宅基地

文章浏览阅读304次。本节书摘来异步社区《树莓派Python编程入门与实战》一书中的第3章,第3.2节,作者:【美】Richard Blum,更多章节内容可以访问云栖社区“异步社区”公众号查看3.2 检查你的Python环境树莓派Python编程入门与实战Raspbian发行版默认安装了Python第三版环境和一些必要的工具。下面是预装了的Python功能。Python..._怎么查树莓派是否有python环境?

工具IDEA 配置springboot+maven项目-程序员宅基地

文章浏览阅读81次。工具IDEA 配置springboot+maven项目 首先安装IDEA,至于怎么安装就不介绍了。。第一步 配置maven环境 首先安装maven,先在网上下载一个maven包。在IDEA的settings中Maven设置 点击USer settings file 文件夹正常的是空白 如图找到你下载的maven文件夹,引入setti..._maven项目怎么配置springboot

GSL 系列 5 — 向量和矩阵 2 — 向量 (vector)_gsl_vector *-程序员宅基地

文章浏览阅读1.3k次。文章目录0 写在前面1 向量 (vector)0 写在前面因为向量是构建于块之上,请先理解块,参见:GSL 系列 5 — 向量和矩阵 1 — 块 (block)1 向量 (vector)向量建构于块之上,添加了对块的切片描述,向量切片必须是内存空间中一组等间隔的元素,不同的向量可以创建于一个块之上,定义如下:// gsl_vector_double.htypedef struct {..._gsl_vector *

c语言 之求 Fibionacci 数列的前n个数_求fib序列c语言-程序员宅基地

文章浏览阅读1.9k次。Fibionacci数列有如下特点:前两个数都为1,从第三个数开始,该数是前两个数之和。即:F1=1;(n=1)F2=1;(n=2)Fn=Fn-1+Fn-2;(n>2)下面给出几种求法:解法一:#include int fib(int n){ int fib1 =1; int fib2 =1; int fib = 1; int i = 0; while (_求fib序列c语言

随便推点

浅析LiveMedia智能视频网关的AI识别技术及应用场景_.net ai 识别视频直播的话语-程序员宅基地

文章浏览阅读239次。LiveMedia智能视频边缘网关,支持对多路网络IPC和NVR设备的高清视频流进行实时智能分析。通过将网络摄像机、NVR、编码器等视频源设备统一集中接入和汇聚管理,对接入的多路高清视频流进行人、车、物、行为等实时检测与分析,结合硬件中内置的多种AI算法,实现人脸识别/检测、车辆识别/检测、目标检测、行为识别等目的,可对异常行为事件进行告警与提醒,支持对接视频结构化数据平台、大数据综合分析平台等。_.net ai 识别视频直播的话语

Kinetis KL8x 使用eDMA模块接收串口数据_site: csdn.net edma循环-程序员宅基地

文章浏览阅读1.6k次。飞思卡尔的芯片KL系列Cortex-M0+内核的,其他的应该可以通用,大体一致,之前在KL25上用过,这次是KL81,我对比两者使用类似,就是某些寄存器不同罢了正文开始:需要用LPUART接收上层接口的数据,比较大,而且大小不固定,之前用FIFO来接收,但是遇到收发错乱,很不稳定,故使用eDMA来接收#include "fsl_port_hal.h"#include "fsl_dev_site: csdn.net edma循环

OpenSSL杂记(CA证书)-程序员宅基地

文章浏览阅读896次。OpenSSL和OpenSSHOpenSSH只允许白名单的用户登录1、限制前:[email protected]'s password: [ww@qq ~]$ exitlogoutConnection to 10.201.106.129 closed.[root@zz ~]# ssh [email protected]@10.201.106.129's password: ...

GPIO 口的输入,输出模式及其说明_gpio_mode_in-程序员宅基地

文章浏览阅读4.2w次,点赞65次,收藏351次。GPIO端口各种模式的区别(1)GPIO_Mode_AIN 模拟输入(2)GPIO_Mode_IN_FLOATING 浮空输入(3)GPIO_Mode_IPD 下拉输入(4)GPIO_Mode_IPU 上拉输入(5)GPIO_Mode_Out_OD 开漏输出(6)GPIO_Mode_Out_PP 推挽输出(7)GPIO_Mode_AF_OD 复用开漏输出(8)GPIO_Mode_A..._gpio_mode_in

CSS的三种引入方式_css 的三种引入方式-程序员宅基地

文章浏览阅读3k次,点赞3次,收藏14次。CSS的引入方式共有三种:行内样式、内部样式表、外部样式表。_css 的三种引入方式

javascript用js简单的实现电子时钟_4、编写程序,实现电子时钟效果,要求每隔1秒获取一次当前时间,并提供一个按钮控制-程序员宅基地

文章浏览阅读3.6k次,点赞3次,收藏12次。<!DOCTYPEhtml><htmllang="en"><head><metacharset="UTF-8"><metaname="viewport"content="width=device-width,initial-scale=1.0"><title>Document</title><!--给div一个简单样式--><..._4、编写程序,实现电子时钟效果,要求每隔1秒获取一次当前时间,并提供一个按钮控制