[Java] 스택(Stack)

스택(Stack)이란?

스택은 가장 마지막에 들어간 것이

가장 처음 나오는 구조이다.

이를 LIFO(Last-In-First-Out)라고 한다.

 

사용하는 대표 사례는

수식의 괄호 쌍이나 전위/중위/후위 표기법, DFS, Flood Fill, undo/redo를 구현하는데 사용된다.

 

Java에서 스택을 사용하기 위해서
import java.util.stack 코드를 추가해줘야 한다.

 

Java의 스택에서 제공하는 주요 함수는 다음과 같다.

Method
push(item)	스택의 가장 위에 item을 추가하고, 추가된 요소를 반환한다.
pop()	스택의 가장 위에 있는 요소를 삭제하면서, 가장 위 요소를 반환한다.
peek()	스택의 가장 위에 있는 요소를 삭제하지 않고, 가장 위 요소를 반환한다.
empty()	스택이 비었는지 확인하고, 비어있으면 true를 반환하고 요소가 하나라도 있으면 false를 반환한다.
search(Object o)	주어진 객체(o)를 찾아서 그 위치를 반환하며, 못 찾을 경우 -1을 반환한다. 배열과 달리 위치는 0이 아닌 1부터 시작한다. 반환값이 1이면 가장 먼저 pop되는 요소이다.

 

pop()과 peek()에서 주의할 점은

스택이 비어있는 상태에서 호출하면 EmptyStackException이 발생한다.

따라서, if(!stack.isEmpty())을 한 후에 

pop()과 peek()을 실행하는 것이 좋다.

 

Java에서 Stack은 Vector 클래스를 상속하고 있다.

따라서, 동적 공간이며 생성할 때 사이즈를 명시하지 않아도 된다.

처음 Stack을 만들면 10개의 공간을 할당하고

공간이 부족하게 되면 공간을 2배로 늘린다.

 

Java의 Stack은 초기 모델로,

Vector클래스를 잘못 상속하고 있다.

따라서, Stack에서는 사용될 수 없는 함수이자

Vector에서만 사용할 수 있는 몇몇 함수들이 사용가능하다.

예를 들어, Stack은 인덱스를 통해 자료에 접근할 수 없다.

하지만 Java의 Stack은 인덱스를 통하여 접근할 수 있다.

 

Vector 클래스를 잘못 상속하여 생긴 함수는 다음과 같다.

add(), remove(), contains(), firstElement(), indexOf(), get()

 

그래서 자바의 공식 문서에서는

Stack이 아닌 Deque클래스를 사용할 것을 권장하고 있다.

Deque는 양방향에서 출입이 가능한 자료구조이기 때문에

Stack으로 사용할 수도 있고, Que로도 사용할 수 있는 자료구조이다.

---

스택(Stack) 구현

배열 또는 연결리스트를 이용해서 구현할 수 있고,

배열을 이용하는게 구현이 더 쉽다.

스택을 구현하기 위해서는

원소를 담을 큰 배열 1개, 인덱스를 저장할 변수 1개가 필요하다.

pos(cursor)는 다음 원소가 추가될 위치를 가르키고 있고,

pos의 값이 stack 내의 원소 수를 의미한다.

 

[push]
pos가 가리키는 위치에 x를 추가하고,

pos++ > arr[pos++]=x;

[pop]
pos--;만 하면 된다.

pos 위치의 값을 굳이 없앨 필요는 없다.

어차피 다음 push가 들어오면 덮여서 없어지기 때문이다.

[peek]

단순히 가장 위의 값을 반환하면 된다.

return arr[pos-1];

 

---

참고자료

자바 공식 문서 : Stack (Java SE 17 & JDK 17)

https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/Stack.html