[JAVA/자료구조] 자바 Stack 사용법 / 스택 예시 총 정리 - 문자열 뒤집기, 괄호 짝 맞추기

▷ 스택(Stack)이란?

스택(stack)은 LIFO(라스트 인 퍼스트 아웃) 원리를 기반으로 구성된 요소들의 집합을 나타내는 추상적인 데이터 유형이다.

스택에서 수행되는 작업은 크게 세 가지로 구분이 가능하다.
요소를 스택의 맨 위에 추가하는 push, 
스택의 맨 위 요소를 제거하는 pop, 
스택의 맨 위에 있는 요소를 제거하지 않고 액세스하는 peek

 

▷ 스택(Stack)의 특징?

스택 구조는 위로 쌓아 올린 동전 혹은 접시와 같다. 

• LIFO(Last-In First-out)

> 스택에 마지막으로 추가된 요소가 가장 먼저 제거 (가장 나중에 쌓은 접시가 먼저 제거 됨)

• 스택의 한쪽 끝에서만 액세스 가능

> 일반적으로 스택의 'top'이라고 하는 한쪽 끝에서만 추가 및 제거된다.

• 일정한 시간 복잡성

> push/pop/peek 작업은 스택 요소의 수와 관계없이 O(1)의 일정한 시간으로 수행 가능

• 제한된 액세스

> 스택의 맨 위에 있는 요소만 액세스할 수 있다. 더 깊은 곳에 있는 요소에 액세스하려면 위의 요소를 제거해야 함!

• 동적 크기

> 스택은 필요에 따라 확장하거나 축소할 수 있다. (기본 배열 또는 연결리스트를 사용하여 구현)

 

그 외에도, 

-호출되었지만 아직 완료되지 않은 함수나

-메서드를 추적하는 데이터 구조인 호출 스택을 관리하기 위해 프로그래밍 언어와 컴파일러에서 일반적으로 사용되고

-깊이 우선 검색 및 역추적과 같은 알고리즘에도 사용된다.

 

▷ 자바에서 스택(Stack) 을 어떻게 쓰나?

import java.util.Stack; <- 먼저 호출은 필수!

기초적인 실습을 통해 스택 구조를 익혀보자.

public class MyStack<T> {
    private Stack<T> stack = new Stack<>();

    public void push(T element) {
        stack.push(element);
    }

    public T pop() {
        return stack.pop();
    }

    public T peek() {
        return stack.peek();
    }

    public boolean isEmpty() {
        return stack.isEmpty();
    }

    public int size() {
        return stack.size();
    }
}

보면 알 수 있듯이 자바 Stack 클래스는 스택의 기능을 기본적으로 제공한다.

 

다음은 자바에서 Stack 클래스를 활용한 예시다.

 

1) 자바 Stack을 활용해 문자열(String) 뒤집기 

import java.util.Stack;

public class StringReverser {
    public static void main(String[] args) {
        String input = "hello world";
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < input.length(); i++) {
            stack.push(input.charAt(i));
        }
        StringBuilder reversed = new StringBuilder();
        while (!stack.isEmpty()) {
            reversed.append(stack.pop());
        }
        System.out.println(reversed.toString()); // "dlrow olleh"
    }
}

 

 

2) 자바 Stack을 활용해 괄호 짝 맞는지 확인하기

import java.util.Stack;

public class ParenthesesChecker {
    public static void main(String[] args) {
        String input = "((()))";
        boolean isBalanced = isParenthesesBalanced(input);
        System.out.println(isBalanced); // true
    }

    public static boolean isParenthesesBalanced(String input) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < input.length(); i++) {
            char c = input.charAt(i);
            if (c == '(') {
                stack.push(c);
            } else if (c == ')') {
                if (stack.isEmpty() || stack.pop() != '(') {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}

 

---

 

 

지금까지 스택 자료 구조를 자바에서 어떻게 구현하는 지 예시를 통해 알아봤다.

자바의 Stack 클래스를 이용하니 구현이 복잡하지는 않은 편이고,

구조에 대한 이해가 있으면 구현에도 어려움이 없을 것으로 보인다.