백준 18258 - 큐 2

이 문제를 풀기 위해선 먼저 큐 자료구조에 대해 이해하고 있어야 합니다.

큐 자료구조는 선입선출(FIFO) 구조를 가지고 있어 먼저 들어온 요소가 먼저 나가는 방식입니다. 그러기에 어떻게 삽입하고 어떻게 내보낼지 효율적으로 만드는 것이 중요합니다.

이 문제에서는 삽입에서 for을 이용해 모든 요소를 한칸씩 밀면 시간초과가 발생합니다.
그래서 for을 이용하지 않고 큐의 시작과 끝을 가리키는 변수 front, rear를 만들어 삽입은 rear에 하고 내보내는건 front에 했습니다.

이 방식은 메모리 효율이 떨어지는 방식입니다. 이 문제를 해결하기 위해선 원형 큐를 활용해 해결할 수 있습니다.

#include <iostream>
#include <string>

int main()
{
	std::cin.tie(NULL);
	std::ios_base::sync_with_stdio(false);

	int n;
	std::cin >> n;

	int* queue = new int[n + 1];
	int front = -1;
	int rear = -1;

	for (int i = 0; i < n; i++)
		queue[i] = -1;

	for (int i = 0; i < n; i++)
	{
		std::string str;
		int temp;
		std::cin >> str;
		if (str.compare("push") == 0)
		{
			std::cin >> temp;
			queue[++rear] = temp;
		}
		else if (str.compare("pop") == 0)
		{
			if (rear != front)
			{
				std::cout << queue[++front] << "\n";
				queue[front] = -1;
			}
			else
				std::cout << "-1\n";
		}
		else if (str.compare("size") == 0)
		{
			std::cout << rear - front << "\n";
		}
		else if (str.compare("empty") == 0)
		{
			if (rear == front)
				std::cout << "1\n";
			else
				std::cout << "0\n";
		}
		else if (str.compare("front") == 0)
		{
			if (rear != front)
				std::cout << queue[front + 1] << "\n";
			else
				std::cout << "-1\n";
		}
		else if (str.compare("back") == 0)
		{
			if (rear != front)
				std::cout << queue[rear] << "\n";
			else
				std::cout << "-1\n";
		}
	}

	return 0;
}