C++ STL (5) queue队列和priority_queue优先队列的简单用法

C++ STL (5) queue队列和priority_queue优先队列的简单用法

队列的简单介绍

• queue队列的简单介绍

队列(Queue)是只允许在一端进行插入操作，而在另一端进行删除操作的线性表（先进先出）。允许插入的端是队尾，允许删除的端是队头。
queue 模板类需要两个模板参数，一个是元素类型，一个容器类型，元素类型是必要的，容器类型是可选的，默认为deque 类型。
队列的容量可以有限，也可以是无限的。

• 注意点
  新元素进行入队列容易造成假溢出。
  • 假溢出：顺序队列因多次入队列和出队列操作后出现的尚有存储空间但不能进行入队列操作的溢出。
  • 真溢出：顺序队列的最大存储空间已经存满二又要求进行入队列操作所引起的溢出。
• 储存方式
  队列是一个先进先出的线性表，相应的也有顺序存储和链式存储两种方式。
  顺序存储：使用数组实现，比如有一个ｎ个元素的队列，数组下标0的一端是队头，入队操作就是通过数组下标一个个顺序追加，不需要移动元素，但是如果删除队头元素，后面的元素就要往前移动，对应的时间复杂度就是O(n)，性能自然不高。
  循环队列：有两个指针，front指向队头，rear指向对尾元素的下一个位置，元素出队时front往后移动，如果到了对尾则转到头部，同理入队时rear后移，如果到了对尾则转到头部，这样通过下标front出队时，就不需要移动元素了，提高了出队的性能。
• 头文件
  #include<queue>
• 声明方式
  queue<结构类型> 队列名;
• queue 的基本操作
  1.入队，如例：q.push(x); 将x 接到队列的末端。
  2.出队，如例：q.pop(); 弹出队列的第一个元素，注意，并不会返回被弹出元素的值。
  3.访问队首元素，如例：q.front()，即最早被压入队列的元素。
  4.访问队尾元素，如例：q.back()，即最后被压入队列的元素。
  5.判断队列空，如例：q.empty()，当队列空时，返回true。
  6.访问队列中的元素个数，如例：q.size()

例题：HDU - 1702

#include<iostream>
#include<stack>
#include<cstdio>
#include<string>
#include<queue>

using namespace std;

stack<int>s1;
queue<int>s2;

int main()
{
	int T,n,a;
	int i=0,j=0;
	string s,sa;
	cin>>T;
	for(i=0;i<T;i++)
	{
		cin>>n>>s;
		while(!s1.empty())
			s1.pop();
		while(!s2.empty())
			s2.pop();

		if(s=="FILO")
		{
		    for(j=0;j<n;j++)
		    {
			    cin>>sa;
			    if(sa=="IN")
			    {
				    cin>>a;
				    s1.push(a);
			    }
				else if(sa=="OUT")
				{
					if(s1.size()!=0)
					{
					    cout<<s1.top()<<endl;
					    s1.pop();
					}
					else
					{
						cout<<"None"<<endl;
					}
				}
		    }
		}
		else
		{
			for(j=0;j<n;j++)
			{
				cin>>sa;
				if(sa=="IN")
				{
					cin>>a;
					s2.push(a);
				}
				else if(sa=="OUT")
				{
					if(s2.size()!=0)
					{
						cout<<s2.front()<<endl;
					    s2.pop();
					}
					else
					{
						cout<<"None"<<endl;
					}
				}
			}
		}
	}
	return 0;
}

优先队列priority_queue

• 优先队列的简单介绍以及与普通队列的区别
  优先队列容器与队列一样，只能从队尾插入元素，从队首删除元素。但是它有一个特性，就是队列中最大的元素总是位于队首，所以出队时，并非按照先进先出的原则进行，而是将当前队列中最大的元素出队。这点类似于给队列里的元素进行了由大到小的顺序排序。元素的比较规则默认按元素值由大到小排序，可以重载“<”操作符来重新定义比较规则。
• 实现方式
  其成员函数有“判空(empty)” 、“尺寸(Size)” 、“栈顶元素(top)” 、“压栈(push)” 、“弹栈(pop)”等。
  优先级队列可以用向量(vector)或双向队列(deque)来实现(注意list container不能用来实现queue，因为list的迭代器不是任意存取iterator，而pop中用到堆排序时是要求randomaccess iterator 的)：

    priority_queue<vector<int>, less<int> > pq1; 　　　 // 使用递增less<int>函数对象排序
    priority_queue<deque<int>, greater<int> > pq2; 　　// 使用递减greater<int>函数对象排序

• 简单操作
  如果队列为空，则返回真：empty()
  删除对顶元素，删除第一个元素：pop()
  加入一个元素：push()
  返回优先队列中拥有的元素个数：size()
  返回优先队列对顶元素，返回优先队列中有最高优先级的元素：top()
• 注意点
  在默认的优先队列中，优先级高的先出队。在默认的int型中先出队的为较大的数。
  自动排序
• 头文件
  与queue相同，都是#include<queue>
• 声明方式
  priority_queue<结构类型> 队列名;

    priority_queue<int> q;//通过操作，按照元素从大到小的顺序出队
    priority_queue<int,vector<int>, greater<int> > q;//通过操作，按照元素从小到大的顺序出队

• 自定义优先级方式

struct cmp
 {     
　　bool operator()(int x, int y)     
　　{        
　　　　 return　x > y;// x小的优先级高      
　　　　  //也可以写成其他方式，如： return p[x] > p[y];表示p[i]小的优先级高
　　}
};
priority_queue<int, vector<int>, cmp> q;//定义方法

struct node 
{     
　　int x, y;     
　　friend bool operator < (node a, node b)     
　　{         
　　　　return a.x > b.x;//结构体中，x小的优先级高     
　　}
};
priority_queue<node>q;//定义方法
//在该结构中，y为值, x为优先级。
//通过自定义operator<操作符来比较元素中的优先级。
//在重载”<”时，最好不要重载”>”，可能会发生编译错误