C++을 이용한 간단한 스택 예제

안녕하세요. 저는 c++을 공부하고있는 대학생입니다.
제가 공부하고 있는 것 중, stack에 관하여 간단한게 정리하고자 하여 작석하게 되었습니다.
우선. 스택이란? LIFO (Last In First Out) 형식으로 된 자료구조로, 쌓는 형식으로 구현이 되며, 마지막에 들어온 원소가 제일 먼저 나가게 되는 자료구조 입니다.

그림을 보시면, Empty 부분에 Input data가 들어올 수 있으며, Output data는 가장 위에있는(마지막에 들어온) data가 출력하는 형식입니다.

스택을 구현 할 수 있는 방법은 여러가지 있지만, 배열을 이용한 방법과, vector를 이용한 방법, stack 라이브러리를 이용한 방법으로 예시를 들어 설명 드리겠습니다.

문제를 보면서 설명 해 드리겠습니다. 저는 스택문제 중 가장 쉬운 codeup 1402를 통해 코드를 작성하였습니다.

codeup 1402번

입력.
첫째 줄에 데이터의 개수 n이 입력된다. (n <= 1,000)
둘째 줄에 공백을 기준으로 n개의 데이터가 입력된다.

출력.
n개의 데이터를 입력의 역순으로 출력한다.

입력 예시.
5
1 3 5 6 8

출력 예시.
8 6 5 3 1

[풀이 1.]
먼저 배열로 이 문제를 풀어보도록 하겠습니다.

#include <iostream>

int main(){
  int stackarr[1000] = {0, }; //stack의 대상이 될 배열
  int insertData = 0;  // 데이터 개수 입력
  int inputData = 0;  // stackarr에 들어갈 데이터
  
  for(int i = 0; i<insertData; i++) {
		std::cin>>inputData;
  		stackarr[i] = inputData;
  }
  
  for(int i = insertData -1; i>= 0; i--) {
  		std::cout<<stackarr[i]<<" ";
  }
  return 0;
}

배열로 접근하였을때, stackarr라는 배열을 1000개의 원소를 가질 수 있게 만들었습니다. 이유는, 문제의 조건에 데이터 n 의 개수가 1000이하 라는 조건을 만족시키기 위해서입니다.

insertData는 입력할 데이터 개수를 뜻하며, inputData는 stackarr에 들어갈 값을 뜻합니다.

출력 시 , 가장 마지막 배열을 가리키기 위하여, int i = insertData -1 로 선언하여 후위연산자를 통하여 하나씩 감소하여 0번째 배열까지 모두 출력 할 수 있게 만들었습니다.

[풀이 2.]

다음은 vector로 구현 해 보기전에, vector란 무엇인지 간단히 정리 해 보았습니다.

vector는 컨테이너 중 하나로, 시퀀스 컨테이너(sequence container) 입니다. 시퀀스 컨테이너란? 데이터를 선형으로 저장하여, 순서대로 요소를 저장하는 특성을 가지고 있습니다.
대표적인 시퀀스 컨테이너 종류로는 vector, deque , list 정도가 있습니다.
vector의 큰 특징은, 요소의 추가 삭제시, 메모리를 재 할당하는 동적으로 변경하는 특징을 갖고있습니다.

그럼 이제, vector로 문제를 풀어보도록 하겠습니다.

#include <iostream>
#include <vector>

class stackVector{
	public:
		std::vector<int> stackvector;  //stack 역할을 할 vector
		int inputData;  // vector 안에 넣을 값
		
		int stackpush(int num);  // stack input
		int stackOut(int num);  // stack output
};

int stackVector::stackpush(int num){
	for(int i =0; i<num; i++){
		std::cin>>inputData;
		stackvector.push_back(inputData);
	}
}

int stackVector::stackOut(int num){
	for(int i = num-1; i>=0; i--) {
		std::cout<<stackvector[i]<<" ";
	}
  	stackvector.clear();  // 메모리에 할당 된 것을 반환하기 위한 clear
}

int main(){
	
	int insertData = 0;
	stackVector stack;
	
	std::cin>>insertData;  // data 입력 수
	
	stack.stackpush(insertData);
	stack.stackOut(insertData);
	
}

