Queue

큐

큐는 먼저 집어 넣은 데이터가 먼저 나오는 선입선출을 지닌 자료 구조
삽입 삭제에 O(1) 탐색에 O(n)이 걸린다.

#include  <bits/stdc++.h>
using namespace std;
queue<int> q;
int main(){
	for(int i=1;i<=10;i++)q.push(i);
	while(q.size()){
		cout<<q.front()<<' ';
		q.pop();
	}
	return 0;
}
/* 
1 2 3 4 5 6 7 8 9 10
*/

push(value)

value를 큐에 추가합니다.

pop()

가장 앞에 있는 요소를 제거합니다.

size()

큐의 크기입니다.

front()

가장 앞에 있는 요소를 참조합니다

우선순위 큐

우선순위 큐는 각 요소에 어떠한 우선순위가 추가로 부여되어있는 컨테이너를 말함
우선순위가 가같으면 대기열에 포함된 순서에 따라 제공

int형 우선순위 큐

int형 우선순위 큐는 greater 를 서서 오름차순, less를 써서 내림차순으로 바꿀 수 있다.
기본 값은 내림차순이라 단순하게 priority_queue<타입>을 쓰면 해당 타입에 대한 내림차순으로 설정된다.

#include <bits/stdc++.h>
using namespace std;
priority_queue<int, vector<int>, greater<int> > pq;//오름차순 
priority_queue<int> pq2;// 내림차순 
priority_queue<int, vector<int>, less<int>>pq3;//내림차순
int main(){
	for(int i=5; i>=1;i--){
	pq.push(i); pq2.push(i); pq3.push(i);
	}
	while(pq.size()){
		cout<<pq.top()<<" : "<< pq2.top()<<" : "<< pq3.top()<<'\n';
		pq.pop(); pq2.pop();pq3.pop();
	}
	return 0;
}
/*
1 : 5 : 5
2 : 4 : 4
3 : 3 : 3
4 : 2 : 2
5 : 1 : 1
*/

구조체를 담은 우선순위 큐

#include <bits/stdc++.h>
using namespace std;
struct Point{
	int y,x;
	Point(int y, int x) : y(y),x(x){}
	Point(){y=-1,x=-1;}
	bool operator < (const Point & a) const{
	return x>a.x;}	
};

priority_queue<Point> pq;
int main(){
	pq.push({1,1});
	pq.push({2,2});
	pq.push({3,3});
	pq.push({4,4});
	pq.push({5,5});
	pq.push({6,6});
	cout<<pq.top().x<<"\n";
	return 0;
}
//1

< 연사자에 x > a.x를 했기 때문에 내림차순으로 출력이 되어야 하는데 1이 출력된 모습
가장 최소를 끄집어 내고 싶은 로직이면 >, 최대라면 < 로 설정