[백준] 18258번 큐 2 / C++

#문제

백준 18258번 큐 2

#풀이

#include <iostream>
#include <string>
#include <memory>

using namespace std;

struct Node
{
	int data;
	Node* prevNode;
	unique_ptr<Node> nextNode;

	Node(int x) : data(x), prevNode(nullptr), nextNode(nullptr) {}
};

class Queue
{
	int size;
	unique_ptr<Node> front;
	Node* back;

public:
	Queue() : size(0), front(nullptr), back(nullptr) {}

	void Push(int x)
	{
		auto newNode = make_unique<Node>(x);
		Node* newRawNode = newNode.get();

		if (size < 1)
		{
			front = move(newNode);
			back = newRawNode;
		}
		else
		{
			back->nextNode = move(newNode);
			newRawNode->prevNode = back;
			back = newRawNode;
		}

		size++;
	}

	void Pop()
	{
		if (size < 1)
		{
			cout << "-1" << '\n';
		}
		else
		{
			cout << front->data << '\n';

			if (size == 1)
			{
				front = nullptr;
				back = nullptr;
			}
			else
			{
				front = move(front->nextNode);
				front->prevNode = nullptr;
			}

			size--;
		}
	}

	void Size()
	{
		cout << size << '\n';
	}

	void Empty()
	{
		if (size == 0)
		{
			cout << '1' << '\n';
		}
		else
		{
			cout << '0' << '\n';
		}
	}

	void Front()
	{
		if (size == 0)
		{
			cout << "-1" << '\n';
		}
		else
		{
			cout << front->data << '\n';
		}
	}

	void Back()
	{
		if (size == 0)
		{
			cout << "-1" << '\n';
		}
		else
		{
			cout << back->data << '\n';
		}
	}
};

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n;
	cin >> n;

	auto q = make_unique<Queue>();

	while (n--)
	{
		string str;
		cin >> str;

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

			q->Push(x);
		}
		else if (str == "pop")
		{
			q->Pop();
		}
		else if (str == "size")
		{
			q->Size();
		}
		else if (str == "empty")
		{
			q->Empty();
		}
		else if (str == "front")
		{
			q->Front();
		}
		else if (str == "back")
		{
			q->Back();
		}
	}

	return 0;
}

#정리

최대 2,000,000 명령을 처리하는 큐를 만들었다. 큐 1 문제에서는 shared_ptr을 사용하여 쉽게 해결했는데, 같은 코드로 제출해보니 시간초과에 걸렸다. shared_ptr의 오버헤드가 문제일 것이라는 가정 하에 unique_ptr와 raw pointer로 변경하였더니 해결할 수 있었다.




    Enjoy Reading This Article?

    Here are some more articles you might like to read next:

  • [백준] 10845번 큐 / C++
  • [백준] 10866번 덱 / C++
  • [백준] 10828번 스택 / C++
  • [백준] 25206번 너의 평점은 / C++
  • [백준] 4949번 균형잡힌 세상 / C++