[BOJ] 10828 - 스택

스택 뽀개기 프로젝트 - 1

이제부터 BOJ 단계 별 문제의 스택 카테고리에 있는 모든 문제를 풀어볼까 한다.

STL을 쓰면 간단하지만 첫 번째 문제인 10828번이 스택을 직접 만드는 문제이기 때문에 직접 만들어서 앞으로의 문제들에선 내 스택 라이브러리를 쓰기로 하겠다.

예전에 자료구조 공부할 때 만들어 둔 C언어 라이브러리가 있긴 한데, 그때의 나에대한 불신과 C++로, 템플릿을 이용하여 다시 짜보고 싶다는 점 때문에 다시 짜보겠다.

문제

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

스택의 기본 ADT를 작성하고 입출력을 수행하는 문제

난이도

난이도 中, 소요시간 40분 

풀이 과정

10828번에서 만들라는 스택은 int형 데이터를 받는 스택인데, 템플릿을 이용하여 int형이 아니라 다른 어떤 형태의 데이터를 받아도 스택이 만들어질 수 있게끔 구현해보기로 하겠다. 

하지만 이 때문인지 아니면 클래스 안에 또 다른 클래스를 선언해서 그런지 10828번의 답을 제출하면 런타임 에러가 나므로... BOJ에서 [성공!]이 나오진 않았다. BOJ 컴파일러 문제 있는듯...

그래도 나만의 스택 라이브러리를 만든 것에 의의를 뒀다.

먼저 MyStack이라는 클래스를 만든다.

template <typename T>
class MyStack
{
public:
	class MyNode
	{
	public:
		T data;
		MyNode* next;

		MyNode(T _data)
			: data(_data)
		{ }
	};
};

클래스 안에 MyNode라는 클래스를 넣었다. 아마 예전 C++에서는 지원되지 않는 기능으로 알고 있는데, 이 때문에 BOJ에서 컴파일 에러가 나는 것 같다.

각 노드에는 T라는 자료형(아무거나)의 데이터가 저장되고 다음 노드를 가리키는 next라는 포인터를 가지고 있다.

노드의 생성자는 해당 데이터를 받는다.

이제 원래 스택을 짜듯이 짜주면 된다. 

MyStack 클래스의 필드 변수(자바에선 필드인데 C++로는 멤버 변수인가?? 기억이 안난다.)로는 현재 가장 위에 있는 노드를 가리키는 top이라는 포인터와 현재 스택의 사이즈를 나타내는 size라는 int형 변수가 있다.

스택의 ADT에 따라

isEmpty, push, pop 함수가 필요하고, 현재 가장 위에 있는 데이터를 알 수 있는 getTop함수와 스택 사이즈(원소의 개수)를 알 수 있는 getSize함수를 추가하였다. 이는 top과 size라는 필드 변수를 private으로 선언해주었기 때문이다.

마지막으로, 스택 내에 있는 노드들을 순차적으로 탐색하며 모든 원소를 출력하는 display 함수를 만들었다.(display함수는 템플릿 함수로 만들었다.)

최대한 간단하게 짰으니 코드 이해가 쉬울 것 같아서 더 이상 자세한 설명은 생략한다.

stack.h

template <typename T>
class MyStack
{
public:
	class MyNode
	{
	public:
		T data;
		MyNode* next;

		MyNode(T _data)
			: data(_data)
		{ }
	};

	bool isEmpty()
	{
		if (top == nullptr)
			return true;
		else
			return false;
	}

	void push(T _data)
	{
		MyNode* n = new MyNode(_data);

		n->next = top;
		top = n;
		
		size++;
	}

	T pop()
	{
		T removedData = T(-1);	// 강제 형변환
		if (!isEmpty())
		{
			MyNode* removed = top;	// 제거될 놈
			removedData = removed->data;

			top = top->next;
			delete removed;		// 객체를 제거하여 메모리 해제

			size--;
		}
		return removedData;
	}

	T getTop()
	{
		return top->data;
	}

	int getSize()
	{
		return size;
	}

	void display()
	{
		MyNode* temp = top;
		while (temp != nullptr)
		{
			std::cout << temp->data << std::endl;	// 계속 pop해서 나온 값을 출력
			temp = temp->next;
		}
	}

private:
	MyNode* top = nullptr;
	int size;
};

template <typename T>
void display(MyStack<T> s)
{
	while (!s.isEmpty())
		cout << s.pop() << endl;	// 계속 pop해서 나온 값을 출력
}

메인함수는 매우 간단하게 문자열을 먼저 받고, push이면 숫자를 입력받도록 한 후 입력받은 문자열에 따른 함수를 실행하여 반환값을 출력하도록 하였다.

main.cpp

#include <iostream>
#include <string>

using namespace std;

int main(void)
{
	MyStack<int> s;
	int n = 0;

	cin >> n;
	for (int i = 0; i < n; i++)
	{
		string operation;
	
		int data = 0;
		cin >> operation;
		if (operation == "push")
		{
			cin >> data;
			s.push(data);
		}
		else if (operation == "pop")
			cout << s.pop() << endl;
		else if (operation == "empty")
			cout << s.isEmpty() << endl;
		else if (operation == "size")
			cout << s.getSize() << endl;
		else if (operation == "top")
			cout << s.getTop() << endl;
		else
			s.display();
	}
	return 0;
}

이제 스택 헤더 파일을 만들어 놨으니 다음 번 스택 문제에 활용하면 된다~