【二】一起算法---队列:STL queue、手写循环队列、双端队列和单调队列、优先队列

这篇具有很好参考价值的文章主要介绍了【二】一起算法---队列:STL queue、手写循环队列、双端队列和单调队列、优先队列。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

纸上得来终觉浅,绝知此事要躬行。大家好!我是霜淮子,欢迎订阅我的专栏《算法系列》。

学习经典算法和经典代码,建立算法思维;大量编码让代码成为我们大脑的一部分。

⭐️已更系列

 1、基础数据结构

       1.1、链表➡传送门

       1.2、队列➡本章

专栏直达《算法系列》

目录

前言

机器翻译(洛谷P1540)

问题描述:

输入:

输出:

1.2、队列

1.2.1、STL queue

1.2.2、手写循环队列

1.2.3、双端队列和单调队列

1.2.4、优先队列


前言

机器翻译(洛谷P1540)

问题描述:

假设内存中有 MM 个单元,每单元能存放一个单词和译义。每当软件将一个新单词存入内存前,如果当前内存中已存入的单词数不超过 M-1M−1,软件会将新单词存入一个未使用的内存单元;若内存中已存入 MM 个单词,软件会清空最早进入内存的那个单词,腾出单元来,存放新单词。

假设一篇英语文章的长度为 NN 个单词。给定这篇待译文章,翻译软件需要去外存查找多少次词典?假设在翻译开始前,内存中没有任何单词。

输入:

共 22 行。每行中两个数之间用一个空格隔开。

第一行为两个正整数 M,NM,N,代表内存容量和文章的长度。

第二行为 NN 个非负整数,按照文章的顺序,每个数(大小不超过 10001000)代表一个英文单词。文章中两个单词是同一个单词,当且仅当它们对应的非负整数相同。

输出:

一个整数,为软件需要查词典的次数。

1.2、队列

队列中得数据存取方式是“先进先出”,只能向队尾插入数据,从对头移出数据。在我们的日常生活中很常见,比如食堂打饭的队伍,先到先服务。队列有两种实现的方式:链队列和循环队列,

链队列可以看作单链表的一种特殊情况,用指针把各个节点连接在一起。

循环队列是一种顺序表,使用一组连续的存储单元依次存放队列元素,用两个指针head和tail分别指示对头元素和队尾元素,当head和tail走到底的时,下一步回到开始的位置,从而在这组连续空间内循环。循环队列能解决溢出问题,如果不循环,head和tail一直往前走,head和tali都一直往前走,可能会走到存储空间之外,导致溢出。

队列的主要问题是查找慢,需要从头到尾一个个查找。在某些情况下可以使用优先队列,让优先级最高(最大的数或者最小的数)先出队列。

队列的代码很容易实现,如果使用简单环境,最简单的手写队列代码如下:

cont int N =le5;    //定义队列大小,确保够用
int que[N],head,tail;        //对头队尾指针,队列大小为tail-head+1
head++;                  //弹出对头,注意head<=tail
que[head];      //读取对头数据
que[++tail]=data; //数据data入队,尾指针加1,注意不能溢出 
  • 这个队列不是循环的,tail可能超过N,导致溢出

1.2.1、STL queue

STL queue的主要操作如下

(1)、queue<Type>q:定义队列,Type为数据类型,如int、float、char等。

(2)、q.push(item):把item放进队列。

(3)、q.front( ):返回队首元素,但不会删除。

(4)、q.pop( ):删除对首元素。

(5)、q.back( ):返回队尾元素。

(6)、q.size( ):返回元素个数。

(7)、q.empty( ):检查队列是否为空。

下面给出STL queue的代码:

//洛谷P1540, STL queue
#include<bits/stdc++.h>
using namespace std;
int Hash[1003]={0};  //用哈希检查内存中有没有单词,hash[i]=1表示单词i在内存中
queue<int> mem;      //用队列模拟内存
int main(){
    int m,n;      scanf("%d%d",&m,&n);
    int cnt = 0;                         //查词典的次数
    while(n--){
int en;   scanf("%d",&en);       //输入一个英文单词
if(!Hash[en]){                   //如果内存中没有这个单词
++cnt;
mem.push(en);                //单词进队列,放到队列尾部
Hash[en]=1;                  //记录内存中有这个单词
while(mem.size()>m){         //内存满了
Hash[mem.front()] = 0;   //从内存中去掉单词
mem.pop();               //从队头去掉
		   }
	    }
}
printf("%d\n",cnt);
return 0;
}

