스택

스택

Stack(스택)은 LIFO(Last In, First Out) 구조를 가지는 자료구조로, 나중에 삽입된 요소가 먼저 제거되는 방식입니다. 즉, 한쪽 끝에서만 데이터를 삽입하고 제거할 수 있습니다.

 

1.Java에서 Stack 사용법

Java에서는 java.util.Stack 클래스를 제공하여 스택을 쉽게 사용할 수 있습니다.

import java.util.Stack;

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

        // 요소 추가 (push)
        stack.push(10);
        stack.push(20);
        stack.push(30);

        System.out.println("Stack: " + stack);  // 출력: Stack: [10, 20, 30]

        // 요소 제거 (pop) - 가장 최근에 추가된 요소 제거
        int popped = stack.pop();
        System.out.println("Popped element: " + popped);  // 출력: Popped element: 30
        System.out.println("Stack after pop: " + stack);  // 출력: Stack after pop: [10, 20]

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

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

        // 요소 검색 (search) - 해당 요소의 1-based index 반환 (위에서부터)
        System.out.println("Position of 10: " + stack.search(10));  // 출력: Position of 10: 2
    }
}

 

2. 주요 메서드 정리

메서드	설명
push(E item)	스택의 맨 위에 요소를 추가
pop()	스택의 맨 위 요소를 제거하고 반환
peek()	스택의 맨 위 요소를 반환 (제거하지 않음)
empty()	스택이 비어있는지 확인 (true 또는  false 반환)
search(object o)	해당 요소의 위치 반환 (위에서부터 1-based index)

 

3.Stack의 내부 동작 방식

Stack 클래스는 내부적으로 Vector 클래스를 상속받아 구현되어 있습니다. 따라서 동기화(syschronization)기능을 제공하지만, 멀티스레드 환경에서는 Deque인터페이스를 사용하는 것이 더 권장됩니다.

 

대체할 수 있는 자료구조

ArrayDeque(빠르고 가벼운 스택 구현)

LinkedList(양방향 연결 리스트로 구현된 스택 가능)

 

4.Stack을 활용한 예제

(1) 괄호 유효성 검사

import java.util.Stack;

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

    public static void main(String[] args) {
        System.out.println(isValid("({[]})"));  // true
        System.out.println(isValid("({[})"));   // false
    }
}

 

(2) 재귀 없이 DFS(깊이 우선 탐색) 구현

import java.util.*;

class Graph {
    private Map<Integer, List<Integer>> adjList = new HashMap<>();

    public void addEdge(int v, int w) {
        adjList.putIfAbsent(v, new ArrayList<>());
        adjList.get(v).add(w);
    }

    public void dfs(int start) {
        Stack<Integer> stack = new Stack<>();
        Set<Integer> visited = new HashSet<>();
        
        stack.push(start);

        while (!stack.isEmpty()) {
            int node = stack.pop();
            if (!visited.contains(node)) {
                visited.add(node);
                System.out.print(node + " ");
                
                for (int neighbor : adjList.getOrDefault(node, new ArrayList<>())) {
                    stack.push(neighbor);
                }
            }
        }
    }
}

public class DFSExample {
    public static void main(String[] args) {
        Graph g = new Graph();
        g.addEdge(1, 2);
        g.addEdge(1, 3);
        g.addEdge(2, 4);
        g.addEdge(2, 5);
        g.addEdge(3, 6);
        g.addEdge(3, 7);

        System.out.print("DFS Traversal: ");
        g.dfs(1);  // 출력: DFS Traversal: 1 3 7 6 2 5 4
    }
}

 

 

5. Stack과 Queue의 차이점

특징	Stack (스택)	Queue (큐)
구조	LIFO (Last In, First Out)	FIFO (First In, First Out)
삽입/삭제 위치	한쪽 끝에서만 가능	앞에서 삭제, 뒤에서 삽입
주요 메서드	push(), pop(), peek()	offer(), poll(), peek()
구현 클래스	Stack (Vector 상속)	Queue, LinkedList, ArrayDeque

 

6. Stack 사용이 적합한 경우

✅ 함수 호출 스택 (재귀 호출 추적)
✅ 괄호 유효성 검사 ({[()]} 같은 괄호 검사)
✅ Undo / Redo 기능 (이전 상태 저장)
✅ DFS (깊이 우선 탐색) 구현
✅ 후위 표기법 계산기 (계산식 변환 및 연산)