Stack

데이터를 후입선출(LIFO, Last In First Out) 순서로 삽입·삭제하는 선형 자료구조입니다.

핵심 개념

항목내용
원리가장 나중에 들어온 데이터가 가장 먼저 나감
삽입push — 스택의 맨 위(top)에 추가
삭제pop — 스택의 맨 위(top)에서 제거
조회peek — 맨 위 원소를 제거하지 않고 확인
시간 복잡도push, pop, peek 모두 O(1)
 
push(1) → push(2) → push(3)

  │ 3 │ ← top (가장 나중에 삽입)
  │ 2 │
  │ 1 │ ← bottom (가장 먼저 삽입)
  └───┘

pop() → 3 반환 (가장 나중에 들어온 것이 먼저 나감)

  │ 2 │ ← top
  │ 1 │
  └───┘

주요 연산

연산설명시간 복잡도
push(item)top에 원소 삽입O(1)
pop()top 원소 제거 후 반환O(1)
peek() / top()top 원소 확인 (제거 안 함)O(1)
isEmpty()스택이 비었는지 확인O(1)
size()원소 개수 반환O(1)

Java 구현

1. Java 내장 클래스

// Stack 클래스 (레거시, Vector 기반 — 동기화 오버헤드)
Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
stack.push(3);
stack.pop();       // 3
stack.peek();      // 2
stack.isEmpty();   // false
stack.size();      // 2

// Deque 사용 권장 (Java 공식 문서 권장 방식)
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);
stack.push(2);
stack.push(3);
stack.pop();       // 3
stack.peek();      // 2
클래스특징권장 여부
Stack<E>Vector 기반, 동기화됨X 레거시
ArrayDeque<E>배열 기반, 동기화 없음, 빠름O 권장
LinkedList<E>연결 리스트 기반, Deque 구현△ 가능하지만 ArrayDeque가 더 빠름

2. 배열 기반 직접 구현

public class ArrayStack<E> {
    private Object[] arr;
    private int top;
    private int capacity;

    public ArrayStack(int capacity) {
        this.capacity = capacity;
        this.arr = new Object[capacity];
        this.top = -1;
    }

    public void push(E item) {
        if (top == capacity - 1) throw new StackOverflowError();
        arr[++top] = item;
    }

    @SuppressWarnings("unchecked")
    public E pop() {
        if (top == -1) throw new EmptyStackException();
        E item = (E) arr[top];
        arr[top--] = null;
        return item;
    }

    @SuppressWarnings("unchecked")
    public E peek() {
        if (top == -1) throw new EmptyStackException();
        return (E) arr[top];
    }

    public boolean isEmpty() { return top == -1; }
    public int size() { return top + 1; }
}

3. 연결 리스트 기반 직접 구현

public class LinkedStack<E> {
    private static class Node<E> {
        E data;
        Node<E> next;
        Node(E data, Node<E> next) {
            this.data = data;
            this.next = next;
        }
    }

    private Node<E> top;
    private int size;

    public void push(E item) {
        top = new Node<>(item, top);
        size++;
    }

    public E pop() {
        if (top == null) throw new EmptyStackException();
        E item = top.data;
        top = top.next;
        size--;
        return item;
    }

    public E peek() {
        if (top == null) throw new EmptyStackException();
        return top.data;
    }

    public boolean isEmpty() { return top == null; }
    public int size() { return size; }
}

배열 기반 vs 연결 리스트 기반

항목배열 기반연결 리스트 기반
메모리연속 메모리, 크기 고정 (또는 동적 확장)비연속 메모리, 크기 제한 없음
캐시 효율높음 (메모리 연속)낮음 (노드가 흩어짐)
push/popO(1) (amortized, 동적 확장 시)O(1)
오버헤드미사용 공간 낭비 가능노드마다 포인터 추가 메모리

스택의 활용 사례

활용설명
함수 호출 스택 (Call Stack)함수 호출·복귀 주소를 LIFO로 관리
괄호 검사(, {, [ 열린 괄호를 push, 닫힌 괄호와 매칭
후위 표기식 계산피연산자를 push, 연산자 만나면 pop하여 계산
DFS (깊이 우선 탐색)방문할 노드를 스택에 저장
Undo/Redo작업 이력을 스택으로 관리
브라우저 뒤로 가기방문 기록을 스택에 저장
JVM 스택 프레임메서드 호출마다 스택 프레임 push/pop

함수 호출 스택 예시

public static void main(String[] args) {  // ① main 프레임 push
    a();                                    // ② a 프레임 push
}
static void a() {
    b();                                    // ③ b 프레임 push
}
static void b() {
    System.out.println("hello");            // ④ println 프레임 push
}                                           // ⑤ println → b → a → main 순서로 pop

호출 스택 변화:

① │ main │    ② │  a   │    ③ │  b   │    ④ │println│
   └──────┘      │ main │      │  a   │      │  b   │
                  └──────┘      │ main │      │  a   │
                                └──────┘      │ main │
                                              └──────┘
→ 복귀: println pop → b pop → a pop → main pop

괄호 검사 예시

public static boolean isValid(String s) {
    Deque<Character> stack = new ArrayDeque<>();

    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 != '(') return false;
            if (c == '}' && top != '{') return false;
            if (c == ']' && top != '[') return false;
        }
    }
    return stack.isEmpty();
}

isValid("({[]})");  // true
isValid("({[}])");  // false

"({[]})" 검사 과정:

(  → push(   │ ( │
{  → push{   │ { │
              │ ( │
[  → push[   │ [ │
              │ { │
              │ ( │
]  → pop[ O  │ { │
              │ ( │
}  → pop{ O  │ ( │
)  → pop( O  └───┘ 비었으므로 O valid

스택 vs Queue

항목스택 (Stack)큐 (Queue)
원리LIFO (후입선출)FIFO (선입선출)
삽입push (top에)enqueue (rear에)
삭제pop (top에서)dequeue (front에서)
비유접시 쌓기줄 서기
활용함수 호출, DFS, UndoBFS, 작업 큐, 버퍼
 
[스택 — LIFO]          [큐 — FIFO]
  │ 3 │ ← pop           front → │ 1 │ 2 │ 3 │ ← rear
  │ 2 │                          dequeue        enqueue
  │ 1 │
  └───┘

CSLOG에서 보기