队列的理解

た入场券 2022-08-04 13:45 179阅读 0赞

队列 的理解

队列最鲜明的特点是先进先出（First\-In First-Out,FIFO）是一种特殊的线性表，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

之前说栈和枪械的部分原理很相似，那只是像带弹匣的枪，今天说的队列其实也像一些枪械上的原理，机枪，不是用弹匣盛弹的，使用弹链，如图：

![Center][]![Center 1][]

看了图，是不是就觉得确实有点像；

把子弹压到弹链上，就好似入队；把弹链装上枪然后击发，就像出队；

基本的操作：

STL的栈定义在头文件<queue>中，故使用前得写 \#include<queue>

queue<int>q;  //定义一个整型的队列

q.pop()；   //删除栈顶元素（就如同机枪的撞针击发弹匣顶部的子弹的过程）

q.push(i);   //添加元素i（如同往弹链尾再压上子弹）

q.front();    //指向队顶元素（与优先队列不同）

下面这段代码功能是：原样输出

#include<stdio.h>
    #include<queue>
    using namespace std;
    int main(){
    	int t;
    	scanf("%d",&t);
    	while(t--){
    		int n;
    		scanf("%d",&n);
    		queue<int>q;
    		int a;
    		for(int i=0;i<n;i++){
    			scanf("%d",&a);
    			q.push(a);
    		}
    		printf("%d",q.front());
    		q.pop();
    		while(!q.empty()){
    			printf(" %d",q.front());
    			q.pop();
    		}
    		printf("\n");
    	}
    	return 0;
    }

还有一种特殊的队列：优先队列

优先队列，就是对于一些元素有优先权，就比如说去医院就诊，对于那些伤势严重的人，他们就有优先就诊的权力，在程序中，可以体现为数字最大的（或者最小的）有优先出队的权力等；

优先队列的基本操作：

与普通队列相似，

就是q.top()为指向队首元素，还有q.size()返回优先队列中元素的个数，其他一样；

下面先来一个简单的优先队列例子（最常用的），元素按从大到小出队。

#include<cstdio>
    #include<queue>
    using namespace std;
    
    int main(){
    	int t,a,n;
    	scanf("%d",&t);
    	while(t--){
    		priority_queue<int>q;
    		scanf("%d",&n);
    		for(int i=0;i<n;i++){
    			scanf("%d",&a);
    			q.push(a);
    		}
    		printf("%d",q.top());
    		q.pop();
    		while(!q.empty()){
    			printf(" %d",q.top());
    			q.pop();
    		}
    		printf("\n");
    	}
    	return 0;
    }

若要按从小到大出队只需将上面这段代码中的

priority_queue<int>q;

改为

priority_queue<int, vector<int>, greater<int> >q;

即可实现

还有一种是自定义优先队列，目前还未掌握，待掌握后在补进；^ω^

[Center]: https://img-blog.csdn.net/20150830201625145?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 1]: /images/20220731/73e3913ebde3417a93f9f008592da602.png