[Java] 자료구조 Stack에 관하여

1. Stack

Stack이라는 단어는 더미 혹은 쌓다 라는 의미의 단어로, 단어의 뜻 그대로 데이터를 쌓아 올린 형태의 자료구조이다.

가장 마지막에 들어온 자료가 가장 먼저 빠져나가는 선형구조이며, 후입선출(Last In First Out, 나중에 들어간 값이 먼저 나온다) 자료구조를 구현한 자바 클래스이다.

List Collection의 Vector를 상속 받은 Stack 메모리 구조의 클래스를 제공한다.

배열 기반 데이터 구조로 인덱스로 요소에 액세스 할 수 있다.

 

2. 특징

• 먼저 들어간 데이터가 나중에 빠져나가는 Last In First Out
• 인터럽트 처리, 수식의 계산, 서브 루틴의 복귀 번지 저장 등에 쓰인다.
• 그래프의 깊이 우선 탐색(DFS) 알고리즘에 사용된다.
• 재귀적(Recursion) 함수를 호출할 때 사용한다.

 

3. 시간복잡도

• 삽입(push) - 맨 위 데이터를 넣으면 되기 때문에 O(1) 이다.
• 삭제(pop) - 맨 위 데이터를 삭제하면 되기 때문에 O(1)이다.
• 읽기(peek) - 맨 위 데이터를 읽으면 되기 때문에 O(1)이다.
• 탐색(search) - 맨 위 데이터부터 하나씩 찾아야 하기 때문에 O(N)이다.

 

4. Method

• empty() - Stack이 비어 있는지 여부에 대한 boolean 값 반환
• push() - Stack에 데이터를 삽입하고, 삽입한 데이터 반환
• pop() - Stack의 최상위 데이터를 삭제하고, 삭제한 데이터 반환
• peek() - Stack의 최상위 데이터 반환
• search() - 파라미터로 들어온 데이터의 인덱스 반환

 

5. 단점

• Stack 클래스는 synchronized 키워드가 붙어 있기 때문에 Thread-safe 하다는 특징을 가지고 있다. 즉, 멀티스레드 환경이 아닐 경우에 사용을 하게 되면 lock을 거는 작업 때문에 많은 오버헤드가 발생하게 된다.
• Stack 클래스는 Vector 클래스를 잘못 확장한 자바의 큰 실수이다. 왜냐하면 Stack은 LIFO 구조를 이용해야 하기 때문에 Vector 클래스를 확장하면 중간에서 데이터를 삽입, 삭제할 수 있게 된다.

import java.util.Stack;

public class Test {
	public static void main(String[] args) {
		Stack<Integer> stack = new Stack<>();
		stack.push(1);
		stack.push(2);
		stack.push(3);
		
		System.out.println(stack.get(0));	// 해당 인덱스로 원소 찾기
		System.out.println(stack.set(1, 4));	// 해당 인덱스로 원소 넣기
		System.out.println(stack.remove(2));	// 해당 인덱스로 원소 삭제
		
		System.out.println(stack.toString());
	}
}

Stack은 LIFO 구조로 한쪽 방향에서만 삽입, 삭제가 일어나야 하는데 중간에서 삽입, 삭제를 할 수 있다는 큰 문제가 발생한다. 이는 Stack, Vector가 JDK 1.0부터 존재하다 보니 자바에서 잘못 설계한 경우라고 한다.

그리고 마지막으로 큰 단점은 아니지만 Stack은 초기 용량을 설정할 수 있는 생성자가 없다보니 데이터의 삽입을 많이 하게 되면 배열을 복사해야 하는 일이 빈번하게 발생할 수 있다는 단점도 존재한다.

 

6. Stack 클래스 대신 ArrayDeque

ArrayDeque 공식문서를 보면 Stack구조로 사용하면 Stack 클래스보다 빠르고 Queue 구조로 사용하면 Queue 클래스보다 빠르다고 한다(ArrayDeque는 Thread-Safe 하지 않기 때문).

따라서 LIFO 구조를 만들기 위해 적합한 클래스는 Deque 인터페이스를 구현한 ArrayDeque 클래스이다.

Stack과 Deque의 차이점까지 다루기에는 내용이 길어지므로 추후에 다시 다루기로 하겠다.

 

 

🙏 참조 ::

• https://youngjinmo.github.io/2021/05/java-stack/
• https://devlog-wjdrbs96.tistory.com/244