[STL] Queue Container

📌 Queue

• FIFO (First In First Out) 방식
  • 가장 먼저 저장된 데이터가 먼저 처리
  • 양쪽 맨 끝에 있는 데이터만 접근 가능
• container adapter
  • vector, deque, list 등의 컨테이너를 기반으로 구현
  • 기존 컨테이너들이 queue 처럼 동작할 수 있도록 멤버함수를 제한

---

✔ queue 사용

#include <queue>
using namespace std;

• <queue> header
• std::queue

---

✔ queue 생성

queue<[type], [container type]> [name]

[container type] default : deque<[type]>

• queue에 저장될 타입을 명시
• deque 컨테이너 기반으로 생성

// 비어있는 정수형 타입 queue q1을 생성
queue<int> q1;

// 기존에 있는 deque 컨테이너를 q2에 복사
deque<int> d = { 10, 20, 70 };
queue<int> q2(d);

// 기존에 있는 list 컨테이너를 q3에 복사
list<char> l = { 'K', 'S', 'H' };
queue<char, list<char>> q3(l);

• 비어 있는 queue를 생성하거나 다른 sequence container에서 복사하여 생성 가능
• 기본적으로 deque 기반으로 구현되어 있기 때문에, list를 복사할 경우 list 기반 생성으로 선언

---

✔ queue 멤버 함수

1) element access & capacity

function	description
q.front()	첫번째 원소 반환
q.back()	마지막 원소 반환
q.size()	queue q의 크기 반환
q.empty()	비어있으면 true, 그렇지 않으면 false 반환

2) modifiers (수정)

function	description
q.push(x)	원소 x를 마지막 원소 뒤에 추가
q.pop()	첫번째 원소 제거

queue<int> q;

for (int x = 1; x <= 5; x++)
{
    q.push(x * 10);
}

cout << "size: " << q.size();   // 5

while (!q.empty())
{
    cout << q.front() << " ";   // 10 20 30 40 50
    q.pop();
}

---

📌 Priority Queue

• 우선순위가 정의된 queue
• Heap 자료구조 형태
  • 우선순위가 가장 큰 원소가 top을 유지
  • 원소 추가 및 제거 과정에서의 시간 복잡도 : O(logn)

---

✔ priority queue 사용

#include <queue>
using namespace std;

• <queue> header
• std::priority_queue

---

✔ priority queue 생성

priority_queue<[type], [container type], [compare]> [name]

[container type] default : vector<[type]>
[compare] default : less<[type]>

• priority queue에 저장될 타입을 명시
• vector 컨테이너 기반으로 생성
• 우선순위 기준이 없는 경우, 내림차순으로 정렬되어 값이 클수록 높은 우선순위를 가짐

// 비어있는 정수형 타입 priority queue pq1을 생성
priority_queue<int> pq1;

// 기존에 있는 vector 컨테이너를 pq2에 복사
vector<int> v = { 50, 30, 20, 60, 70, 10, 0 };
priority_queue<int> pq2(v.begin(), v.end());

// 작은 값을 우선 순위로 하는 priority queue pq3를 생성
priority_queue<int, vector<int>, greater<int>> pq3;

• 비어 있는 priority queue를 생성하거나 다른 sequence container에서 복사하여 생성 가능
• vector를 복사하는 경우, iterator를 이용하여 복사
• 오름차순 등의 다른 우선순위 기준으로 변경 가능

---

✔ priority queue 멤버 함수

1) element access & capacity

function	description
pq.top()	우선순위가 가장 높은 원소 반환
pq.size()	priority queue pq의 크기 반환
pq.empty()	비어있으면 true, 그렇지 않으면 false 반환

2) modifiers (수정)

function	description
pq.push(x)	원소 x를 pq에 추가
pq.pop()	우선순위가 가장 높은 원소 제거

priority_queue<int> pq;

pq.push(30);
pq.push(10);
pq.push(40);
pq.push(50);
pq.push(90);
pq.push(20);

cout << "size: " << pq.size();   // 6

while (!pq.empty())
{
	cout << pq.top() << " ";     // 90 50 40 30 20 10
	pq.pop();
}

---

✔ priority queue 우선순위 설정

우선순위를 직접 설정하는 경우

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

struct compare
{
	bool operator()(int x, int y)
	{
    	// 절댓값이 큰 수의 우선순위가 높도록 설정
		return abs(x) < abs(y);  
	}
};

int main()
{
	vector<int> v = { 50, -20, 70, -60, -10, 30, 90, 0 };
	priority_queue<int, vector<int>, compare> pq(v.begin(), v.end());

	while (!pq.empty())
	{
		cout << pq.top() << " ";
		pq.pop();
	}

	return 0;
}

• output: 90 70 -60 50 30 -20 -10 0
• compare 구조체 안에 operator를 새로 정의
• vector v가 priority queue로 복사되면서 우선순위 기준 설정

pair에 우선순위를 설정하는 경우

#include <iostream>
#include <queue>
#include <string>
#include <utility>

using namespace std;

struct compare
{
	bool operator()(pair<string, int> x, pair<string, int> y)
	{
		// 가격 내림차순, 과일 이름 오름차순으로 우선순위 설정
		return x.second != y.second ? x.second < y.second : x.first > y.first;
	}
};

int main()
{
	priority_queue<pair<string, int>, vector<pair<string, int>>, compare> fruits;

	fruits.push(make_pair("apple", 3000));
	fruits.push(make_pair("banana", 2000));
	fruits.push(make_pair("melon", 8000));
	fruits.push(make_pair("grape", 5000));
	fruits.push(make_pair("watermelon", 8000));
	fruits.push(make_pair("strawberry", 3000));
	fruits.push(make_pair("pineapple", 8000));
	
	while (!fruits.empty())
	{
		pair<string, int> fruit = fruits.top();
		cout << fruit.first << ": " << fruit.second  << "원\n";
		fruits.pop();
	}

	return 0;
}

• output :

melon: 8000원
pineapple: 8000원
watermelon: 8000원
grape: 5000원
apple: 3000원
strawberry: 3000원
banana: 2000원