[C++/STL] 큐(Queue), 우선순위 큐(Priority Queue)

 

1. 큐(Queue) 

 

 

 

큐(Queue) 란?

 

 - FIFO(First In Fisrt Out) 자료구조

 

 - 가장 먼저 넣었던 데이터를 사용할 때 이용한다.

 

 

---

 

 

큐 사용 방법

 

 

 - 큐 선언

// 헤더 선언 필요
#include <queue>

// int 자료형을 저장하는 큐 선언
queue<int> q;

 

 - 원소 추가

// 원소 n 삽입
q.push(n);

 

 - 맨 처음 원소 제거

// 맨 처음 원소 제거
q.pop();

 

 - 맨 처음 원소 조회

// 맨 처음 원소 조회
q.front();

 

 - 기타

// 큐이 비어있는지 확인
// 원소가 없으면 true, 원소가 있으면 false 반환
q.empty();

// 큐의 크기(원소의 개수) 조회
q.size();

 

---

 

2. 우선순위 큐(Priority Queue)

 

 

 

우선순위 큐(Priority Queue) 란?

 

 - 우선순위의 개념을 큐에 도입한 자료구조.

 

 - 데이터들이 우선순위를 가지며, 우선순위가 높은 데이터가 가장 위에 있다.

 

 - 힙을 이용하여 구현되었다.

 

 - 우선순위 큐는 데이터 추가, 삭제 시 O(logn)을 보장한다.

 

---

 

 

우선순위 큐 사용 방법

 

 - 우선순위 큐 선언

// 헤더 선언 필요
#include<queue>

// int 자료형을 저장하는 우선순위 큐 선언
// priority_queue<자료형, 구현체, 비교 연산자> pq; 
// 비교 연산자 생략 시 maxheap으로 선언된다.
priority_queue<int, vector<int>> pq;  

// less와 greater는 헤더에 #include <functional> 선언이 필요하다.
// maxheap(루트가 우선순위가 제일 높다) 선언
priority_queue<int, vector<int>, less<int>> pq;  

// minheap(루트가 우선순위가 제일 낮다) 선언
priority_queue<int, vector<int>, greater<int>> pq;  

 

 - 일반적인 사용 방법은 큐(Queue)와 동일하다.