[백준] 10845번_알고리즘_자료구조_큐

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

10845번: 큐

 

 

 

문제

정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 여섯 가지이다.

- push X: 정수 X를 큐에 넣는 연산이다.

- pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.

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

- empty: 큐가 비어있으면 1, 아니면 0을 출력한다.

- front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.

- back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.

스택과 큐

스택은 통조림이라고 생각하면 이해하기 쉽다.

토마토 통조림에서 맨 아래에 있는 토마토를 빼긴 힘들다.

맨 위에 있는 토마토부터 꺼내야 한다.

토마토 통조림을 만들 때 가장 처음 들어간 토마토는 맨 아래에 있는 토마토이고, 가장 나중에 들어간 토마토는 맨 위에 있는 토마토이다.

토마토 통조림을 먹는 사람은 가장 나중에 들어간 토마토를 가장 먼저 먹게 된다.

이것이 바로, 후입선출(LIFO : Last-In First-Out)이다.

영어 해석 그대로 "나중에 들어온 것이 먼저 나간다."라는 뜻이다.

스택도 이와 같다.

스택에 데이터를 삽입하면 가장 아래부터 차곡차곡 쌓여지고, 삭제를 하면 가장 위부터 사라진다.

​

큐는 터널이라고 생각하면 이해하기 쉽다.

<a href=' https://kr.freepik.com/vectors/car'>Car  벡터는 vectorpocket - kr.freepik.com가 제작함</a>

터널에서는 추월을 하면 안 된다.

즉, 터널에 먼저 들어간 차가 먼저 나가야 한다.

터널에 가장 먼저 들어간 차가 가장 먼저 터널을 나온다.

이것이 바로, 선입선출(FIFO : First-In First-Out)이다.

큐도 이와 같다.

큐에 가장 처음 들어온 데이터가 가장 먼저 나가게 된다.

스택은 구멍이 하나인 통조림과 같기 때문에 먼저 들어간 데이터는 가장 나중에 나가게 되지만,

큐는 구멍이 두 개 있는 터널과 같기 때문에 먼저 들어간 데이터가 가장 먼저 나가게 된다.

​

큐의 종류에는 선형 큐와 원형 큐가 있다.

선형 큐는 일자로 된 주차장이라고 생각하면 이해가 쉽다.

맨 앞에 있는 차가 나가고 난 빈자리는 차지 않고 그 뒤부터 차가 채워진다고 가정해보자.

맨 앞의 주차공간은 계속 비어져 있어 비효율적인 공간을 차지하게 된다.

즉, 선형 큐는 데이터가 처음 들어온 자리에 고정되어 그 데이터를 삭제해도 비어있는 인덱스로 남게 되어 메모리 낭비가 심하다.

원형 큐는 선형 큐의 단점을 극복한 큐로, 원형으로 된 선형 큐이다.

데이터가 큐의 최대 범위를 넘어가게 되면 동적으로 첫 번째 인덱스로 돌아가게 한다.

---

코드 설명

1. 사용한 라이브러리

#include <cstring>

strcmp를 이용하기 위함이다.

​

2. 광역 변수

모든 지역에서 쓸 수 있는 변수이다.

단, 반드시 광역 변수가 호출되기 전에 선언이 되어있어야 한다.

이 문제에서는 사용자에게 받는 명령을 담는 stack 배열과 배열의 가장 위에 있는 주소를 가리키는 address 변수를 광역 변수로 선언했다.

배열의 주소는 0부터 시작하므로 address는 -1로 지정하였고, 데이터가 들어올 때(push 함수) -1에 1을 더한 0으로 바꾸어 배열의 첫 번째 인덱스에 데이터를 삽입한다.

​

3. push 함수

void push(int x)

{

que[++address] = x;

}

정수 x를 큐에 넣는 함수이다.

현재 배열은 이미 값이 저장되어 있거나, 배열의 주소를 가리키고 있지 않기 때문에(address가 -1일 때)

++address를 해주어 배열의 주소를 하나 더해준다.

address++로하는 방법도 있는데 이럴 때는 문장을 실행한 뒤에 하나를 더한다.

반면에 ++address는 문장이 실행되기 전에 하나를 더하고 문장을 실행한다.

​

4. pop 함수

void pop()

{

int top_pop = 0;

if (address < 0) cout << "-1\n";

else {

top_pop = que[0];

for (int i = 0; i < address; i++) {

que[i] = que[i + 1];

}

que[address--] = 0;

cout << top_pop << "\n";

}

}

