큐(queue)

선입 선출, 스택과 꺼내는 순서가 반대

#include <iostream>
#include <queue>
using namespace std;

int main()
{
	queue<int> qi;
    	cout << pq.empty() << " ";	//큐가 비어있나 true/false
	qi.push(1);	//값 넣기
	qi.push(2);
    	qi.push(3);
	qi.push(6);
	qi.push(4);
	cout << qi.front() << " ";	//맨앞의 수
    	cout << qi.size() << " ";	//큐의 개수
	cout << qi.back() << " ";	//맨뒤의 수
    	cout << pq.empty() << " ";
	qi.pop();	//맨앞의 값 제거
	cout << qi.front();

	return 0;
}

결과값

1 1 5 4 0 2

 

 

 

---

우선순위 큐

- 원소의 추가와 삭제는 O(log n)의 시간이 걸리고 탐색은O(1)시간이 걸린다.

- 필요한 연산이 최대, 최소를 구하는 것이면 우선순위 큐를 사용하면 좋다.

- 기본적으로 원소가 내림차순으로 정렬이 되어있다.

- 탐색 및 삭제의 대상이 되는 것은 최대 원소이다.

 

#include <iostream>
#include <queue>
using namespace std;

int main()
{
	priority_queue<int> pq;
    //priority_queue<int, vector<int>, greater<int>> pq; //가장 순번이 빠른순(오름차순)
    //priority_queue<int, vector<int>, less<int>> pq;	//가장 순번이 늦은순(내림차순)
	pq.push(3);
	pq.push(4);
	pq.push(1);
	pq.push(2);
	pq.push(2);

	cout << pq.top() << " ";	//가장 큰 수
	cout << pq.size() << " ";	//원소의 개수
	pq.pop();	//가장 큰 수를 제거

	cout << pq.top() << " ";
    
	return 0;
}