[Java | 자료구조] 스택 (Stack) 정리

PS/자료구조

[Java | 자료구조] 스택 (Stack) 정리

yaho!! 2024. 7. 24. 10:02

Stack이란?

스택(Stack)은 자료구조 중 하나로 선입후출(LIFO, Last-In-First-Out) 방식으로 데이터를 저장하고 처리한다.

스택은 선입후출 구조를 가지고 있기 때문에 가장 마지막에 들어간 데이터가 가장 먼저 나오게 된다.

스택은 데이터를 순서대로 쌓아올리는 구조로,
마치 접시를 쌓아올리는 것과 비슷한 개념이다

자바에서 스택은 자료구조로 구현하기 위한 클래스를 제공한다. 구체적으로, 자바에서는 Stack 클래스를 제공하며, 이는 java.util 패키지에 포함되어 있다. 이 Stack 클래스는 Vector 클래스를 상속받아 구현되어 있다.

스택의 특징

후입선출 (LIFO) 원칙
스택은 후입선출 원칙을 따른다. 즉, 마지막에 추가된 데이터가 가장 먼저 제거된다.
이를 통해 스택은 데이터를 쌓아올리고, 꺼낼 때는 가장 위에 쌓인 데이터부터 꺼내는 구조이다

단순한 연산

제한된 접근
스택에서는 오직 상단의 데이터만 접근할 수 있다.
즉, 데이터는 스택의 상단에서만 삽입되거나 제거될 수 있으며, 중간이나 하단의 데이터에 직접 접근할 수 없다.

스택의 장점

1. 간단한 구조: 스택의 구조가 간단하고, 연산이 직관적이다.

스택은 기본적인 연산(push, pop, peek)이 간단하여 구현이 쉽고 직관적이다.
메모리 관리와 데이터 접근 방식이 간단하다

2. 빠른 연산: push, pop, peek 연산이 모두 O(1) 시간 복잡도로 수행된다.

스택의 주요 연산(push, pop)은 O(1) 시간 복잡도로 상수 시간에 수행된다. 데이터의 추가와 제거가 매우 빠르다.

3. 유용한 응용: 함수 호출 스택, 괄호 검증, 깊이 우선 탐색(DFS) 등에서 중요한 역할을 한다.

스택은 후입선출 방식이 필요한 다양한 알고리즘과 문제에서 유용하게 사용된다.
예를 들어, 수식의 괄호 검사, 깊이 우선 탐색(DFS) 등의 문제에서 효과적이다

스택의 단점

1. 제한된 접근 : 스택은 후입선출 구조로 인해 임의의 요소에 접근할 수 없다.

스택의 맨 위에 있는 요소만 접근할 수 있으며, 중간 요소나 하단 요소에 직접 접근할 수 없다.

2. 메모리 관리 : 스택이 제한된 크기로 설정된 경우, 스택 오버플로우(Stack Overflow) 문제가 발생할 수 있다.

이 문제는 스택이 가득 차서 더 이상 데이터를 추가할 수 없을 때 발생한다.

3. 단일 방향 : 스택은 한 방향으로만 데이터 접근이 가능하다.

데이터의 추가와 제거는 스택의 상단에서만 이루어지며, 데이터의 삽입이나 삭제가 필요한 위치를 조정하기 어렵다

Stack 메서드

Stack 클래스는 java.util 패키지에 포함되어 있으며, 스택 자료구조의 기능을 제공하는 클래스를 구현하고 있다.

이 클래스는 Vector를 상속받아 스택의 주요 연산을 구현한다.

Stack 메서드 목록
push(E item)	스택의 맨 위에 요소를 추가한다.
pop()	스택의 맨 위에서 요소를 제거하고 그 값을 반환한다. 스택이 비어있으면 EmptyStackException 예외 발생한다.
peek() 또는 top()	스택의 맨 위에 있는 요소를 제거하지 않고 반환한다. 스택이 비어있으면 EmptyStackException 예외 발생한다.
isEmpty()	스택이 비어 있는지 확인한다.
search(Object o)	스택에서 주어진 객체의 위치를 검색한다. 스택의 맨 위가 1로 간주된다. 만약 객체가 스택에 없다면 -1을 반환한다.
size()	스택에 저장된 요소의 개수를 반환한다.

Stack 사용하기

import java.util.Stack;

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

        stack.push(10);
        stack.push(20);
        stack.push(30);
        
        System.out.println("Top element: " + stack.peek());

        System.out.println("Removed element: " + stack.pop());

        System.out.println("Stack after removal: " + stack);

        System.out.println("Is stack empty? " + stack.isEmpty());

        System.out.println("Position of element 10: " + stack.search(10));
    }
}

자바에서는 Deque 인터페이스를 사용하여 스택을 구현하는 것이 더 권장한다.

Deque는 스택 외에도 큐의 기능을 제공하며, ArrayDeque와 LinkedList를 사용하여 스택을 효과적으로 구현할 수 있다.

스택 구현

class Stack {
    int[] stack;
    int top;

    public Stack() {
        stack = new int[10001];
        top = -1;
    }

    public void push(int data) {
        stack[++top] = data;
    }

    public int pop() {
        if (top == -1) {
            return -1;
        }
        return stack[top--];
    }

    public int top() {
        if (empty() == 1) {
            return -1;
        }
        return stack[top];
    }

    public int size() {
        return top + 1;
    }

    public int empty() {
        return top == -1 ? 1 : 0;
    }
}