Java) Stack이란? (간단 설명, 사용법, 예시)

https://hobbyatelier.tistory.com/97

Java) List란? (ArrayList, LinkedList, Vector 설명, 사용법, 예시)

 

저번 글에서 List 클래스들의 구현체들에 대해 썼을 때, 

Stack에 대해서 잠시나마 썼었다.

Stack 대신에 Dequq(덱)이란 구현체를 쓰는 것을 추천했는데, 이는 잘못된 상속 설계로 인한 문제때문이다.

그럼에도 불구하고 Stack은 여러 코딩 테스트 문제에서 자주 다뤄지기에 Stack에 대해 써보려고 한다.

 

                List (인터페이스)               Stack의 상속 관계
                  ↑
   +--------------+--------------+
   |              |              |
ArrayList    LinkedList       Vector
                                |
                             Stack           - 스택은 Vector를 상속 받아 설계되었다.

 

---

 Stack(스택)이란?

 

자바의 Stack 클래스는 LIFO(Last-In-First-Out, 후입선출) 구조를 따르는 컬렉션 클래스이다.

즉, 가장 나중에 넣은 요소가 가장 먼저 나온다. 

예시로 택배 상하차를 생각하면 되는데, 트럭에 상자를 차곡차곡 쌓아 놓고 배달지에 도착하면 쌓아 놓은 상자를 위에서부터 내려놓는 이미지를 기억해 두면 편하다.

 

Java에서는 java.util.Stack 클래스로 제공되며, Vector 클래스를 상속받아 구현되어 있다.

1. 기본 구조

Stack<Type> stack = new Stack<>();

 

예시 :

Stack<Integer> stack = new Stack<>();  // Integer 스택

 

 

2. 주요 메서드

 

메서드	설명
push(E item)	스택의 top에 요소를 추가
pop()	스택의 top 요소를 제거하고 반환
peek()	스택의 top 요소를 제거하지 않고 반환
empty()	스택이 비어있는지 확인
search(Object o)	요소가 top으로부터 몇 번째인지 반환 (1부터 시작), 없으면 -1

 

---

3. 간단한 예제

import java.util.Stack;

public class StackExample {
    public static void main(String[] args) {
        Stack<String> stack = new Stack<>();

        stack.push("Alpha");
        stack.push("Bravo");
        stack.push("Charlie");

        System.out.println("Top element: " + stack.peek()); // Charlie
        System.out.println("Popped: " + stack.pop());       // Charlie
        System.out.println("Top now: " + stack.peek());     // Bravo
        System.out.println("Is empty? " + stack.empty());   // false
    }
}

 

 

---

3-1. 주의사항

• Stack은 Vector를 상속받기 때문에 스레드-세이프(Thread-safe) 하지만, 요즘은 더 나은 대안으로 Deque 인터페이스(예: ArrayDeque)를 사용한다.
• 예: Deque<Integer> stack = new ArrayDeque<>();

---

5. Stack의 시간 복잡도

 

연산시간	복잡도	설명
push()	O(1)	요소를 top에 추가
pop()	O(1)	top 요소를 제거하고 반환
peek()	O(1)	top 요소를 반환 (제거 X)
search()	O(n)	특정 요소 탐색 (top부터 순차 검색)

• 대부분의 기본 연산은 상수 시간 O(1) 으로 매우 빠름
• 단, search()는 내부에서 순차 탐색을 하므로 최악의 경우 O(n)

---

6. 공간 복잡도

• O(n)
  n개의 요소를 저장할 수 있는 스택이라면, 요소를 담기 위해 선형적인 공간이 필요함.
  (스택의 크기와 동일하게 메모리를 사용)

---

7. 스택이 사용되는 대표적인 상황들

7-1. 재귀 호출 시 호출 스택

• 자바를 포함한 대부분의 언어에서 함수 호출은 스택에 쌓임
• 깊은 재귀 함수에서 StackOverflowError 가 발생할 수도 있음

7-2. 괄호 유효성 검사

()[]{} 가 제대로 열리고 닫혔는지 확인하는 문제


LeetCode 20번 문제가 대표적인 예시다

 

https://hobbyatelier.tistory.com/93

 

[자바] LeetCode 20. Valid Parentheses

 

 

7-3. 중위 → 후위 표기법 변환 / 계산기 구현

• 연산자 우선순위를 관리할 때 스택 사용

7-4. DFS (깊이 우선 탐색)

• 재귀적으로 구현되지만, 명시적으로 스택으로 구현 가능

7-5. 되돌리기(Undo), 브라우저 뒤로 가기

• 사용자 동작을 스택에 저장하고, pop 하며 이전 상태로 되돌리는 구조

7-6. 문자열 뒤집기

• 한 문자씩 push 후 pop 하면 역순으로 출력됨

---

8. 정리 요약

 

항목	내용
시간 복잡도	대부분 O(1), 검색은 O(n)
공간 복잡도	O(n)
사용 사례	재귀, 괄호 검사, DFS, 되돌리기, 수식 계산 등
대체 자료구조	Deque (ArrayDeque) – 더 빠르고 유연함