[자료구조] 스택 with Java

안녕하세요, Jude 입니다.
 
(이 글을 읽기전 노드에 관한 글을 읽고오시면, 이해에 도움이 되실겁니다. https://survive20.tistory.com/15)

[자료구조기초1] Node(노드)란 무엇인가? with Java

 
오늘은 "스택(Stack)" 에 대해 이야기 해볼까 합니다. 스택은 지난번 소개해드린 노드들의 연결관계 중 하나입니다.
 
어디서 많이 들어본 단어가 아닐까싶습니다. 이글을 읽고 계신분들은 "리그오브레전드(LOL)" (이하. 롤) 이라는 게임을 아시나요?
 
롤에는 "나서스(Nasus)"라는 캐릭터가 있습니다. 이 캐릭터의 "흡수의 일격"이라는 스킬이 있습니다.

좌 : 나서스의 모습 / 우 : 흡수의 일격

설명을 읽어보면, "적을 처치하면 영구적으로 피해량이 3만큼 증가한다"고 하는데, 유저들은 이를 흔히 스택을 쌓는다 라고합니다.
 
현직 개발자 이시거나, 예비개발자 분들은 이력서 작성하실때, 혹은 공고확인하실때 "기술스택"이라는 말로도 흔히 들어보신 말 일거라고 생각합니다.
 
위 두 사례모두, 추상적이거나 산술적이긴해도, 하나의 오브젝트가 쌓여서 모이는 경우인데요.
 
우리가 오늘 알아볼 자료구조 또한 이러한 특성이 반영되어 스택이라는 이름이 붙게 되었습니다.
 
본격적으로 스택에 대해 알아 보겠습니다.
 
스택의 가장 큰 특징은, 바로
 

LIFO(Last In, First Out), 마지막에 입력된 원소가, 먼저 반환된다.

이렇게 글로만 설명되면 이해가 어려우 실 것 같아, 익숙하실거같은 시각 자료를 준비 해봤습니다.

하노이탑 (Tower of Hanoi)

초중고등학교 시절, 혹은 프로그래밍을 처음 공부하시면서, 만나 보셨을 하노이탑, 이 친구의 각 탑은 자료구조 스택과 똑같은 구조를 가지고 있습니다. 가장 맨위의 링만 조작할 수 있다는것이죠. 스택 데이터에 접근할때 가장 마지막원소(Top)부터 접근 하게 됩니다. (하지만 저장된 데이터 값의 크기는 상관이없다는 점에서 차이가 있습니다!)
 
한번 Java 코드로 스택을 만나보겠습니다.

Stack

먼저 스택은 null 로 초기화되어있는 top이라는 노드 하나로 구성되어있습니다. 그리고 pop 과 push 메서드를 지원합니다.
pop 메서드는 해당 stack의 최상단 노드를 반환하는 메서드이고, push는 해당 스택에, 새로운 데이터노드를 추가하는 메서드입니다.

Stack 의 시각화 자료(next가 위의 원소로 착각하는 분들이 많습니다)

각 메서드의 동작 원리를 알려드리기위한 시각 자료입니다.

push 메서드 :
push 의 매게변수로 스택에 쌓아줄 특정한 데이터 item을 전달 해줍니다. 이 item 으로 새로운 노드 객체(nthNode)를 생성하고, nthNode가 선언되기 이전의 top을 nthNode 의 next 로 지정을 해주고, nthNode가 추가됨으로써, 최상단 노드가 되었으니, Stack의 top에 nthNode를 저장해줍니다.

pop 메서드 :
최상단 노드를 리턴하며, 스택에서 제거하는 메서드 입니다. 만약 top 이 null 값이면 반환 및 제거할 값이 없으니EmptyStackExceptionError를 반환하고, 값이 있다면, 탑의 데이터를 반환합니다. 반환하면서 참조해제를 해주면 자바의 가비지콜렉터가 알아서 제거를 해주게됩니다. 참조를 해제를 해 주려면, top.next 가 top 이 되어야한다는 사실은 시각화자료를 살펴보시면 금방 이해하실 수 있을 겁니다.

Stack 의 모든원소에 접근하기 !

show 메서드

해당스택의 모든 원소를 출력하며 제거하는 메서드 입니다. 해당 스택의 모든 원소(노드)에 접근 하기위하기에는, 각 참조 관계를 활용해야 하는데요. Stack에서 접근 할 수 있는 것은 top 노드 밖에 없기 때문에, top 노드 부터 접근을합니다. 탑의 데이터를 리턴하고 새로운 top은, top.next 가 되며 하나씩 확인 하며 출력 하는 것 입니다. 그리고 마지막 원소에서는 top 의 참조가 없을 것 이기때문에 top == null 이면 실행을 중지하도록 만들었습니다.

 
사실 자바에서는 Stack 클래스가 정의되어 있어서, 별도의 코드작성없이 사용가능하지만, 그 구조를 이해하기위해 같이 스택에 대해 알아봤습니다. 스택의 특징인 최상단 노드에서만 접근이 가능하다는점, Stack의 next는 다음이 아닌 이전 노드를 가르킨다는 것!만 기억하시면 좋을 것 같습니다.