1.2.2、手写循环队列

手写循环队列代码:

#include<bits/stdc++.h>
#define N 1003               //队列大小
int Hash[N]={0};             //用Hash检查内存中有没有单词
struct myqueue{
    int data[N];             //分配静态空间
    /* 如果动态分配,这样写: int *data;    */
    int head, rear;          //队头、队尾
    bool init(){             //初始化
        /*如果动态分配,这样写:
        Q.data = (int *)malloc(N * sizeof(int)) ;
        if(!Q.data) return false;        */
        head = rear = 0; 
        return true;
    }
    int size(){ return (rear - head + N) % N;}       //返回队列长度        
    bool empty(){               //判断队列是否为空
        if(size()==0) return true;
        else          return false;
    }
    bool push(int e){           //队尾插入新元素。新的rear指向下一个空的位置
         if((rear + 1) % N == head ) return false;    //队列满
         data[rear] = e;
         rear = (rear + 1) % N;
         return true;
    }
    bool pop(int &e){           //删除队头元素,并返回它
         if(head == rear) return false;       //队列空
         e = data[head];
         head = (head + 1) % N;
         return true;
    }
    int front(){  return data[head]; }         //返回队首,但是不删除        
}Q;
int main(){
    Q.init();                    //初始化队列
    int m,n;  scanf("%d%d",&m,&n);
    int cnt = 0;
    while(n--){
	   int en;  scanf("%d",&en);    //输入一个英文单词
	   if(!Hash[en]){               //如果内存中没有这个单词
		  ++cnt;
		  Q.push(en);              //单词进队列,放到队列尾部
		  Hash[en]=1;
		  while(Q.size()>m){       //内存满了
               int tmp;   Q.pop(tmp);     //删除队头
			 Hash[tmp] = 0;       //从内存中去掉单词
		  }
	   }
    }
    printf("%d\n",cnt);
    return 0;
}

1.2.3、双端队列和单调队列

双端队列和单调队列的概念

双端队列(deque)是一种具有队列和栈性质的数据结构,它支持在两端进行插入和删除操作。具体来说,双端队列可以在队列的头部和尾部进行元素的添加和删除操作,因此既可以作为队列使用,也可以作为栈使用。

单调队列(monotonic queue)是一种特殊的队列,它主要用于解决一类特殊的问题,即滑动窗口问题。滑动窗口问题是指在一个固定大小的窗口中,找到一些特定的元素或计算一些特定的值。单调队列主要用于维护滑动窗口中的元素,使得队列中的元素满足一定的单调性(单调递增或单调递减)。

在实际应用中,双端队列和单调队列都有广泛的应用。双端队列可以用于维护一个滑动窗口中的最大值或最小值,而单调队列则可以用于求解滑动窗口中的最大值、最小值、中位数等问题。

1.2.4、优先队列

优先队列(priority queue)是一种特殊的队列,它的每个元素都具有一个优先级。优先级高的元素先出队列,优先级相同的元素按照其在队列中的先后顺序出队列。通常来说,优先队列中元素的优先级是由一个可比较的关键字来确定的。

优先队列可以使用各种数据结构来实现,包括数组、链表、堆等。其中,二叉堆是一种经典的实现方式。二叉堆分为最大堆和最小堆,最大堆的根节点元素是整个堆中的最大值,而最小堆的根节点元素是整个堆中的最小值。在实际应用中,最大堆常常用于维护一个动态数据集中的最小值,而最小堆则常常用于维护一个动态数据集中的最大值。

优先队列的常见操作包括插入元素、删除元素、查找最大/最小元素等。其中,插入元素和删除元素的时间复杂度通常是O(log n),查找最大/最小元素的时间复杂度是O(1)。优先队列在很多算法中都有广泛的应用,比如Dijkstra算法、Prim算法、Kruskal算法等。

-END-【二】一起算法---队列:STL queue、手写循环队列、双端队列和单调队列、优先队列

 文章来源地址https://www.toymoban.com/news/detail-402104.html

