C++之隊列

文章目錄

• 1.雙端隊列
• • 1.1插入元素
  • 1.2删除元素
  • 1.3通路元素
  • 1.4其它特性
• 2.優先隊列
• 3.應用：

1.雙端隊列

1.1插入元素

• 在頭部添加元素：

  deq.push_front(x);

• 在末尾添加元素：

  deq.push_back(x);

• 在任意位置插入元素，時間複雜度為O(n)：

  deq.insert(iterator it,int x);

1.2删除元素

• 頭部删除元素：

  deq.pop_front();

• 末尾删除元素：

  deq.pop_back();

• 删除任意位置元素，時間複雜度為O(n)：

  deq.erase(iterator it);

• 删除first到last之間的元素：

  deq.erase(iterator first,iterator last);

• 清空元素：

  deq.clear();

1.3通路元素

• 通路元素 除了頭部，末尾時間複雜度為O(n)：

  deq[i];deq.at(i);

• 通路頭部元素：

  deq.front();

• 通路尾部元素：

  deq.back();

1.4其它特性

• 計算隊列大小：

  deq.size();

• 判斷對列是否為空：

  deq.empty();

• 翻轉隊列：

  reverse(deq.begin(),deq.end());

• 對列進行排序：

  sort(deq.begin(),deq.end());

2.優先隊列

• 定義：在優先隊列中，元素賦予優先級，具有優先級最高先出的特征。

  例如：

  priority_queue<type,container,function>

  。其中type:資料類型；container:實作優先隊列的底層容器，例如vector,deque，但不能用list; function:元素之間的比較形式。後面兩個參數可以省略，一旦省略，預設是大根推
• 常見成員函數：

  bool empty() const;

  、

  int size() const;

  、

  void pop();//删除隊列的頂部元素

  、

  int top(); //與對列q.front()不同,這裡是q.top();傳回隊列頂部元素;

  、

  void push();将元素插到隊列中并進行排序

• 大頂堆：

  priority_queue<int> q;

  、

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

• 小頂堆：

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

  //greater和less是std實作的兩個仿函數（就是使一個類的使用看上去像一個函數。其實作就是類中實作一個operator()，這個類就有了類似函數的行為，就是一個仿函數類了）
• 用pair類型做優先隊列的例子：

priority_queue<pair<int,int>> q;
pair<int,int> a(1,11);
pair<int,int> b(2,22);
pair<int,int> c(2,33);
q.push(a);
q.push(b);
q.push(c);
while(!q.empty()){
    cout<<q.top().first<<" "<<q.top().second<<endl;
    q.pop();
}
           

• 用pair類型做優先隊列（自定義first，second的值的大小）的例子

#include <iostream>
#include <queue>
using namespace std;
typedef pair<int, int> P;
struct cmp{
    bool operator()(const P p1, const P p2){  
        	return p1.second > p2.second; //second的小值優先,恰好相反
    }
};
int main()
{
	priority_queue<P, vector<P>, cmp> que;
	que.push(P(10,20));
	que.push(P(15,30));
	que.push(P(20,1));
	P p;
	while(!que.empty()){
	    p=que.top();
	    que.pop();
	    cout<<p.first<<" "<<p.second<<endl;
	}
}
           

• 自定義類型與優先對列的例子：

#include<bits/stdc++.h>
using namespace std;
struct Node{
	int x;
	int y;
	Node(int x,int y){
		this->x=x;
		this->y=y;
	}
};
struct cmp{
	bool operator()(Node a,Node b){
		if(a.x==b.x) return a.y<b.y;
		return a.x<b.x;//這裡符号表示恰好相反
	}
};
int main()
{
    priority_queue<Node,vector<Node>,cmp> q;
    Node a(1,11);
    Node b(2,22);
    Node c(2,33);
    q.push(a);
    q.push(b);
    q.push(c);
    while(!q.empty()){
    	cout<<q.top().x<<" "<<q.top().y<<endl;
    	q.pop();
	}
	return 0;
}
           

3.應用：

• 題目：回文序列：這道題沒有很明顯提示使用雙端對列。但是考慮到回文序列是需要頭尾一一對應相等，我們需要對頭尾的元素進行去除，是以我們想到雙端對列。