04. 스택

Jerry·2025년 7월 16일

data structure

C언어로 쉽게 풀어쓴 자료구조

목록 보기

3/12

4.1 스택이란?

정의

후입선출(Last-In, First-Out; LIFO) 방식으로 데이터를 저장하고 꺼내는 자료구조

연산

객체: 0개 이상의 원소를 가지는 유한 선형 리스트
연산:
  create(size) ::= 최대 크기가 size인 공백 스택을 생성한다.
  is_full(s) ::=
    if(스택의 원소 수 == size) return TRUE;
    else return FALSE;
  is_empty(s) ::=
    if(스택의 원소 수 == 0) return TRUE;
    else return FALSE;
  push(s, item) ::=
    if( is_full(s) ) return ERROR_STACKFULL;
    else 스택의 맨 위에 item을 추가한다.
  pop(s) ::=
    if( is_empty(s) ) return ERROR_STACKEMPTY;
    else 스택의 맨 위의 원소를 제거해서 반환한다.
  peek(s) ::=
    if( is_empty(s) ) return ERROR_STACKEMPTY;
    else 스택의 맨 위의 원소를 제거하지 않고 반환한다.

4.2 스택의 구현

배열 기반

public class ArrayStack<T> {
    private T[] data;
    private int top;         // 스택의 맨 위 인덱스 (0-based)
    private int maxSize;     // 현재 배열의 최대 크기

    // create(size): 최대 크기가 size인 공백 스택 생성
    public ArrayStack(int size) {
        this.data = new T[size];
        this.maxSize = size;
        this.top = -1;  // 공백 스택
    }

    // is_full: 스택이 가득 찼는지
    public boolean is_full() {
        return (top + 1) == maxSize;
    }

    // is_empty: 스택이 비었는지
    public boolean is_empty() {
        return top == -1;
    }

    // peek: 스택이 비어 있으면 예외, 아니면 맨 위 원소를 제거하지 않고 반환
    @SuppressWarnings("unchecked")
    public T peek() {
        if (is_empty()) {
            throw new NoSuchElementException("스택이 비었습니다!");
        }
        return (T) data[top];
    }

    // push(item): (스택이 가득 차면 2배로 확장 후) item 추가
    public int push(T item) {
        if (is_full()) {
            // 크기 2배로 확장
            int newSize = maxSize * 2;
            T[] newData = new T[newSize];
            System.arraycopy(data, 0, newData, 0, maxSize);
            data = newData;
            maxSize = newSize;
        }
        data[++top] = item;
        return 0; // 정상 종료 (0 반환)
    }

    // pop: 스택이 비어 있으면 예외, 아니면 맨 위 원소 제거·반환
    @SuppressWarnings("unchecked")
    public T pop() {
        if (is_empty()) {
            throw new NoSuchElementException("스택이 비었습니다!");
        }
        return (T) data[top--];
    }

	// 현재 스택에 들어 있는 원소 개수
    public int size() {
        return top + 1;
    }
}

public class Main {
    public static void main(String[] args) {
        ArrayStack<Integer> s = new ArrayStack<>(2);

        System.out.println(s.push(10)); // 0
        System.out.println(s.push(20)); // 0
        System.out.println(s.push(30)); // 크기 2→4로 확장, 0
        System.out.println(s.peek()); // 30
        System.out.println(s.pop()); // 30
        System.out.println(s.pop()); // 20
        System.out.println(s.pop()); // 10
        System.out.println(s.pop()); // NoSuchElementException("스택이 비었습니다!")
    }
}

java.util.List 기반

import java.util.*;

public class ListStack {
    public static void main(String[] args) {
	    // create(): 공백 스택 생성 (크기 무관)
        List<Object> stack = new ArrayList<>();

        // is_full: 없음 (자동 확장)

        // is_empty
        System.out.println(stack.isEmpty()); // true
        
        // push 연산 (맨 뒤에 추가)
        stack.add("A");
        stack.add("B");
        stack.add("C");

        // peek 연산 (맨 위 값 보기: 마지막 요소)
        System.out.println(stack.get(stack.size() - 1)); // C

        // pop 연산 (맨 위 값 제거 및 반환)
        System.out.println(stack.remove(stack.size() - 1)); // C
        System.out.println(stack.remove(stack.size() - 1)); // B
        System.out.println(stack.remove(stack.size() - 1)); // A

        // size 연산 (스택에 들어 있는 원소 개수)
        System.out.println(stack.size()); // 0

        // 비어 있을 때 pop 또는 peek: 예외 발생
        try {
            System.out.println(stack.remove(stack.size() - 1));
        } catch (IndexOutOfBoundsException e) {
            System.out.println("IndexOutOfBoundsException: 스택이 비었습니다!");
        }
        try {
            System.out.println(stack.get(stack.size() - 1));
        } catch (IndexOutOfBoundsException e) {
            System.out.println("IndexOutOfBoundsException: 스택이 비었습니다!");
        }
    }
}

java.util.Stack 기반

import java.util.*;

public class StackStack {
    public static void main(String[] args) {
        // create(): 공백 스택 생성 (크기 무관)
        Stack<Object> stack = new Stack<>();

        // is_full: 없음 (Stack은 내부적으로 Vector 기반, 자동 확장)
        
        // is_empty
        System.out.println(stack.isEmpty()); // true

        // push 연산 (맨 위에 추가)
        stack.push("A");
        stack.push("B");
        stack.push("C");

        // peek 연산 (맨 위 값 보기)
        System.out.println(stack.peek()); // C

        // pop 연산 (맨 위 값 제거 및 반환)
        System.out.println(stack.pop()); // C
        System.out.println(stack.pop()); // B
        System.out.println(stack.pop()); // A

        // size 연산 (스택에 들어 있는 원소 개수)
        System.out.println(stack.size()); // 0

        // 비어 있을 때 pop 또는 peek: 예외 발생
        try {
            System.out.println(stack.pop());
        } catch (EmptyStackException e) {
            System.out.println("EmptyStackException: 스택이 비었습니다!");
        }
        try {
            System.out.println(stack.peek());
        } catch (EmptyStackException e) {
            System.out.println("EmptyStackException: 스택이 비었습니다!");
        }
    }
}

java.util.Deque 기반

import java.util.*;

public class DequeStack {
    public static void main(String[] args) {
        // create(): 공백 스택 생성 (크기 무관)
        Deque<Object> stack = new ArrayDeque<>();

        // is_full: 없음 (Deque는 내부적으로 자동 확장)

        // is_empty
        System.out.println(stack.isEmpty()); // true

        // push 연산 (맨 위에 추가)
        stack.push("A");
        stack.push("B");
        stack.push("C");

        // peek 연산 (맨 위 값 보기)
        System.out.println(stack.peek()); // C

        // pop 연산 (맨 위 값 제거 및 반환)
        System.out.println(stack.pop()); // C
        System.out.println(stack.pop()); // B
        System.out.println(stack.pop()); // A

        // size 연산 (스택에 들어 있는 원소 개수)
        System.out.println(stack.size()); // 0

        // 비어 있을 때 pop 또는 peek: 예외 발생
        try {
            System.out.println(stack.pop());
        } catch (NoSuchElementException e) {
            System.out.println("NoSuchElementException: 스택이 비었습니다!");
        }
        try {
            System.out.println(stack.peek());
        } catch (NoSuchElementException e) {
            System.out.println("NoSuchElementException: 스택이 비었습니다!");
        }
    }
}