到了这里,关于【二】一起算法---队列:STL queue、手写循环队列、双端队列和单调队列、优先队列的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构与算法】C++的STL模板(迭代器iterator、容器vector、队列queue、集合set、映射map)以及算法例题

    更多算法例题链接: 【数据结构与算法】递推法和递归法解题(递归递推算法典型例题) 什么是迭代器(iterator) 迭代器(iterator)的定义: 迭代器是一种检查容器内元素并遍历元素的数据类型。 迭代器提供对一个容器中的对象的访问方法,并且定义了容器中对象的范围。 容器

    2024年04月14日
    浏览(48)
  • 【数据结构】队列的使用|模拟实现|循环队列|双端队列|面试题

    1.1 概念 队列 :只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出FIFO(First In First Out) 入队列:进行插入操作的一端称为 队尾(Tail/Rear) 出队列:进行删除操作的一端称为 队头(Head/Front) 队列和栈的区别: 队列是 先进先出(队

    2024年02月03日
    浏览(43)
  • 【C++初阶10-stack&queue】STL中的栈和队列(附优先级队列

    本期分享:STL中的栈和队列。 在数据结构初阶时,我们已经学习这来那个两种数据结构,如今来看STL中的,不过是更加标准化。而实现起来,会简单得超乎你想象! 文中不足错漏之处望请斧正! STL中的栈和队列是容器适配器。容器适配器是对某种已有容器的再次封装。 比如

    2024年02月06日
    浏览(43)
  • 『C++ - STL』之优先级队列( priority_queue )

    什么是优先级队列,从该名中可以知道他一定有队列的一定属性,即先入先出(LILO),而这里的优先级则可以判断出它的另一个特点就是可以按照一定的条件将符合该条件的先进行出队,这就是优先级队列; 而在数据结构中有一个支持该操作的结构 - 堆( heap ); 而在STL中,这个

    2024年02月07日
    浏览(42)
  • 数据结构与算法-双端队列

    Gitee上开源的数据结构与算法代码库:数据结构与算法Gitee代码库 双端队列、队列、栈对比 定义 特点 队列 一端删除(头)另一端添加(尾) First In First Out 栈 一端删除和添加(顶) Last In First Out 双端队列 两端都可以删除、添加 优先级队列 优先级高者先出队 延时队列 根据

    2024年02月13日
    浏览(40)
  • 【C++入门到精通】C++入门 —— priority_queue(STL)优先队列

    ⭕文章绑定了VS平台下std::priority_queue的源码,大家可以下载了解一下😍 前面我们讲了C语言的基础知识,也了解了一些数据结构,并且讲了有关C++的命名空间的一些知识点以及关于C++的缺省参数、函数重载,引用 和 内联函数也认识了什么是类和对象以及怎么去new一个 ‘对象

    2024年02月12日
    浏览(43)
  • 【C++】STL使用仿函数控制优先级队列priority_queue

    本文章讲解C++STL的容器适配器:priority_queue的实现,并实现仿函数控制priority_queue底层。 priority_queue叫做优先级队列,它的底层结构是堆,在库中,默认生成的是大堆 在库的实现中,使用vector作为该优先级队列的适配容器。 由于priority_queue也是一个适配器,所以它的接口函数

    2024年02月16日
    浏览(43)
  • 【C++】STL优先级队列(priority_queue)功能介绍以及模拟实现

    点进来的小伙伴不知道学过数据结构里的堆没有,如果学过的话,那就好说了,优先级队列就是堆,如果没学过,没关系,可以参考一下我之前写的一篇关于堆的博客,可以点进去看看:【数据结构】堆(包含堆排序和TOPK问题) 那么了解过堆了的话,我就不讲那么细致了,

    2024年02月16日
    浏览(45)
  • 【STL】priority_queue(优先级队列)详解及仿函数使用(附完整源码)

    1. priority_queue介绍和使用 1.1 priority_queue介绍 优先级队列也是在 queue 里: 因此和 queue 一样, priority_queue 也是一个容器适配器。priority_queue官方文档 优先队列是一种容器适配器,根据严格的弱排序标准,它的第一个元素总是它所包含的元素中最大的。 类似于堆,在堆中可以随

    2024年02月08日
    浏览(40)
  • 算法模板之单调栈和单调队列图文详解

    🌈个人主页: 聆风吟 🔥系列专栏: 算法模板、数据结构 🔖少年有梦不应止于心动,更要付诸行动。      💬 hello! 各位铁子们大家好哇,今天作者给大家带来了单调栈和单调队列的算法模板讲解,让我们一起加油进步。      📚 系列专栏:本期文章收录在《算法

    2024年02月02日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包