[자료구조] 자바 Stack 후입선출(LIFO) 클래스 가이드

Stack이란?

Java에서 Stack은 후입선출(LIFO, Last In First Out) 방식으로 요소를 관리하는 자료구조입니다.

새로운 요소가 추가될 때마다 스택의 가장 상단에 쌓이며, 데이터를 꺼낼 때는 가장 최근에 추가된 요소부터 제거됩니다.

Stack의 사전적 정의
'쌓다', '쌓이다'로 물건을 쌓아 올리는 것처럼 데이터를 순서대로 쌓는 자료구조입니다.

• Stack의 주요 특징
  • 후입선출(LIFO) : Stack은 가장 최근에 추가된 요소가 가장 먼저 제거됩니다.
  • Vector 기반 구현 : Java의 Vector 클래스를 상속받아 구현되었으며, 모든 기능을 활용할 수 있습니다.
  • 동기화 지원 : Vector를 상속받았기 때문에 기본적으로 동기화되어 있으며, 멀티스레드 환경에서도 안전하게 사용할 수 있습니다.
  • 단방향 입출력 구조 : 데이터의 들어오는 방향과 나가는 방향이 같습니다.
• Stack의 연산
  • push(object o) : 객체 o를 스택의 가장 상단에 추가합니다.
  • pop() : 스택에서 가장 상단에 있는 항목을 제거합니다.
  • peek() : 스택에 가장 상단에 있는 항목을 반환합니다.
  • isEmpty() : 스택이 비어 있을 경우에 true를 반환합니다.
  • search(Object o) : 스택의 상단부터 탐색하여 지정된 객체가 있는 요소의 위치를 반환하며, 없을 경우 -1을 반환합니다.
  • size() : 현재 스택에 있는 요소의 개수를 반환합니다.
  • clear() : 스택의 모든 요소들을 제거합니다.

Stack 클래스의 장단점

• 장점
  • 간단한 사용법 : LIFO 구조로 데이터를 관리하기 위한 간단한 인터페이스를 제공합니다.
  • 동기화 지원 : Vector를 기반으로 하기 때문에 멀티스레드 환경에서 안전하게 사용할 수 있습니다.
  • 기본 메서드 제공 : 데이터를 추가, 제거, 조회할 수 있는 기본적인 간단한 연산 메서드를 제공하여 사용할 수 있습니다.
• 단점
  • 낮은 성능 : Vector를 상속받아 구현했기 때문에, 동기화로 인한 성능 저하가 있을 수 있습니다.
  • 구식 클래스 : Java 초창기에 도입한 클래스로, 이후 등장한 ArrayDeque 인터페이스와 같은 대안이 더 자주 사용됩니다.
  • 제한된 용도 : Stack은 LIFO 구조로만 동작하기 때문에, 다양한 자료구조의 요구 사항을 충족하지 못할 수 있습니다.

사용 사례

Stack은 다음과 같은 상황에서 주로 사용됩니다.

• 재귀 알고리즘(dfs 알고리즘)
• 웹 브라우저 방문기록 관리
• 실행 취소 기능 구현
• 역순 문자열 생성
• 수식의 괄호 유효성 검사
• 후위 표기법 계산

Stack 사용 방법

Stack 선언하기

Java에서 Stack을 사용하려면 'import java.util.Stack;'을 import 해야 합니다.

Stack의 선언은 Stack<T> 변수명 = new Stack<>(); 형태로 선언할 수 있으며, 데이터 타입은 클래스 또는 래퍼 클래스로 선언합니다.

import java.util.Stack;

class StackExample {
    public static void main(String[] args) {
        Stack<Integer> stack_int = new Stack<>();
        Stack<Double> stack_double = new Stack<>();
        
        Stack<Student> stack_student = new Stack<>();
    }
}

Stack 요소 추가하기(push, add)

Stack의 가장 상단에 요소를 추가하기 위해서는 push() 또는 add() 메서드를 사용해야 합니다.

• push()
  • Stack 자료구조의 동작 방식(LIFO)을 명시적으로 나타냅니다.
  • 스택에서 값을 추가할 때 의도를 명확하게  표현합니다.
• add()
  • Vector 클래스에서 상속된 메서드로 단순히 요소를 리스트의 끝에 추가하는 동작을 합니다.
  • 스택의 의도를 흐리게 하고, 단순 리스트처럼 보일 수 있습니다.

❗️Stack 사용 시 push()를 권장합니다.
명확한 LIFO 구조를 표현하기 위해 add() 대신에 push()를 사용하는 것이 좋습니다.

Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);

stack.add(3);

System.out.println(stack); // [1, 2, 3]

Stack 요소 꺼내기(pop, remove)

