纸上得来终觉浅,绝知此事要躬行。大家好!我是霜淮子,欢迎订阅我的专栏《算法系列》。
学习经典算法和经典代码,建立算法思维;大量编码让代码成为我们大脑的一部分。
⭐️已更系列
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-文章来源:https://www.toymoban.com/news/detail-402104.html
文章来源地址https://www.toymoban.com/news/detail-402104.html
到了这里,关于【二】一起算法---队列:STL queue、手写循环队列、双端队列和单调队列、优先队列的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!