vector 를 이용해서 템플릿 인수를 int로 하여, 객체이름을 stackvector로 선언하였습니다. vector는 앞서 말씀드린 것 처럼 시퀀스 컨테이너기 때문에, 순서대로 요소가 들어가는 것 을 이용하여 스택처럼 구현 해 보았습니다.
class를 따로 선언해서 그 안에 stack의 기본동작인 입력과 출력을 구현하였고, main 함수에서 인자를 받아 값을 넣을 수 있게 만들었습니다.

[풀이 3.]

다음은 stack 라이브러리를 이용해서 구현 해 보도록 하겠습니다. STL을 공부 하신분이라면 익숙한 라이브러리입니다. 정말 간단하고 구현도 쉽습니다. 바로 풀어보도록 하겠습니다.

#include <iostream>
#include <stack>

int main(){
	std::stack<int> stack;
	int insertData = 0;
	int inputData = 0;
	
	std::cin>>insertData;
	
	for(int i =0; i<insertData; i++){
		std::cin>>inputData;
		stack.push(inputData);
	}
	
	for(int i = 0; i<insertData; i++){
		std::cout<<stack.top()<<" ";
		stack.pop();
	}
}

stack 라이브러리를 사용하면 이렇게 간단하게 구현이 가능합니다. 설명을 드리자면, stack에 대한 템플릿 인수 와 이름을 정하여 할당 해 주고, insertData 와 inputData를 이용해서 앞서 풀었던 풀이 1과 풀이 2처럼 입력 할 데이터 수를 넣어준 다음, for 반복문을 통하여 stack에 inputData를 stack push 한 다음, 출력 할 때, top() 을 이용하여 가장 위에있는 원소를 출력 한 후, pop으로 메모리 반환을 해 줌으로써, 앞에 있는 풀이처럼 구현이 가능하게 됩니다.

[공부 한 후 느낀점]

스택에 대한 기본문제인 만큼 난이도는 쉬운편이지만, 스택에 대한 동작 원리를 공부하기 위해 여러가지 방법으로 풀어보았습니다. for문을 사용하는것이 아닌, 사용자 정의함수를 만들어 재귀형식으로 돌리는 방법도 있고, while문을 통하여 EOF에 해당되는 지점을 만들어서 break 하는 방법도 있고 여러가지 더 다양하게 풀 수 있을 것 같습니다. 가장 중요한 것은, 시간복잡도와 공간복잡도를 고려하여 최적의 코드를 짜는것을 중점으로하여 연습해야 할 것 같습니다.
풀이 1 에서 했던 arr방법은 공간복잡도에 있어서 낭비라고 생각이 듭니다. 이유는, 처음에 1000개로 공간을 할당 해 주었기때문에, 제 얕은 지식으로 말씀드리자면. heap영역 (cpu가 관여하지 않는 메모리 영역) 에 arr가 할당되는데 arr가 차지하는 1000개의 공간만큼 할당되는것이라, 만약에 5개의 공간만 사용한다면 995개의 공간은 잉여 공간이 되므로 불 필요한 공간을 만든 것 이기때문에 공간복잡도 면에 있어, 좋지 않다고 생각합니다.
풀이 2 에서는 제가 class를 사용하였는데, 복잡한 문제도 아니였고, 다중상속을 한 것도 아니기때문에 시간복잡도에 있어서 큰 차이는 없을거라 생각이 됩니다. 또한 vector를 사용하였고, 메모리도 끝에서 반환을 해 주었기때문에 공간복잡도에 있어서 괜찮다고 생각이 됩니다. 다만 너무 class를 많이쓰거나, 다중상속을 하는것은 시간복잡도 면에 있어 좋지 않다고 생각합니다.
풀이 3 에서는 정말 간단하게 stack을 사용한 것 같습니다. 만약에 코딩테스트 나 다른 업무를 볼 때, STL 사용에 제약이 없다면 stack을 쓰는게 가장 좋을 것 같다고 생각이 들 만큼 좋은 것 같습니다.