자료구조 : 큐(queue)

 

1. 큐의 정의

큐(queue)는 먼저 집어 넣은 데이터가 먼저 나오는 FIFO (First In First Out)구조로 저장하는 형식을 말한다.

영어 단어 queue는 표를 사러 일렬로 늘어선 사람들로 이루어진 줄을 말하기도 하며, 먼저 줄을 선 사람이 먼저 나갈 수 있는 상황을 연상하면 된다.

한쪽 끝에서만 데이터를 넣고 다른 한쪽 끝에서만 데이터를 뺄 수 있다.

나중에 집어 넣은 데이터가 먼저 나오는 스택과는 반대되는 개념이다.

 

2. 큐의 함수

push : 큐에 자료를 넣음 

pop : 큐에서 자료를 뺌

front : 큐의 가장 앞에 있는 자료

back : 큐의 가장 뒤에 있는 자료 

empty : 큐가 비어있는지 아닌지

size : 큐에 저장되어있는 데이터의 개수

 

C++의 경우 STL의 queue, Java의 경우 Java.util.Queue를 사용

 

3. 큐의 구현

push 함수

queue[end] = val;

end +=1;

 

pop함수 

queue[begin] = NULL;

begin +=1;

 

size함수

end-begin

 

empty함수

begin==end

// 이런식으로 배열을 이용해서 큐를 구현할 경우 공간복잡도가 증가하여 메모리를 많이 낭비할 것이다.

// 고로 큐는 연결리스트를 이용하여 구현 되어 있다.

 

3. 큐 관련 문제 풀이

백준 10845번 큐 : https://www.acmicpc.net/problem/10845

큐를 구현하는 문제

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

queue<int> q;

int main(void) {
	int t;
	cin >> t;
	while (t--) {
		string cmd;
		cin >> cmd;
		if (cmd == "push") {
			int num;
			cin >> num;
			q.push(num);
		}
		else if (cmd == "pop") {
			if (!q.empty()) {
				cout << q.front() << endl;
				q.pop();
			}
			else cout << "-1" << endl;
		}
		else if (cmd == "size") {
			cout << q.size() << endl;
		}
		else if (cmd == "empty") {
			cout << q.empty() << endl;
		}
		else if (cmd == "front") {
			cout << (q.empty() ? -1 : q.front()) << endl;
		}
		else if (cmd == "back") {
			cout << (q.empty() ? -1 : q.back()) << endl;
		}
	}
}

 

백준 1158번 조세퍼스 : https://www.acmicpc.net/problem/1158

큐를 사용한 시뮬레이션 문제

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 M(<=N)이 주어진다.

순서대로 M번째 사람을 제거한다.

원에서 사람들이 제거되는 순서를 (N,M)-조세퍼스 순열이라고 한다.

위 문제와 같이 끝과 처음이 연결된 문제를 풀때 큐 또는 배열에 나머지 연산자를 사용하여 푸는 것이 좋다.

k번째 사람을 pop하고 출력하며 나머지는 처음에서 끝으로 넣어주면 되는 문제이다.

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

queue<int> q;

int main(void) {
	int n, k;
	cin >> n >> k;

	for (int i = 1; i <= n; ++i) q.push(i);
	cout << "<";
	for (int i = 0; i < n-1; ++i) {
		for (int j = 0; j < k; ++j) {
			if (j == k - 1) {
				cout << q.front() << ", ";
				q.pop();
			}
			else {
				q.push(q.front());
				q.pop();
			}
		}
	}

	cout <<q.front()<< ">";
	//system("pause");
}