자바 공부#2_04. Stack

 

Stack?

Stack은 한쪽 끝에서만 데이터를 추가하거나 삭제할 수 있는 자료구조이다. 후입선출(Last-In-First-Out, LIFO)의 구조를 가진다. 가장 마지막에 추가된 요소가 가장 먼저 제거된다.

Java에서는 Stack을 구현하기 위해 java.util.Stack 클래스를 사용할 수 있다. 하지만 Stack 클래스는 오래된 Vector 기반이기 때문에, 최근에는 성능이 더 좋은 Deque 계열의 ArrayDeque 또는 LinkedList로 대체하는 경우가 많다.

 

1. Stack의 주요 메서드

• push(E item) : 데이터를 스택에 추가한다.
• pop() : 가장 마지막에 들어간 데이터를 제거하고 반환한다.
• peek() : 데이터를 제거하지 않고, 가장 위에 있는 데이터를 반환한다.
• empty() : 스택이 비어있는지 여부를 확인한다.
• search(Object o) : 해당 객체가 스택에서 몇 번째에 있는지 반환한다 (1부터 시작). 못 찾으면 -1 반환.

Stack 사용 예시

• 괄호의 유효성 검사
• 웹 브라우저의 뒤로가기 기능
• 재귀적 연산 (ex. DFS)
• 수식 계산기 (후위표기법 등)

Stack의 시간복잡도

push()	O(1)
pop()	O(1)
peek()	O(1)
search()	O(n)

 

 

2. Stack vs ArrayDeque vs LinkedList

	내부 구조	동기화	성능	특징
Stack	Vector 기반	O	느림	동기화 지원. 오래된 방식
ArrayDeque	배열 기반	X	빠름	가장 많이 사용됨. Null 불가
LinkedList	연결 리스트	X	느림	요소 간 삽입/삭제에 유리

 

사용 시 주의할 점

• Stack 클래스는 동기화를 지원하기 때문에 멀티스레드 환경에서는 유용할 수 있으나, 단일 스레드 환경에서는 오히려 성능 저하 요인이 될 수 있다.
• ArrayDeque는 스택/큐 양방향 모두 지원하며 null 값을 허용하지 않는다.
• LinkedList는 스택으로도 사용할 수 있지만 메모리 사용량이 많고 성능이 좋지 않을 수 있다.

필요에 따라 Stack의 구현체는 목적에 맞게 선택하는 것이 중요하다. 단순한 스택 구조가 필요하다면 ArrayDeque를 사용하는 것이 일반적이다.