[자료구조] 우선순위 큐, 큐

우선순위 큐

📌 사용하려면

#include <queue> 
using namespace std;

//최소부터 반환하는 큐(오름차순 정렬)
//컴파일러가 int>> 부분을 비트연산으로 착각할 수 있으니 띄어쓰기 해주기
priority_queue< int, vector<int>, greater<int> > q1;

//최대부터 반환하는 큐(내림차순 정렬)
priority_queue< int, vector<int>, less<int> > q2;

//q2와 똑같은 기능. 디폴트는 less임
priority_queue<int> q3;

• priority_queue< 자료형, 구현체, 비교 연산자 > 이름;
  • 자료형 : int, double, long long, 선언한 클래스 등..
  • 구현체 : vector<자료형>이 디폴트
    • 우선순위 큐가 vector위에서 돌아가고 있다는 뜻
    • deque<자료형> 도 가능
  • 비교연산자
    - less<자료형> : 최대부터 반환(내림차순 정렬)
    - 디폴트
    - greater<자료형> : 최소부터 반환(오름차순 정렬)
    
    

📌 기본 함수

• q1.pop();
  • 우선순위 큐에서 top의 원소를 삭제
  • 주의❗ 우선순위 큐든 그냥 큐든 pop한 원소를 변수에 바로 넣을 순 없음
    • int n = q1.pop(); 불가능
    • int n = q1.top();을 통해 변수에 저장한 후 pop해야함
• q1.push(value);
  • 우선순위 큐에 원소(value) 추가
• q1.top();
  • top에 있는 원소(맨처음 원소) 반환(조회)
  • 주의❗ 그냥 큐는 q1.front()로 접근하는데 우선순위 큐는 top()임
• q1.empty();
  • 비어있으면 true, 아니면 false를 반환
• q1.size();
  • 우선순위 큐에 포함되어 있는 원소들의 수를 반환

📌 시간복잡도

• 우선순위 큐 원소 삽입/삭제 : 𝑂(𝑙𝑜𝑔𝑁)
• 우선순위 큐를 이용한 정렬 : 𝑂(𝑁𝑙𝑜𝑔𝑁)
  • cf. sort함수(퀵정렬)를 이용한 정렬 : 𝑂(𝑁𝑙𝑜𝑔𝑁)
  • 여러 개의 원소 중 가장 작은 원소 2개를 뽑는 경우에는 정렬함수로 다 정렬할 필요x, 우선순위큐 삽입/삭제 이용하면 더 빠름!

👉 생각보다 연산속도가 빠르므로 가능한 경우엔 최대한 이용하도록 하자!

---

큐

📌 사용하려면

#include <queue>
using namespace std;

queue<int> q;

• queue<자료형> 이름;
  
  

📌 기본 함수

• q.pop();
  • 큐에서 front의 원소를 삭제
• q.push(value);
  • 큐에 원소(value) 추가
• q.front();
  • front에 있는 원소(맨처음 원소) 반환(조회)
• q.size();
  • 비어있으면 true, 아니면 false를 반환
• q.empty();
  • 큐에 포함되어 있는 원소들의 수를 반환
    
    

주의❗

• 큐, 우선순위 큐는 탐색(조회)가 불가능
• iterator 없음
  • 일일이 pop으로 꺼내보는 수밖에 없다
• 큐 사용 문제는 보통 while(!q.empty()) 안에서 큐 관련 작업을 함
  따라서 큐에 맨 처음으로 원소 넣는 작업은 while문 앞에서 해줘야 함
• q.front() q.pop()은 반드시 !q.empty()라는 조건 안에서 수행
  • 스택도 마찬가지
• 변수값을 큐에 push하고 그 변수에 접근해서 값을 바꾸어도 큐에 있는 값은 변하지 않는다.

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

  for (int i = 0; i < 10; i++)
  {
    arr[i] = i;
  }

  pq.push(arr[0]);
  pq.push(arr[1]);
  pq.push(arr[2]);

  arr[1] = 10; //큐 밖에서 변수값을 10으로 바꿔도
  while (!pq.empty())
  {
    int a = pq.top();
    cout << a; //큐 안에 있는 값은 그대로 1
    pq.pop();
  }

💡 활용

• 큐에 머무는 시간 = 현재 시각 - 큐에 들어간 시각
• 큐에 들어간 시각을 원소의 pair로 저장
• ex. 13335 트럭 : 원소들이 큐 안에 머무른 시간을 각각 관리해야 하는 경우(일정 시간 지나면 큐에서 빼야 함)