자료구조 Stack 구현하기

"알고리즘 공부를 하면서 자료구조에 대해서 공부를 해야한다"란 말을 많이 듣는다. 자료구조 라이브러리는 이미 구현되어있는데, 실제 구현 방법에 대해 알고 있는 것이 좋다고 한다. 이유로는 어떻게 돌아가는지를 알기 때문에 실제 구현 시에 도움이 된다고 하는데, 조금 기분이 이상하다.

 우리는 이미 배열이란 자료구조를 애용한다.

 "배열 없이 못 살아"란 말을 할 정도로 배열 자료구조를 많이 사용한다. 조금 코딩하다보면 배열을 찾게 된다. 이처럼 다른 자료구조들도 친근해야하는 것이 중요한 게 아닐까? 친근하다의 기준이 무엇일까? 많이 이용해봤기 때문에 그 자료구조를 적재적소로 이용할 수 있다는 뜻일 것이다. -> 적재적소로 이용하기 위해선 무엇이 필요할까? 어떻게 구현되어있는지 알고 있어야 가능하다.

스택의 개념

스택은 유명한 Stack이란 게임과 같다.

아님 롤에서 나오는 나서스 스택과 같다.

여기서 문제가 생긴다. 스택은 단순히 쌓는 친구야! 맞아! 그리고 처음 쌓은 것은 마지막에 나오지! 바로 선입후출, 후입선출이야!!

그리고.. 내 고정 관념은 선입후출로 굳어졌다.

무조건 쌓는다!란 생각때문에 일단 스택에 데이터를 넣고 본다. 그러니까 스택을 쓴다는 것은 데이터를 넣고 본다. 그리고 빼내면서 사용한다. 선입선출 말 덕분에 방법이 하나로 굳어진다. 넣을 때 연산을 할 수 있지 않을까란? 생각을 해보자. 추후 이어지는 글에서 자세하게 다뤄볼 생각이다.

스택 구현 방법론

스택뿐만 아니라 자료구조를 구현할 때 여러가지 생각이 든다. 1. 내 실력이 좋지 않다. 2. 정해진 방법이 없다.이다. 코딩 시에 정해진 방법이 없으면 더 힘들어진다. 맞는 방법이 없으니까!! 물론 나도 정답을 가지고 있지 않지만, 현재 실력에서의 방법을 정해서 정리해보려고 한다.

1. 정적 배열 이용

 C++은 기억이 가물 가물하지만, 일단 시도한 바에 따르면 배열 길이의 초기화를 배열 선언시 해줘야한다.
Java는 배열을 선언하고 나중에 배열의 길이를 초기화가 가능하다.(와.. 부럽다)

컴파일 에러가 없으니 된다고 본다.

Java로 한번 짜봐야 겠다.

타입이 여러가지로 사용이 가능하니, 배열의 이름을 지어주는 것이 제일 애매하다.

C++로 짠다면 아래와 같이 작성한다.

2.  동적 배열(포인터) 이용

 비주얼 스튜디오에서 위에 올린 클래스랑 이름이 동일하다고 에러 발생!을 알려줘서 이름을 Dstack이라고 바꿨다.
코드를 보면 알겠지만, 동적 생성 부분만 다르지 거의 비슷하다.

정적과 동적의 차이

 정적은 이미 내 스택메모리에 메모리를 쌓는 행위이기 때문에 빠르다. 동적은 내 힙 메모리에 쌓기 때문에 느리다. 실제 알고리즘 문제를 풀 때에 정적을 사용할까? 동적을 사용할까? 의문이다. 
 만약에 회사 면접에 가서 알고리즘 문제를 풀 때 스택을 구현해야한다면 정적으로 구현해야할까? 동적으로 구현해야할까? 모르겠다. 아직 레벨이 부족하기 때문에 모르는 것일까? 

끝

어떤 언어로 구현하는지는 중요하지 않다. 이 자료구조를 배열처럼 익숙해지려면 직접 문제에 적용을 해봐야하니 다음 글에서 문제에서 스택을 어떠한 방식으로 이용하였는지 분석해보자!