스택(Stack)의 기본 개념

스택은 선형 자료구조의 일종으로, 데이터의 삽입과 삭제 연산이 한쪽 끝에서만 이루어지는 제한된 형태의 리스트입니다. 이러한 특성 때문에 후입선출(LIFO, Last-In-First-Out) 원칙을 따릅니다. 데이터가 드나드는 유일한 통로를 스택의 상단(Top)이라 부르며, 가장 아래쪽을 하단(Bottom)이라고 합니다.

스택 인터페이스 설계

스택의 핵심 연산을 정의하기 위해 인터페이스를 작성합니다. 기존 Object 타입 대신 제네릭(Generic)을 활용하여 타입 안정성을 높이고, 메서드의 명칭을 직관적으로 변경합니다.

public interface CustomStack<T> {
    // 현재 저장된 데이터의 개수 반환
    int count();
    
    // 스택이 비어있는지 확인
    boolean isEmpty();
    
    // 새로운 데이터 추가 (Push)
    void push(T item);
    
    // 최상단 데이터 제거 및 반환 (Pop)
    T pop();
    
    // 최상단 데이터 조회 (Peek)
    T peek();
}

배열을 활용한 순차 저장 구조 구현

순차 스택은 메모리 상에 연속된 공간을 할당하는 배열을 기반으로 구현됩니다. 배열의 끝부분을 스택의 상단(Top)으로 설정하면, 데이터의 추가 및 삭제 연산을 O(1) 시간 복잡도로 처리할 수 있습니다. 배열의 고정된 크기 한계를 극복하기 위해, 용량이 가득 찼을 때 자동으로 크기를 두 배로 확장하는 동적 할당 방식을 적용합니다.

import java.util.Arrays;
import java.util.EmptyStackException;

public class ArrayBasedStack<T> implements CustomStack<T> {
    private static final int DEFAULT_CAPACITY = 10;
    private Object[] storage;
    private int currentIndex;

    public ArrayBasedStack() {
        this.storage = new Object[DEFAULT_CAPACITY];
        this.currentIndex = -1;
    }

    @Override
    public int count() {
        return currentIndex + 1;
    }

    @Override
    public boolean isEmpty() {
        return currentIndex == -1;
    }

    @Override
    public void push(T item) {
        if (count() == storage.length) {
            resizeCapacity();
        }
        storage[++currentIndex] = item;
    }

    private void resizeCapacity() {
        int newCapacity = storage.length * 2;
        storage = Arrays.copyOf(storage, newCapacity);
    }

    @SuppressWarnings("unchecked")
    @Override
    public T pop() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        T item = (T) storage[currentIndex];
        storage[currentIndex--] = null; // 가비지 컬렉션 유도
        return item;
    }

    @SuppressWarnings("unchecked")
    @Override
    public T peek() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return (T) storage[currentIndex];
    }
}

연결 리스트를 활용한 체인 저장 구조 구현

체인 스택은 노드 단위로 메모리를 할당하는 연결 리스트를 사용합니다. 단일 연결 리스트의 머리(Head) 부분을 스택의 상단으로 활용하면, 순차 스택과 동일하게 O(1) 시간 복잡도의 삽입 및 삭제 연산을 보장합니다. 또한, 배열 기반 구현과 달리 초기 용량 설정이나 동적 확장 과정이 필요 없다는 장점이 있습니다.

import java.util.EmptyStackException;

public class LinkedListBasedStack<T> implements CustomStack<T> {
    
    private static class Node<E> {
        E data;
        Node<E> next;

        Node(E data, Node<E> next) {
            this.data = data;
            this.next = next;
        }
    }

    private Node<T> headNode;
    private int elementCount;

    public LinkedListBasedStack() {
        this.headNode = null;
        this.elementCount = 0;
    }

    @Override
    public int count() {
        return elementCount;
    }

    @Override
    public boolean isEmpty() {
        return elementCount == 0;
    }

    @Override
    public void push(T item) {
        Node<T> newNode = new Node<>(item, headNode);
        headNode = newNode;
        elementCount++;
    }

    @Override
    public T pop() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        T retrievedData = headNode.data;
        headNode = headNode.next;
        elementCount--;
        return retrievedData;
    }

    @Override
    public T peek() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return headNode.data;
    }
}