Stack에서 가장 최상단에 있는 요소를 제거하기 위해서는 pop() 또는 remove()라는 메서드를 사용하면 됩니다.

• pop()
  • Stack의 가장 최상단의 요소를 제거하고 반환합니다.
  • LIFO 구조를 따르는 스택의 핵심 동작을 표현합니다.
  • 스택이 공백일 경우 "EmptyStackException"이 발생합니다.
• remove()
  • 특정 인덱스나 값을 기반으로 요소를 제거합니다.
  • LIFO와 무관하며 리스트 동작처럼 보일 수 있습니다.
  • 옳지 않은 인덱스 입력 시 "ArrayIndexOutOfBoundsException"이 발생합니다.

❗️Stack 사용 시 pop()을 권장합니다.
스택의 일관성과 LIFO 원칙을 유지하려면 remove() 대신에 pop()을 사용하는 것을 권장합니다.

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

stack.pop(); // 3
System.out.println(stack); // [1, 2]

stack.pop(); // 2
stack.pop(); // 1
System.out.println(stack); // []

Stack 최상단 요소 확인하기(peek)

Stack의 가장 최상단의 값을 꺼내지 않고 출력을 하고 싶다면 peek() 메서드를 사용해서 출력할 수 있습니다.

❗️스택이 비어있을 경우에 peek() 메서드 호출 시 NoSuchElementException 예외가 발생할 수 있으므로 주의해야 합니다.

Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
stack.push(3);

System.out.println(stack.peek()); // 3
System.out.println(stack); // [1, 2, 3]

Stack 비어있는지 확인하기(isEmpty)

Stack이 현재 비어있는지 확인하기 위해서는 isEmpty() 메서드를 사용합니다. Stack이 비어있다면 true, 그렇지 않다면 false를 반환합니다.

Stack<Integer> stack = new Stack<>();
stack.push(1);

if(!stack.isEmpty() {
    stack.pop();
}

Stack 요소 탐색하기(search)

스택 상단부터 탐색하여 해당 요소의 인덱스를 반환하며, 해당 요소가 여러 개일 경우 마지막 위치를 반환합니다.

만약에 찾는 요소가 스택에 없을 경우 -1을 반환하게 됩니다.

Stack<String> stack = new Stack<>();
stack.push("Hello");
stack.push("Backend");
stack.push("World");

System.out.println(stack); // [Hello, Backend, World]

System.out.println(stack.search("Hello")); // 0
System.out.println(stack.search("Backend")); // 1
System.out.println(stack.search("World")); // 2

Stack 사이즈 확인하기(size)

현재 스택에 저장된 요소의 개수를 반환합니다.

Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
stack.push(3);

System.out.println(stack.size()); // 3

Stack 비우기(clear)

스택의 모든 요소를 제거합니다.

Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
stack.push(3);

System.out.println(stack); // [1, 2, 3]
stack.clear();

System.out.println(stack.size()); // 0
System.out.println(stack); // []

Stack 대신 ArrayDeque 사용하기

Java Stack 클래스는 동기화를 지원하지만, 성능 저하가 있을 수 있습니다.

이러한 단점을 보완하기 위해 Java에서는 ArrayDeque라는 대안을 제공합니다.

• Stack : 동기화를 지원하지만 성능이 상대적으로 저하될 수 있습니다.
• ArrayDeque : 동기화는 지원하지 않지만, 더 높은 성능을 제공하며, LIFO 구조를 구현하는 데 적합합니다.

특징	Stack	ArrayDeque
동기화	지원	지원하지 않음
성능	동기화로 인해 성능 저하 가능	더 높은 성능 제공
LIFO 제공	지원	지원

import java.util.ArrayDeque;
import java.util.Deque;

public class ArrayDequeExample {
    public static void main(String[] args) {
        // ArrayDeque 생성
        Deque<Integer> stack = new ArrayDeque<>();
        
        // 요소 추가
        stack.push(10);
        stack.push(20);
        stack.push(30);
        
        // 요소 제거 및 출력
        while (!stack.isEmpty()) {
            System.out.println(stack.pop());
        }
    }
}

결론

Java Stack 클래스는 LIFO 구조를 구현하기 위한 간단하고 직관적인 방법을 제공합니다.

Stack은 동기화를 지원하기 때문에 멀티스레드 환경에서 안전하게 사용할 수 있지만, 성능 저하의 가능성이 있으며,

현재 Java 애플리케이션에서는 ArrayDeque와 같은 대안이 더 자주 사용됩니다.

LIFO 구조를 구현해야 하는 상황에서 Stack과 ArrayDeque 중 적절한 자료구조를 선택하는 것이 중요합니다.