[C++ STL] queue(큐)

큐(queue)

큐 한쪽 끝에서 자료를 넣고 반대 쪽 끝에서 자료를 꺼낼 수 있는 선입선출(FIFO, First In First Out)의 속성을 지닌다. (동적배열(vector)의 경우 맨 끝에서 자료를 넣는 것이 유사하지만 맨 앞에서 자료를 꺼내진 않음) 이는 일상생활과 아주 밀접한 자료구조이다. 예를들면 놀이공원이나 음식점에서 선 줄이나 할 일의 목록을 큐를 이용해 표현할 수 있다. 간단한 예제를 통해 기본적인 큐의 연산을 살펴보자.

 

 

• 큐 선언
• 요소 삽입/삭제
• 큐에서 꺼낸(삭제한) 요소 저장
• 큐의 각 요소 출력

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

int main() {

	//큐 선언
	queue<int> que;

	//큐에 요소 추가하기
	for (int i = 0; i < 5; i++) {
		que.push(i);
	}

	//요소 삭제하기
	int output = que.front();
	que.pop();
	
	//큐의 전체요소 출력하기
	while (!que.empty()) {
		cout << que.front() << " ";
		que.pop();
	}


	return 0;
}

queue의 멤버함수

멤버함수
q.empty()	비어있으면 true 아니면 false를 리턴
q.size()	원소의 수를 리턴
q.front()	맨 앞 원소 리턴
q.back()	맨 뒤 원소 리턴
q.push(a)	맨 뒤에 원소 a를 추가
q.pop()	맨 앞 원소 삭제

예제 (요세푸스 문제)

선형자료구조 포스팅에서 풀었던 요세푸스문제도 큐를 이용하여 더 간단하게 풀 수 있다. 연결리스트를 이용할 때는 원형연결리스트를 흉내내기 위해 포인터가 리스트의 마지막을 가리키면 다시 첫번째를 가리키도록 바꿔줘야했다. 하지만 큐를 이용하면 그런 수고로움을 덜 수 있다.

 

1. 첫번째 사람이 죽는다.
2. 맨 앞에 있는 사람을 뒤로 보내는 작업을 k-1번한다.
3. 1,2번을 두 명이 남을 때 까지 반복한다.

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

void jopsep(int N, int K);
int main() {
	int T;
	pair<int, int> data[100];
	cin >> T;


	for (int i = 0; i < T; i++) {
		cin >> data[i].first >> data[i].second;
	}

	for (int i = 0; i < T; i++) {
		int N = data[i].first;
		int K = data[i].second;
		jopsep(N, K);
	}


	return 0;
}


void jopsep(int N, int K) {
	queue<int> survivor;

	for (int i=1; i <= N; i++) {
		survivor.push(i);
	}

	while (N > 2) {
		survivor.pop();
		N--;
		for (int i = 0; i < K - 1; i++) {
			int a = survivor.front();
			survivor.pop();
			survivor.push(a);
		}

	}

	while(!survivor.empty()) {
		cout << survivor.front()<< " ";
		survivor.pop();

	}
	cout << endl;

}

예제 (외계 신호 분석)

외계에서 신호 N개가 순차적으로 들어올 때 부분합이 K가 되는 갯수를 구하는 문제

 

입력: test case갯수, N, K

출력: 부분합이 K가 되는 구간의 갯수

 

#include<iostream>
#include<queue>
using namespace std;
int countRanges(int K, int N);

const int MOD = 10000;
struct RNG {
	unsigned signal;
	RNG() : signal(1983){}
	unsigned next() {
		unsigned out = signal % MOD + 1;
		signal = (signal * 214013u + 2531011u);
		return out;
	}
};
int main() {

	int T;
	pair<int, int> data[30];
	cin >> T;
	for(int i = 0; i < T; i++) {
		cin >> data[i].first >> data[i].second;
	}

	for (int i = 0; i < T; i++) {
		cout << countRanges(data[i].first, data[i].second)<<endl;
		
	}
	
	return 0;
}

int countRanges(int K, int N) {
	RNG rng;
	queue<int> range;
	int count = 0;
	int sum = 0;

	for (int i = 0; i < N; i++) {
		int a = rng.next();
		sum += a;
		range.push(a);

		while (sum > K) {
			sum -= range.front();
			range.pop();
		}
		if(sum==K) count++;
	}


	return count;
}

Reference

프로그래밍 대회에서 배우는 알고리즘 문제해결전략, 구종만