자료구조 - 스택(Stack)

1. 스택(Stack)이란 무엇인가?

스택(Stack)이란 사전적 의미는 '무더기', '쌓다'라는 뜻이다.

가장 중요한 핵심은 'LIFO (Last-In, First-Out) 후입 선출' 이다.

 

예를 들면, 프링글스 통이나 막혀있는 골목길과 같다.

1. 입구와 출구는 하나뿐이다. (위쪽 구멍)
2. 가장 먼저 넣은 감자칩(맨 아래)을 먹으려면, 그 위에 쌓인 감자칩을 다 꺼내 먹어야한다.
3. 중간에 있는 감자칩(데이터)을 쏙 뺄 수 없다. 무조건 맨 위(Top)에서만 꺼낼 수 있다.

---

2. 스택의 3대 동작 (용어 정리)

스택을 다룰 때 사용하는 명령어는 전 세계 공통으로 딱 3가지만 기억하면 된다.

1. Push (밀어 넣기): 데이터를 맨 위에 쌓는다.
2. Pop (터뜨리기/꺼내기): 맨 위에 있는 데이터를 꺼내면서 삭제한다.
3. Peek (살짝 보기): 맨 위에 뭐가 있는지 확인만 한다. (데이터를 꺼내는 것이 아님)

---

3. 왜 스택을 배울까? (컴퓨터의 생각 방식)

단순히 데이터를 쌓는 거라면 배열(Array)을 쓰면 되는데, 왜 굳이 '중간 데이터를 못 꺼내는' 불편한 스택을 쓸까?

 

그 이유는 컴퓨터의 뇌 구조가 스택 기반으로 되어 있기 때문이다. 우리가 Java 개발을 하면서 자주 보는 에러 메시지에 그 힌트가 있다.

 

예시: 함수 호출 (Call Stack)

 

1. main() 실행 → 스택에 push
2. A() 호출 → main 위에 A를 push (main은 잠시 대기)
3. B() 호출 → A 위에 B를 push (A도 잠시 대기)
4. B() 작업 끝(return) → B가 pop (사라짐) -> 이제 A가 다시 일할 차례
5. A() 작업 끝(return) → A가 pop -> 이제 main이 다시 일할 차례

그래서 에러가 나면 함수 호출이 쌓인 기록을 보여주는 데, 그게 바로 스택 트레이스(Stack Trace)라고 한다.

---

[참고] 스택(Stack)을 구현할 때 int[]가 아니라 Object[] (객체 배열) 였다면?

package step02;

public class MyArrayStack {
    private int[] stack;
    private int top; // 스택의 가장 위(마지막 데이터)를 가리키는 인덱스

    public MyArrayStack(int size) {
        this.stack = new int[size];
        this.top = -1; // 초기엔 비어있음
    }

    // 1. push: 데이터를 넣는다.
    public void push(int value) {
        stack[++top] = value;
    }

    // 2. pop: 데이터를 뺀다.
    public int pop() {
        int value = stack[top];
        top--;

        return value; // 임시 반환값
    }

    // 테스트용 메인 함수
    public static void main(String[] args) {
        MyArrayStack s = new MyArrayStack(5);
        s.push(10);
        s.push(20);
        s.push(30);

        System.out.println(s.pop()); // 30 출력 되어야 함
        System.out.println(s.pop()); // 20 출력 되어야 함
        System.out.println(s.pop()); // 10 출력 되어야 함
    }
}

 

스택의 원리를 구현한 소스코드다.

여기서 pop 코드는 top-- 만 하고 끝난다. 만약, 이게 객체였다면, top이 내려갔어도 배열의 그 위치에는 여전히 객체의 주소값이 남아있게 된다.

 

Java의 가비지 컬렉터(GC)는 "어? 배열이 아직 저 객체를 잡고 있네?" 라고 판단해서 회수를 안한다. 이것을 'Loitering Objects(배회하는 객체)'라고 부른다.

 

객체 스택일 때는 stack[top--] = null; 처럼 참조를 끊어주는 것이 완벽한 구현 방법이다.