Java 스택(Stack) 클래스 정리

자바에는 java.util.Stack이 있지만, 자료구조 감을 잡으려면 한 번쯤 직접 구현해 보는 게 좋다. 여기서는
1) 자바 표준 Stack 간단 사용법,
2) 배열 기반 스택,
3) 연결 리스트 기반 스택,
4) 둘의 차이
까지 한 번에 정리한다.

---

1. Java의 Stack 클래스

Stack<Element> stack = new Stack<>();

주요 메서드:

public E push(E item);     // 데이터 추가 (top에 쌓기)
public E pop();            // top 요소 제거 + 반환
public E peek();           // top 요소 조회 (제거 X)
public boolean empty();    // 스택이 비었으면 true
public int search(Object o); // top 기준 1부터 시작하는 위치, 없으면 -1

간단 예제:

Stack<Integer> stack = new Stack<>();
for (int i = 0; i < 5; i++) {
    stack.push(i + 1);
    System.out.println(stack.peek());
} // 1, 2, 3, 4, 5

stack.pop();                         // 5 제거 → 1, 2, 3, 4
System.out.println(stack.peek());    // 4
System.out.println(stack.search(1)); // 4 (top=4 기준: 4→1, 3→2, 2→3, 1→4)
System.out.println(stack.empty());   // false

search()는 인덱스가 아니라 top에서 몇 번째인지(1-based)를 반환한다는 점만 주의하면 된다.

---

2. 배열로 Stack 구현하기

public class ArrayStack {

    private int top;          // 현재 top 인덱스 (비어있을 때 -1)
    private final int[] data;
    private final int capacity;

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

    public void push(int item) {
        if (isFull()) {
            throw new IllegalStateException("Stack is full");
        }
        data[++top] = item;
    }

    public int pop() {
        if (isEmpty()) {
            throw new IllegalStateException("Stack is empty");
        }
        int value = data[top];
        data[top--] = 0; // 필요 없다면 생략 가능
        return value;
    }

    public int peek() {
        if (isEmpty()) {
            throw new IllegalStateException("Stack is empty");
        }
        return data[top];
    }

    // top 기준 1부터 시작하는 위치 (Java Stack#search와 동일)
    public int search(int item) {
        for (int i = 0; i <= top; i++) {
            if (data[i] == item) {
                return (top - i) + 1;
            }
        }
        return -1;
    }

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

    public boolean isFull() {
        return top == capacity - 1;
    }

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

특징

• push 전에는 isFull(), pop/peek 전에는 isEmpty()로 경계 체크.
• search는 자바 Stack처럼 top 기준 역순 위치를 반환하도록 맞췄다.

---

3. LinkedList로 Stack 구현하기

Node 정의

public class Node {

    private final int data;
    private Node next;

    public Node(int data) {
        this.data = data;
        this.next = null;
    }

    public void linkNext(Node next) {
        this.next = next;
    }

    public int getData() {
        return data;
    }

    public Node getNext() {
        return next;
    }
}

Stack 구현

public class LinkedListStack {

    private Node top;
    private int size;

    public LinkedListStack() {
        this.top = null;
        this.size = 0;
    }

    public void push(int data) {
        Node node = new Node(data);
        node.linkNext(top);
        top = node;
        size++;
    }

    public int pop() {
        if (isEmpty()) {
            throw new IllegalStateException("Stack is empty");
        }
        int value = top.getData();
        top = top.getNext();
        size--;
        return value;
    }

    public int peek() {
        if (isEmpty()) {
            throw new IllegalStateException("Stack is empty");
        }
        return top.getData();
    }

    public int search(int item) {
        Node current = top;
        int indexFromTop = 1;

        while (current != null) {
            if (current.getData() == item) {
                return indexFromTop; // top 기준 1부터
            }
            current = current.getNext();
            indexFromTop++;
        }

        return -1;
    }

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

    public int size() {
        return size;
    }
}

동작 흐름

• push
  • 새 노드를 만들고, next를 기존 top에 연결한 뒤 top을 새 노드로 교체.
• pop
  • 현재 top의 데이터를 반환하고, top을 top.getNext()로 이동.
• search
  • top에서부터 한 노드씩 내려가며 값 비교, 찾으면 top 기준 1-based 위치 반환.

---

4. 배열 vs LinkedList, 언제 쓸까

기준	배열 기반 Stack	LinkedList 기반 Stack
최대 크기	생성 시 고정	사실상 제한 없음 (메모리 한도 내)
접근 속도	인덱스 접근, 캐시 친화적	노드 따라가야 해서 상대적으로 느림
구현 난이도	직관적, 간단	Node 정의 필요, 약간 더 복잡
삽입/삭제	top 기준 O(1)	top 기준 O(1)

• 일반적으로는 배열 기반 + 자동 확장(ArrayList/ArrayDeque 스타일)을 많이 쓰고,
  연결 리스트 기반은 “크기 가변 + 삽입/삭제 패턴이 복잡한 경우”에 더 어울린다.
• 핵심은 스택의 본질이 LIFO(Last-In, First-Out)이라는 것뿐이고,
  내부 구현은 배열이든 연결 리스트든 인터페이스만 잘 맞춰 두면 바깥 코드에서는 똑같이 쓸 수 있다는 점이다.