큐에서 가장 앞에 있는 정수(배열의 0번 인덱스)를 삭제하고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력하는 함수이다.

배열의 주소를 가리키는 address 변수가 0보다 작을 때는, 배열에 담긴 값이 없다는 뜻이므로 -1을 출력하고,

배열에 담긴 값이 있을 때는, 가장 앞에 있는 값(배열의 0번 인덱스)을 top_pop 변수에 담는다.

큐는 가장 앞에 있는 인덱스부터 삭제되고 그 인덱스가 비어있는 인덱스로 남아 메모리를 낭비한다.

이러한 점을 극복하기 위해 데이터가 삭제되면 그 뒤에 있는 데이터들을 하나씩 앞으로 옮겨주었다.

가장 뒤에 있는 값을 0으로 바꾸어 없애고, address를 하나 줄여서 배열의 크기를 줄인다.

그다음, 삭제할 가장 앞에 있는 값을 담은 top_pop을 출력한다.

줄바꿈은 endl로도 가능하지만, 수행 시간을 줄이기 위해 "\n"으로 대체한다.

​

5. size 함수

void size()

{

cout << address + 1 << "\n";

}

배열의 주소는 0부터 시작하기 때문에, size를 표현하기 위해서는 1을 더해주어야 한다.

​

6. empty 함수

void empty()

{

if (address < 0) cout << "1\n";

else cout << "0\n";

}

큐가 비어있으면 1, 아니면 0을 출력하는 함수이다.

address가 0보다 작으면 배열에 담긴 게 없다는 뜻이므로, 1을 출력하고, 0보다 크거나 같으면 배열에 하나 이상 담겨 있다는 뜻이므로 0을 출력한다.

​

7. front 함수

void front()

{

if (address < 0) cout << "-1\n";

else cout << que[0] << "\n";

}

큐의 가장 앞에 있는 정수를 출력하는 함수이다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력하는 함수이다.

가장 앞에 있는 주소는 0번 인덱스이므로 que 배열의 0번 인덱스에 들어있는 값을 출력하면 된다.

​

8. back 함수

void back()

{

if (address < 0) cout << "-1\n";

else cout << que[address] << "\n";

}

큐의 가장 뒤에 있는 정수를 출력하는 함수이다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력하는 함수이다.

address는 배열의 가장 뒤에 있는 주소를 가리키므로 que 배열의 address 주소에 있는 값을 출력하면 된다.

​

9. strcmp 함수

문자열 1과 문자열 2가 같으면 0을 반환하는 함수이다.

컴파일러는 0을 false로 인식하기 때문에, '!'('반대')를 앞에 쓰면 true가 된다.

그러므로 문자열 1과 문자열 2가 같으면 if 문을 실행하고, 다르면 if 문을 실행하지 않는다.

---

코드

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

int que[10000];
int address = -1;

void push(int x)
{
	que[++address] = x;
}

void pop()
{
	int top_pop = 0;
	if (address < 0) cout << "-1\n";
	else {
		top_pop = que[0];
		for (int i = 0; i < address; i++) {
			que[i] = que[i + 1];
		}
		que[address--] = 0;
		cout << top_pop << "\n";
	}
}

void size()
{
	cout << address + 1 << "\n";
}

void empty()
{
	if (address < 0)cout << "1\n";
	else cout << "0\n";
}

void front()
{
	if (address < 0) cout << "-1\n";
	else cout << que[0] << "\n";
}

void back()
{
	if (address < 0) cout << "-1\n";
	else cout << que[address] << "\n";
}

int main()
{
	int n, x;
	cin >> n;
	char command[10];

	for (int i = 0; i < n; i++)
	{
		cin >> command;
		if (!strcmp(command, "push")) {
			cin >> x;
			push(x);
		}
		else if (!strcmp(command, "pop")) pop();
		else if (!strcmp(command, "size")) size();
		else if (!strcmp(command, "empty")) empty();
		else if (!strcmp(command, "front")) front();
		else if (!strcmp(command, "back")) back();
	}

	return 0;
}

 

(컴퓨터공학과 과동아리 init 에서 큐에 대한 자세한 설명을 듣고, 스택 코드와 연관 지어 생각해 보면서 큐 코드를 만들었더니 한 번에 맞았다.)

​

​

​