[자료구조] 스택(Stack) Java 예제 포함

스택(Stack)은 컴퓨터 과학에서 매우 중요한 자료 구조 중 하나로, 데이터를 저장하고 접근하는 방법에 대한 규칙을 따릅니다. 스택은 LIFO(Last In, First Out)라는 원칙을 기반으로 동작합니다. 이는 마지막에 들어간 데이터가 먼저 나오는 구조로, 물리적인 구조로는 책을 쌓는 것과 비슷합니다.

 

 

 

스택의 주요 특징

1. LIFO (Last In, First Out):
   • 스택에 저장된 데이터는 나중에 추가된 데이터가 먼저 처리됩니다.
   • 즉, 스택의 마지막에 추가된 요소가 가장 먼저 제거됩니다.
2. 기본 연산:
   • Push: 스택의 맨 위에 새로운 데이터를 추가하는 연산입니다.
   • Pop: 스택의 맨 위에 있는 데이터를 제거하고 반환하는 연산입니다.
   • Peek (또는 Top): 스택의 맨 위에 있는 데이터를 제거하지 않고 반환합니다.
   • isEmpty: 스택이 비어 있는지 여부를 확인하는 연산입니다.
   • Size: 스택에 쌓여 있는 데이터의 개수를 반환합니다.

스택의 활용 예시

1. 함수 호출 스택:
   • 컴퓨터 프로그램에서 함수를 호출할 때, 호출된 함수의 정보는 스택에 저장됩니다. 이 스택을 "호출 스택"이라고 하며, 함수를 종료할 때는 스택에서 해당 함수의 정보를 꺼내어 처리합니다.
2. 괄호 유효성 검사:
   • 프로그래밍에서 수식의 괄호의 유효성을 검사할 때 스택이 자주 사용됩니다. 여는 괄호를 스택에 넣고, 닫는 괄호가 나올 때마다 스택에서 비교하는 방식으로 유효성을 검사합니다.
3. 탐색 알고리즘:
   • 깊이 우선 탐색(DFS)과 같은 알고리즘에서는 스택을 이용해 탐색할 노드를 관리합니다.
4. 브라우저 뒤로 가기 기능:
   • 브라우저에서 뒤로 가기 기능은 이전 페이지로 돌아갈 때 스택을 이용하여 사용자가 방문한 페이지를 관리합니다.

스택 예시: 프링글스 통

프링글스 통을 예로 들면, 가장 위에 있는 과자가 가장 나중에 들어왔고, 이 과자를 꺼내면 그 아래에 있는 과자 역시 차례로 꺼낼 수 있습니다. 통의 가장 밑에 있는 과자는 가장 먼저 들어간 과자지만, 마지막에 먹게 됩니다. 이처럼 스택은 나중에 넣은 데이터가 먼저 나오는 구조입니다.

 

 

 

Java에서 스택 선언 및 사용

Java에서는 스택을 쉽게 사용할 수 있도록 java.util.Stack 클래스를 제공합니다. 이를 통해 스택의 기본적인 연산을 할 수 있습니다.

1. 스택 선언

스택을 사용하려면 Stack 클래스를 인스턴스화하여 선언할 수 있습니다.

import java.util.Stack;

public class StackExample {
    public static void main(String[] args) {
        // Integer 타입의 스택 선언
        Stack<Integer> stack = new Stack<>();
        
        // String 타입의 스택 선언
        Stack<String> stringStack = new Stack<>();
    }
}

 

2. 스택 사용

push, pop, peek 등 스택의 기본적인 연산을 사용하는 예시입니다.

import java.util.Stack;

public class StackExample {
    public static void main(String[] args) {
        // 정수형 스택 선언
        Stack<Integer> stack = new Stack<>();
        
        // 요소 추가 (Push)
        stack.push(10); // 스택: [10]
        stack.push(20); // 스택: [10, 20]
        stack.push(30); // 스택: [10, 20, 30]

        // 스택의 맨 위 요소 확인 (Peek)
        System.out.println("Top element: " + stack.peek()); // 출력: 30

        // 요소 제거 (Pop)
        System.out.println("Popped element: " + stack.pop()); // 출력: 30
        System.out.println("Popped element: " + stack.pop()); // 출력: 20

        // 스택의 현재 상태 출력
        System.out.println("Stack after pops: " + stack); // 출력: [10]

        // 스택이 비었는지 확인
        System.out.println("Is stack empty? " + stack.isEmpty()); // 출력: false

        // 요소 제거 후 상태 확인
        stack.pop(); // 스택: []
        System.out.println("Is stack empty after pop? " + stack.isEmpty()); // 출력: true
    }
}

 

3. 응용 예시: 괄호 유효성 검사

스택을 활용하여 괄호의 유효성을 검사하는 예시입니다.

import java.util.Stack;

public class BracketChecker {
    public static boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '{' || c == '[') {
                stack.push(c);
            } else {
                if (stack.isEmpty()) return false;
                char top = stack.pop();
                if ((c == ')' && top != '(') || 
                    (c == '}' && top != '{') || 
                    (c == ']' && top != '[')) {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }

    public static void main(String[] args) {
        String expression = "{[()]}";
        System.out.println("Is the expression valid? " + isValid(expression)); // 출력: true
    }
}

 

 

이렇게 스택을 활용하면 데이터를 효율적으로 관리하고, 여러 상황에 맞는 알고리즘을 구현할 수 있습니다.