[Algorithm][BOJ][10828] 스택

스택

1. 요구사항 분석
2. 알고리즘 선택
3. 풀이 분석
4. 최적화

요구사항 분석

스택의 여러 명령어들 중
PUSH, POP, SIZE, EMPTY, TOP을 각각 구현하고 예외사항을 처러하도록 합니다.
스택의 최대 길이는 10’000 이하로 제한되어 있습니다.

올라가기

알고리즘 선택

스택은 FILO(First In Last Out)의 대표적인 자료구조 중 하나입니다.
TOP 노드를 지정하고 TOP 노드에서만 PUSH, POP 연산이 진행됩니다.
따라서 각 노드는 다음 노드를 가르키는 포인터와 소유하는 값으로 구성됩니다.

STL을 사용하여 짧은 코드를 사용할 수 있지만 연습을 위해 직접 구현해보는 것을 추천합니다.

올라가기

풀이 분석

#include <iostream>

class NODE {
	NODE* next;
	int val;

public:
	NODE(int inV) : val(inV), next(nullptr) { }
	
	int get() { return val; }
	int set(int v) { val = v; }
	void set_next(NODE* nn) { next = nn; }
	NODE* get_next() { return next; }
};

int main() {
	int N = 0;
	std::cin >> N;
	NODE* top = nullptr;
	int size = 0;

	for (int i = 0; i < N; ++i) {
		std::string order;
		std::cin >> order;
		if (order == "push") {
			int newNum;
			std::cin >> newNum;
			NODE* newNode = new NODE(newNum);
			
			if (top == nullptr) {
				top = newNode;
			}
			else {
				newNode->set_next(top);
				top = newNode;
			}
			size += 1;
		}
		else if (order == "pop") {
			if (top == nullptr) printf("-1\n");
			else {
				printf("%d\n", top->get());
				NODE* delNode = top;
				top = top->get_next();
				delete delNode;
				size -= 1;
			}
		}
		else if (order == "size") {
			if (top == nullptr) printf("0\n");
			else printf("%d\n", size);
		}
		else if (order == "empty") {
			if (top == nullptr) printf("1\n");
			else printf("0\n");
		}
		else if (order == "top") {
			if (top == nullptr) printf("-1\n");
			else printf("%d\n", top->get());
		}
	}
	return 0;
}   
   

올라가기

최적화

스택의 구조를 잘 이해하고자 직접 구현을 해보았지만
STL에 구현된 스택보다 더 효율적으로 구현되지는 않았습니다.
따라서 특수한 자료구조를 사용하지 않는다면 STL의 스택을 사용하는 것을 추천합니다.

올라가기