큐 강의 정리

큐(Queue)

 

스택은 LIFO

큐는 FIFO

 

 

STL Queue에는 인덱스를 가지고 내부 원소 접근하는 기능이 없어

 

큐는 한쪽 끝에서 원소를 넣고 반대쪽 끝에서 원소를 뺄 수 있는 자료구조입니다. 스택에서는 먼저 들어간 원소가 나중에 나왔는데 큐에서는 먼저 들어간 원소가 먼저 나오게 됩니다. 공항에서 입국수속을 하는 줄과 같은 상황이라고 볼 수도 있습니다.

 

스택을 FILO(First In Last Out)이라고 한 것과 비슷하게 큐를 FIFO(First in First Out)이라고 하기도 합니다.

-바킹독-

 

큐에서 연산의 시간복잡도를 보면 스택처럼 원소의 추가와 제거가 모두 O(1)입니다. 스택에서는 보통 원소가 추가되고 제거되는 곳을 top이라고 부르고, 원소가 위 아래로 배치된 것으로 생각을 많이 하는데 큐에서는 추가되는 곳을 rear, 즉 뒤쪽이라고 하고 제거되는 쪽을 front, 즉 앞쪽이라고 합니다. 아무튼 가장 앞쪽에 위치해있거나 가장 뒤쪽에 위치한 원소의 확인도 O(1)입니다.

 

4번 성질에 대한 얘기는 이미 스택 단원에서 충분히 언급을 했기 때문에 여기서는 설명을 깊게 하지는 않을 것입니다. 요약해서 다시 말을 해보면 스택과 비슷한 맥락으로 큐라는 자료구조에서는 인덱스를 가지고 원소에 접근하는 기능이 없지만, 배열을 가지고 직접 만들 땐 해당 기능이 가능하도록 구현을 할 수 있다 정도로 요약이 가능합니다. 단, STL queue에는 인덱스로 내부 원소를 접근하는 기능이 없습니다.

-바킹독-

 

push를 할 때는 tail이 증가하고 pop을 할 때는 head가 증가 (슬라이드 쭉 보기)

이러다 보면 안 쓰는 공간 많잖아... 그걸 효율적으로 하기 위해 원형 큐를 만들었어!

이와 같이 스택과는 다르게 큐는 배열로 구현하면 삭제가 발생할 때 마다 앞쪽에 쓸모없는 공간이 계속 생기게 됩니다. 이 문제를 해결하는 방법은 의외로 간단한데 큐의 원소가 들어갈 배열을 원형으로 만드는 것입니다. 관념적으로는 배열이 원형인거고, 실제 구현을 할 땐 head나 tail이 7인 상태에서 1이 더해질 때 0번지로 다시 오도록 만들면 됩니다.

-바킹독-

 

직접 큐를 구현해보자

해당 example을 참고 (55는 다른 값으로 덮어 쓸 필요 없음-어차피 head가 이동할 것이기 때문)

 

틀린 부분 살펴보자.

#include <iostream>
using namespace std;

const int MX = 1000005;
int dat[MX];
int head = 0, tail = 0;

void push(int x) {
	// push를 하면 tail이 증가하고 head는 그대로다.
	//틀린 부분 - tail에다가 push할 대상을 넣고 tail++을 해준다!
	dat[tail] = x;
	tail++;
}

void pop() {
	// pop을 하면 head가 증가하고 tail은 그대로다.
	head++;
}

int front() {
	int fr = dat[head];
	return fr;
}

int back() {
	int bk = dat[tail-1]; // 여기 틀림
	return bk;
}

void test() {
	push(55);
	push(17);
	pop();
}

int main(void) {
	test();
}

push() 틀림 : tail이 가리키는 공간은 빈 공간-그래서 tail에다가 push해준다. head에다가 push해주는게 아니다.

tail에다가 push하니 push 후에 tail이 증가하는 거다.

back() 틀림 : tail이 원초적으로 빈 공간을 가리켜서 제일 마지막 숫자는 tail-1로 접근을 해야 한다.

 

 

물론 STL에 큐도 있습니다.(레퍼런스 링크, 예제 링크) 보통 큐는 BFS랑 Flood Fill를 할 때 쓰게 되는데 둘 다 코딩테스트 단골 문제여서 문제를 풀 때 STL queue를 쓸 일이 아주 많을 것입니다. 그래서 나중 가면 적어도 STL queue 만큼은 외우기 싫어도 외워질 것입니다.

 

그리고 큐가 비어있는데 front나 back이나 pop을 호출하면 런타임에러가 발생할 수 있다는 점은 주의를 하셔야 합니다.

STL Queue

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

int main(void) {
	queue<int> Q;
	Q.push(10); // 10
	Q.push(20); // 10 20
	Q.push(30); // 10 20 30
	cout << Q.size() << '\n'; // 3
	if (Q.empty()) cout << "Q is empty\n";
	else cout << "Q is not empty\n"; // Q is not empty
	Q.pop(); // 20 30
	cout << Q.front() << '\n'; // 20
	cout << Q.back() << '\n'; // 30
	Q.push(40); // 20 30 40
	Q.pop(); // 30 40
	cout << Q.front() << '\n'; // 30

}

 

그리고 백준 10845 큐 문제를 연습해보자.

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

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	queue<int> Q;
	int n;
	cin >> n;
	while (n--) {
		string q;
		cin >> q;
		if (q == "push") { // 문자열이 push ~~이면
			// push 3 같은 문자열을 받는 기법!
			int val;
			cin >> val;
			Q.push(val);
		}
		else if (q == "pop") {
			if (Q.empty()) cout << -1 << '\n';
			else {
				cout << Q.front() << '\n';
				Q.pop();
			}
		}
		else if (q == "size") {
			cout << Q.size() << '\n';
		}
		else if (q == "empty") {
			cout << Q.empty() << '\n';
		}
		else if (q == "front") {
			if (Q.empty()) cout << -1 << '\n';
			else cout << Q.front() << '\n';
		}
		else { // back
			if (Q.empty()) cout << -1 << '\n';
			else cout << Q.back() << '\n';
		}
	}
}

 

바킹독 큐) https://blog.encrypted.gg/934