[자료구조] 스택(Stack)

자료구조와 알고리즘/자료구조

[자료구조] 스택(Stack)

프린이8549 2024. 10. 2. 19:46

프로그래밍에서 Stack은 두 가지 의미를 가지고 있다:

프로그램 실행 시 사용되는 메모리 영역
- 프로그램 실행 중 함수 호출이나 변수 저장을 위해 사용되는 메모리 스택 영역.
자료구조로서의 스택
- 후입선출(Last-In, First-Out) 방식으로 데이터를 관리하는 자료구조.

본 글에서는 두 번째 의미인 자료구조로서의 스택에 대해 다루고자 한다.

1. Stack의 정의

1.1. 스택의 정의

스택은 배열이나 연결 리스트를 사용해서 구현할 수 있는 선형 자료구조로,

삽입과 삭제가 한쪽 끝(top)에서만 이루어진 후입선출(Last-in First-out; LIFO)의 자료구조를 의미한다.

즉, 마지막에 삽입된 데이터가 가장 먼저 삭제되는 형태이다.

1.2. 관련 용어

위치

top : 삽입과 삭제가 일어나는 위치(또는 top pointer)

주요 연산

push : 입력 연산. top 위치에 새로운 데이터 삽입
pop : 출력 연산. top 위치에 현 데이터를 삭제하고 확인
peek : 조회 연산. 탑 포인터가 가리키는 데이터를 조회할 뿐, top의 인덱스를 변화시키지는 않음(단순 확인)
empty : 스택이 비어 있는지 확인
size : 스택의 크기 확인

2. Stack의 구현

스택은 배열 또는 연결 리스트를 이용하여 쉽게 구현할 수 있다.

배열을 사용하는 경우 크기가 고정되며, 크기를 초과하는 데이터를 삽입하면 오버플로우가 발생할 수 있다(하단 참고).

반면, 연결 리스트를 사용하면 크기 제한이 없지만 메모리 사용량이 더 많아질 수 있다.

배열을 이용해서 구현한다면,

스택을 위한 배열을 생성한다.
초기 index(top)값을 0으로 잡는다.
push 시 배열에 요소를 삽입하고 index값을 하나 올린다.
pop 시 index 값을 하나 없애고 감소된 인덱스에 있는 요소를 반환한다(동시에 배열에서는 삭제).
peek 시 (index - 1) 에 위치한 값을 조회한다.
empty 여부는 index == 0 을 통해 알 수 있다.

위 내용을 자바로 구현한 내용은 아래와 같다.(백준 28278번 문항).

import java.io.*;

public class Main {
    /*
    BOJ NO.28278 : 스택
    */
    static int[] stack;  // 스택을 저장할 배열
    static int top;  // 스택의 현재 위치(크기)

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 명령의 수 N 입력 받기
        int N = Integer.parseInt(br.readLine());
        stack = new int[N];  // 명령의 수에 맞는 스택 크기

        top = 0;  // 스택의 초기 크기 0

        StringBuilder sb = new StringBuilder();

        while (N-- > 0) {
            String[] input = br.readLine().split(" ");
            int num = Integer.parseInt(input[0]);

            switch (num) {
                case 1: // 정수 X를 스택에 넣는다
                    int X = Integer.parseInt(input[1]);
                    push(X);
                    break;
                case 2: // 스택에서 맨 위의 정수를 빼고 출력한다. 없다면 -1 출력
                    sb.append(pop()).append("\n");
                    break;
                case 3: // 스택에 들어있는 정수의 개수를 출력
                    sb.append(size()).append("\n");
                    break;
                case 4: // 스택이 비어있으면 1, 아니면 0을 출력
                    sb.append(empty() ? 1 : 0).append("\n");
                    break;
                case 5: // 스택의 맨 위 정수를 출력. 없다면 -1 출력
                    sb.append(peek()).append("\n");
                    break;
            }
        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }

    // 정수 X를 스택에 넣는 메소드
    public static void push(int item) {
        stack[top++] = item;
    }

    // 스택의 맨 위 정수를 꺼내는 메소드 (꺼낸 후 해당 자리를 0으로 초기화)
    public static int pop() {
        if (empty()) {
            return -1;
        }
        int item = stack[--top];  // idx 감소 후 값을 가져옴
        stack[top] = 0;  // 해당 자리를 0으로 초기화
        return item;
    }

    // 스택의 크기 반환
    public static int size() {
        return top;
    }

    // 스택이 비어있는지 여부 확인
    public static boolean empty() {
        return top == 0;
    }

    // 스택의 맨 위 정수를 반환(꺼내지 않고)
    public static int peek() {
        if (empty()) {
            return -1;
        }
        return stack[top - 1];
    }
}