[C++] STL queue 사용법

Queue

큐 (Queue) 는 제일 먼저 넣은 데이터가 가장 먼저 나오는 FIFO (First In First Out) 자료 구조이다. 

Queue 구조에 대한 자세한 설명은 아래 게시글에서 확인할 수 있다.

 

https://readytojoin.tistory.com/77

[ Algorithm ] 큐

 

C++에서 queue 는 C++ 표준 라이브러리 (STL; Standard Template Library) 로 정의되어 있기에, 필요할 때 선언한다면 편리하게 사용할 수 있다.

 

Queue - 선언

먼저, queue 를 사용하기 위해서는 queue 라는 헤더 파일을 전처리기로 include 한 뒤 std::queue 을 정의해야 한다.

#include <queue>
std::queue<int> q1;
std::queue<char> q2;
std::queue<double> q3;

 

using namespace std; 선언을 한 상태라면 다음과 같이 선언할 수 있다.

#include <queue>
queue<int> q1;
queue<char> q2;
queue<double> q3;

 

각각 int 형 queue, char 형 queue, double 형 queue를 선언하였다.

 

이후 코드에 편의를 주기 위해 앞으로 등장하는 코드에서 using namespace std; 선언을 한 상태라고 가정한다.

 

Queue - 데이터 추가

queue 에 데이터를 추가하려면 push() 메소드를 활용한다.

반환형이 없는 void 메소드이다. O(1) 의 시간복잡도를 가진다.

void push(const value_type& _Val);

queue<int> q;
q.push(10);
q.push(20);
q.push(30);

 

Queue - 데이터 삭제

queue 에서 데이터를 삭제하려면 pop() 메소드를 활용한다. 가장 먼저 push 한 데이터가 먼저 삭제된다.

반환형이 없는 void 메소드이다. O(1) 의 시간복잡도를 가진다.

void pop();

queue<int> q;
q.push(10);
q.push(20);
q.push(30);

q.pop(); // 10 pop 
q.pop(); // 20 pop
q.pop(); // 30 pop

 

Queue - 데이터 검토

queue 에 데이터가 비어있는지, 몇 개의 데이터가 들어있는지 확인하기 위해 empty(), size() 메소드를 사용할 수 있다.

bool empty();

empty() 메소드는 큐가 비었다면 1, 비어있지 않다면 0을 반환하며 시간복잡도가 O(1) 인 메소드이다.

size_type size();

size() 메소드는 큐에 들어있는 데이터의 개수를 반환하며 시간복잡도가 O(1) 인 메소드이다.

queue<int> q;
q.push(10);
q.push(20);

cout << q.empty() << endl;
cout << q.size() << endl;

 

Queue - 데이터 가져오기

queue 는 제일 최상단에 있는 데이터 ( 가장 마지막에 넣은 데이터 ), 제일 최하단에 있는 데이터 ( 가장 먼저 넣은 데이터 ) 를 가져올 수 있다.

reference front();

front() 메소드는 큐에 제일 최하단에 있는 데이터를 반환하며 시간복잡도가 O(1) 인 메소드이다.

reference back();

back() 메소드는 큐에 제일 최상단에 있는 데이터를 반환하며 시간복잡도가 O(1) 인 메소드이다.

queue<int> q;
q.push(10);
q.push(20);
q.push(30);
q.push(40);

cout << q.front() << endl; // 10
cout << q.back() << endl; // 40

 

Queue - 전체 코드

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

int main(void) {
	queue<int> q;
	q.push(10);
	q.push(20);

	cout << "Empty? " << (q.empty() ? "Yes" : "No") << endl;
	cout << "Size : " << q.size() << endl;

	cout << "Front : " << q.front() << endl; // 10
	cout << "Back : " << q.back() << endl; // 20
	q.pop();

	q.push(30);

	cout << "Front : " << q.front() << endl; // 20
	cout << "Back : " << q.back() << endl; // 30
	q.pop();

	cout << "Front : " << q.front() << endl; // 30
	cout << "Back : " << q.back() << endl; // 30
	q.pop();

	cout << "Empty? " << (q.empty() ? "Yes" : "No") << endl;
	cout << "Size : " << q.size() << endl;

	return 0;
}

 

Queue - STL 을 이용한 문제 풀이

https://www.acmicpc.net/problem/18258

18258번: 큐 2

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

int main(void) {
	ios::sync_with_stdio(false); // Fase IO
	cin.tie(NULL);

	int n; cin >> n;
	queue<int> q;

	while (n--) {
		string str; cin >> str;
		if (!str.compare("push")) {
			int value; cin >> value;
			q.push(value);
		}
		else if (!str.compare("pop")) {
			if (q.empty()) cout << -1 << "\n";
			else {
				cout << q.front() << "\n";
				q.pop();
			}
		}
		else if (!str.compare("size")) cout << q.size() << "\n";
		else if (!str.compare("empty")) cout << q.empty() << "\n";
		else if (!str.compare("front")) {
			if (q.empty()) cout << -1 << "\n";
			else cout << q.front() << "\n";
		}
		else if (!str.compare("back")) {
			if (q.empty()) cout << -1 << "\n";
			else cout << q.back() << "\n";
		}
	}
	return 0;
}

Fast IO 를 신경써야 하는 문제이다.