[자료구조] Stack

Stack의 개념

• 한 쪽 끝에서만 자료를 넣고 뺄 수 있는 LIFO(Last In First Out) 형식의 구조

개인적인 Think

• Stack을 이해하려면 도형으로 보는 것이 간편하고 쉽다고 생각한다. 다음 사진을 보자.
  

하노이탑이라고 하는 흔히 재귀 호출을 배울 때 빠지지 않고 나오는 예제이다. 여기서 우리는 Stack 과 비슷한 것을 느낄 수 있다.
(B 기둥과 C 기둥은 이번 포스팅에서 사용하지 않으니 빼고 생각하자.)

A 기둥에 있는 5번 블록을 빼고 싶다면 어떻게 해야 하는가?
이 의문에 대한 답은 위에 존재하는 4 ~ 1번까지의 블록들을 제거해야 한다는 것이다.

그렇다면 A 기둥에 쌓여있는 탑을 똑같이 쌓아야 할 때 가장 먼저 쌓여야 하는 부분은 무엇일까?

그것 또한 5번 블록이다. 따라서 5번 블록이 먼저 쌓였지만 가장 늦게 빠질 수 있는 것이다.

그러면 가장 먼저 제거할 수 있는 블록은 몇 번일까?
당연하게도 최 상단에 있는 블록인 1번이다.

이러한 구조를 선입 선출
즉, 먼저 쌓인 것은 먼저 나가고 나중에 쌓인 것은 마지막에 나가는 것이다.

---

JAVA 라이브러리 사용시 Stack 관련 메소드

push(E item)

• 해당 item을 Stack의 top에 삽입
• Vector의 addElement(item)과 동일

pop()

• Stack의 top에 있는 item을 삭제하고 해당 item을 반환

peek()

• Stack의 top에 있는 item을 삭제하지않고 해당 item을 반환

empty()

• Stack이 비어있으면 true를 반환 그렇지않으면 false를 반환

search(Object o)

• 해당 Object의 위치를 반환
  Stack의 top 위치는 1, 해당 Object가 없으면 -1을 반환

https://gmlwjd9405.github.io/2018/08/03/data-structure-stack.html