[C++] BOJ 10845번: 큐

문제

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

명령은 총 여섯 가지이다.

• push X: 정수 X를 큐에 넣는 연산이다.
• pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• size: 큐에 들어있는 정수의 개수를 출력한다.
• empty: 큐가 비어있으면 1, 아니면 0을 출력한다.
• front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.

입력

15
push 1
push 2
front
back
size
empty
pop
pop
pop
size
empty
pop
push 3
empty
front

출력

1
2
2
0
1
2
-1
0
1
-1
0
3

 

코드

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

// 10845번 큐

//큐 구현
class QueueS {
public:
	int front;
	int back;
	int size;
	int *values;		//모든 값들을 담은 배열을 가리키는 포인터

	//생성자
	QueueS() {
		size = 10001;		//큐의 사이즈 
		values = new int[size];
		front = 0;
		back=0;
	}
	//소멸자
	~QueueS() {
		delete[] values;
	}

	void push(int data) {
		if ((back+1)%size!=front) {
			values[back] = data;
			back = (back + 1) % size;
		}
	}

	void pop() {
		front = (front + 1) % size;
	}

	bool empty() {
		if (back == front)
			return true;
		else
			return false;
	}
};

QueueS st;

void getNumSize(string str) {
	int temp;

	if (str == "back") {
		if (st.back - st.front != 0) {
			cout << st.values[st.back - 1] << "\n";
		}
		else cout << "-1\n";
	}
	else if (str == "front") {
		if (st.back - st.front != 0) {
			cout << st.values[st.front] << "\n";
		}
		else cout << "-1\n";
	}
	else if (str == "size") {
		cout << st.back-st.front << "\n";
	}
	else if (str == "empty") {
		cout << ((st.back - st.front==0)?true:false) << "\n";
	}
	else if (str == "pop") {
		if (st.back - st.front!=0) {
			cout << st.values[st.front] << "\n";
			st.pop();
		}
		else {
			cout << "-1\n";
		}
	}
	else if (str == "push")
	{
		cin >> temp;
		st.push(temp);
	}
}

int main() {

	int n;
	string str;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> str;
		getNumSize(str);
	}

	return 0;
}

 

*간단한 해설*

큐를 클래스를 이용하여 구현하였다. 큐 클래스의 front,back은 일종의 맨 앞의 index 번호를 말하는 것이고, back은 맨 뒤의 index번호를 말하는 것이다. 그리고 int* values를 통해서 입력 받은 값들을 back을 늘려가면서 저장하였다.

 

 

C 구조체와 C++의 queue 라이브러리를 이용하여 구현하신 분도 있었다.

https://blockdmask.tistory.com/119

[백준 10845] 큐 (C, C++ Queue)

내 코드는 헤더를 추가하지 않는데 시간이 너무 길어서.. 블로그 글을 참고하다 보니 아무래도 cout문제도 있을 것 같아서 printf로 한번 다 바꿔보았다.

 

그렇게까지 영향을 준건 아닌가보다 싶어서 좀 더 찾아보니

https://coding-insider.tistory.com/entry/cin-cout-%EC%9E%85%EC%B6%9C%EB%A0%A5-%EC%86%8D%EB%8F%84-%EB%B9%A0%EB%A5%B4%EA%B2%8C%ED%95%98%EB%8A%94-%EB%B0%A9%EB%B2%95

cin, cout 입출력 속도 빠르게 하는 방법

cin의 속도가 생각보다 엄청 느리다는것! 

ios_base :: sync_with_stdio(false); 
cin.tie(NULL); 
cout.tie(NULL);

이 코드를 추가해주면 빨라진다고는 하나 scanf,printf와 같이 사용하면 안되고 싱글쓰레드 영역에서만 사용 가능해서 실제 코드 영역에서는 사용하는 것을 지양하라고 한다.

일단 싱글 쓰레드 영역이니 쟤들을 추가해서 한번 돌려보았다.

 

속도는 빨라졌지만 메모리는 늘어났다.. 그러면 scanf,printf로 다 바꿔보겠다.

 

결과적으로는 메모리도 줄어들었다. 아무래도 scanf,printf로 출력하는 방식으로 앞으로도 써야겠다.

 

코드(scanf,printf)

#include<iostream>
#include<string.h>
using namespace std;

// 10845번 큐
//큐 구현
class QueueS {
public:
	int front;
	int back;
	int size;
	int *values;		//모든 값들을 담은 배열을 가리키는 포인터

	//생성자
	QueueS() {
		size = 10001;		//큐의 사이즈 
		values = new int[size];
		front = 0;
		back = 0;
	}
	//소멸자
	~QueueS() {
		delete[] values;
	}

	void push(int data) {
		if ((back + 1) % size != front) {
			values[back] = data;
			back = (back + 1) % size;
		}
	}

	void pop() {
		front = (front + 1) % size;
	}

	bool empty() {
		if (back == front)
			return true;
		else
			return false;
	}
};

QueueS st;

void getNumSize(char str[]) {
	int temp;

	if (!strcmp(str, "back")) {
		if (st.back - st.front != 0) {
			printf("%d\n", st.values[st.back - 1]);
		}
		else printf("-1\n");
	}
	else if (!strcmp(str,"front")) {
		if (st.back - st.front != 0) {
			printf("%d\n", st.values[st.front]);
		}
		else printf("-1\n");
	}
	else if (!strcmp(str ,"size")) {
		printf("%d\n", st.back - st.front);
	}
	else if (!strcmp(str,"empty")) {
		printf("%d\n", ((st.back - st.front == 0) ? true : false));
	}
	else if (!strcmp(str, "pop")) {
		if (st.back - st.front != 0) {
			printf("%d\n", st.values[st.front]);
			st.pop();
		}
		else {
			printf("-1\n");
		}
	}
	else if (!strcmp(str,"push"))
	{
		scanf("%d", &temp);
		st.push(temp);
	}
}

int main() {

	int n;
	char str[6];
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%s", str);
		getNumSize(str);
	}

	return 0;
}

 

*이 방법만이 맞는 정답은 아닙니다.

훨씬 좋고 빠른 다른 알고리즘을 구현할 수 있습니다.

알고리즘 공부하시는 분들 화이팅! '0'/*