(2024-2 자료구조반) 3. 큐

권용훈·2025년 2월 2일

gbsw 재학생 부트캠프 - 2024 winter

gbsw 부트캠프 시리즈

목록 보기

15/32

지난 시간에는 후입선출형태의 자료구조인 스택을 알아보았습니다.
이번 시간에는 선입선출형태의 자료구조인 큐를 알아보겠습니다.

1) 정의

가장 먼저 들어간 데이터가 가장 먼저 나오는 형태의 자료구조입니다.

FIFO(First In First Out)라고도 부릅니다.

스택은 데이터가 들어오는 곳, 나오는 곳이 같은 것과 달리,
큐는 데이터가 들어오는 곳, 나오는 곳이 다릅니다.

스택을 배웠을 때와 같이,
문제를 하나 풀어보면서 큐를 이해해봅시다.

10845번 문제

다음 6가지 쿼리를 수행하는 문제입니다.

push X: 정수 X를 큐에 넣는다.

pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 큐가 비어있다면 -1를 출력한다.

size: 큐에 있는 정수의 개수를 출력한다.

empty: 큐가 비어있는지 확인한다.

front: 큐에서 가장 앞에 있는 정수를 출력한다. 큐가 비어있다면 -1를 출력한다.

back: 큐에서 가장 뒤에 있는 정수를 출력한다. 큐가 비어있다면 -1를 출력한다.

문제에서 요구하는 쿼리이자, 큐의 기본적인 연산입니다.

(0) 큐의 요소

큐를 사용하기 위해서는, 보통은 다음 세 가지 변수를 선언합니다.

queue[]: 데이터를 저장할 곳입니다.
front: 큐의 가장 앞에 있는 데이터의 앞을 가리키는 변수입니다. 초기값은 -1입니다.
rear: 큐의 가장 뒤에 있는 데이터를 가리키는 변수입니다. 초기값은 -1입니다.

큐에 데이터 하나가 들어오면, rear는 1 증가하여 0이 됩니다.
이 수는 큐의 가장 뒤의 데이터가 있는 인덱스를 가리킵니다.

큐에 데이터 하나를 꺼내면, front는 1 증가하여 0이 됩니다.
이 수는 큐의 가장 앞의 데이터의 앞의 인덱스를 가리킵니다.

front는 문제에서 요구하는 함수인 front와 이름이 같기에, 이번에 한해 큐의 변수인 front와 rear를 각각 f, r로 표기하겠습니다.

(1) push

다음과 같이 구현할 수 있습니다.

// 큐의 맨 위를 가리키는 변수를 올린 후, 값 저장
void push(int x) {
	queue[++r] = x;
}

스택과 같습니다.

(2) pop

다음과 같이 구현할 수 있습니다.

int pop(){
	// 큐가 비어있는 경우
	if (f == r)
		return -1;

	// 반환 후 큐 사이즈 줄이기
	return queue[(f++)+1];
}

f와 r이 같다면, 큐가 비어있다는 뜻이기에 -1를 반환합니다.

그것이 아니라면, 큐의 맨 앞 데이터를 반환한 후,
f를 1 증가시킴으로써 데이터를 없앱니다.

(3) size

다음과 같이 구현할 수 있습니다.

int size() {
	// 맨 뒤 인덱스 - 맨 앞 인덱스
	return r - f;
}

큐의 가장 뒤의 인덱스에서 가장 앞의 인덱스의 인덱스를 뺌으로써,

큐의 사이즈를 알 수 있습니다.

(4) empty

다음과 같이 구현할 수 있습니다.

int empty() {
	// f = r이면, 비어있는 스택
	return f == r ? 1 : 0;
}

비어있으면 1, 아니면 0을 반환하면 됩니다.

(5) front

다음과 같이 구현할 수 있습니다.

int front() {
	// 큐가 비어있는 경우
	if (f == r)
		return -1;

	return queue[f + 1];
}

문자 네 개를 제외하면
pop과 완전히 같습니다.

(6) back

다음과 같이 구현할 수 있습니다.

int back() {
	// 큐가 비어있는 경우
	if (f == r)
		return -1;

	return queue[r];
}

변수 하나를 제외하면
front와 완전히 같습니다.

(7) 정답 코드

여러분은 큐의 기본적인 연산을 모두 이해하였습니다.
다음은 이 문제의 올바른 코드입니다.

// made by biggrace681
#include <iostream>
using namespace std;

int queue[10000]{}, f = -1, r = -1;

// 스택의 맨 위를 가리키는 변수를 올린 후, 값 저장
void push(int x) {
	queue[++r] = x;
}

int pop() {
	// 큐가 비어있는 경우
	if (f == r)
		return -1;

	// 반환 후 큐 사이즈 줄이기
	return queue[(f++) + 1];
}

int size() {
	// 맨 뒤 인덱스 - 맨 앞 인덱스
	return r - f;
}

int empty() {
	// f = r이면, 비어있는 스택
	return f == r ? 1 : 0;
}

int front() {
	// 큐가 비어있는 경우
	if (f == r)
		return -1;

	return queue[f + 1];
}

int back() {
	// 큐가 비어있는 경우
	if (f == r)
		return -1;

	return queue[r];
}

int main() {

	int n; cin >> n;

	while (n--) {

		string query; cin >> query;

		if (query == "push") {
			int x;cin >> x;
			push(x);
		}

		if (query == "pop")
			cout << pop() << '\n';

		if (query == "size")
			cout << size() << '\n';

		if (query == "empty")
			cout << empty() << '\n';

		if (query == "front")
			cout << front() << '\n';

		if (query == "back")
			cout << back() << '\n';

	}

}