[자료구조] 스택(stack)과 자바를 통한 구현(배열, ArrayList)

스택 

스택(stack)은 먼저 넣은 데이터가 나중에 나오는 자료구조이다. 데이터를 넣는 작업은 푸시(push) , 꺼내는 작업은 팝(pop) 이라고 한다.

 

스택에서 데이터를 관리할 때, 가장 최근에 추가된 데이터를 먼저 꺼내는 구조를 따른다. 데이터를 삽입하거나 삭제할 수 있는 위치는 한쪽 끝인 top 이다. 스택의 맨 아래쪽은 bottom 이라고 하며, 여기에 직접 접근할 수는 없다.

 

예를 들어, 접시를 쌓는 과정과 유사하다. 접시를 추가할 때는 위에서 쌓고, 꺼낼 때도 맨 위에서부터 꺼낸다. 이처럼 스택은 제한된 입출력 방식으로 후입선출(LIFO: Last In, First Out)의 성질을 갖는다.

스택의 장단점

장점

• 구조가 단순해서 구현이 쉽다.
• 데이터 저장/읽기 속도가 빠르다.

 

단점(배열 기반)

• 데이터 최대 개수를 미리 정해야 한다.
• 저장 공간 낭비 발생할 수 있다. (미리 최대 개수만큼 저장 공간 확보해야 함)

 

 

스택 구현하기 

스택을 구현하는 주요 방법은 다음 세 가지가 있다

1. 배열(Array)
   • 정적인 크기를 가지며, 스택의 크기를 미리 지정해야 한다.
   • 데이터가 계속 추가될 경우, 크기를 초과하면 오버플로우(Overflow) 가 발생할 수 있다.
   • 빠른 접근 속도를 제공하지만, 크기 제한이 단점이다.
2. ArrayList
   • 동적 배열로, 데이터가 추가되면 자동으로 크기를 조정한다.
   • 배열 기반이라 인덱스를 통한 빠른 접근이 가능하다.
   • 메모리 재할당이 필요한 경우 성능 저하가 발생할 수 있다.
3. LinkedList
   • 노드 기반 자료구조로, 삽입과 삭제가 빠르게 이루어진다.
   • 데이터가 추가될 때마다 메모리를 동적으로 할당하므로 크기 제한이 없다.
   • 노드 구조를 사용하기 때문에 메모리 사용량이 많고, 접근 속도가 상대적으로 느리다.

이 세 가지 방법 중 배열은 단순하고 효율적이지만 크기 제한이 단점이다.
ArrayList와 LinkedList는 동적 크기를 지원하며, 각각 빠른 접근 또는 빠른 삽입/삭제가 장점이다.
구현 목적에 따라 적합한 방법을 선택해야 한다. 

 

배열을 통한 구현

자바에서 Stack 클래스를 상속받아 배열 기반으로 스택을 구현한 예제이다.

전체코드

package fc.stack;

import java.util.EmptyStackException;
import java.util.Stack;

public class FixedArrayStack<E> extends Stack<E> {
    private final int capacity; // 최대 크기
    private Object[] elements; // 데이터 저장용 배열
    private int size; // 현재 스택에 저장된 데이터 개수

    public FixedArrayStack(int capacity) {
        if (capacity <= 0) {
            throw new IllegalArgumentException("Capacity must be greater than 0");
        }
        this.capacity = capacity;
        this.elements = new Object[capacity];
        this.size = 0;
    }

    // push 메서드 오버라이딩
    @Override
    public E push(E item) {
        if (size >= capacity) {
            throw new IllegalStateException("Stack Overflow: Maximum capacity reached");
        }
        elements[size++] = item;
        return item;
    }

    // pop 메서드 오버라이딩
    @Override
    public E pop() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        @SuppressWarnings("unchecked")
        E item = (E) elements[--size];
        elements[size] = null; // 메모리 누수 방지
        return item;
    }

    // peek 메서드 오버라이딩
    @Override
    public E peek() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return (E) elements[size - 1];
    }

    // 스택 비어있는지 확인
    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    // 스택 크기 반환
    @Override
    public int size() {
        return size;
    }

    // 현재 스택의 최대 크기 반환
    public int getCapacity() {
        return capacity;
    }

    public static void main(String[] args) {
        FixedArrayStack<Integer> stack = new FixedArrayStack<>(3); // 최대 3개 저장 가능
        
        try {
            // 데이터 푸시
            stack.push(10);
            stack.push(20);
            stack.push(30);
            
            System.out.println("Stack size: " + stack.size()); // 3
            System.out.println("Top element: " + stack.peek()); // 30
            
            // 추가 데이터 푸시 (오버플로우 발생)
            stack.push(40); // 예외 발생
        } catch (IllegalStateException e) {
            System.err.println(e.getMessage());
        }
        
        // 데이터 팝
        System.out.println("Popped: " + stack.pop()); // 30
        System.out.println("Stack size after pop: " + stack.size()); // 2
    }
}

 

 

메서드 별  코드 

1. push 메서드

스택에 데이터를 추가하는 메서드이다.

배열이 가득 찬 경우 IllegalStateException(Stack Overflow) 을 발생시킨다.

@Override
public E push(E item) {
    if (size >= capacity) { 
        // 스택이 가득 찬 경우 예외 발생
        throw new IllegalStateException("Stack Overflow: Maximum capacity reached");
    }
    elements[size++] = item; // 데이터를 배열에 추가하고 크기 증가
    return item; // 추가된 데이터 반환
}

 

2. pop 메서드

스택에서 데이터를 꺼내는 메서드이다.
스택이 비어 있으면  EmptyStackException 을 발생시킨다.

@Override
public E pop() {
    if (isEmpty()) { 
        // 스택이 비어 있는 경우 예외 발생
        throw new EmptyStackException();
    }
    E item = (E) elements[--size]; // 최상단 데이터 꺼내기
    elements[size] = null; // 메모리 누수 방지
    return item; // 꺼낸 데이터 반환
}

 

3. peek 메서드 

스택의 최상단 데이터를 확인하는 메서드이다. 

스택이 비어 있는 경우  EmptyStackException 을 발생시킨다.

@Override
public E peek() {
    if (isEmpty()) { 
        // 스택이 비어 있는 경우 예외 발생
        throw new EmptyStackException();
    }
    return (E) elements[size - 1]; // 최상단 데이터 반환
}

 

 

4. isEmpty 메서드 

스택이 비어 있는지 확인하는 메서드이다. 

@Override
public boolean isEmpty() {
    return size == 0; // 데이터 개수가 0이면 비어 있음
}

 

5. size 메서드

스택에 저장된 데이터의 개수를 반환한다.

@Override
public int size() {
    return size; // 현재 스택에 저장된 데이터 개수 반환
}

 

6. getCapacity 메서드

스택의 최대 크기를 반환한다. 

기본 stack에 메서드는 아니고 배열로 구현했기 때문에 있다.

public int getCapacity() {
    return capacity; // 스택의 고정된 최대 크기 반환
}

 

 

ArrayList를 이용한 구현

마찬가지로 stack 클래스를 상속받아 구현한다. 

전체코드

import java.util.ArrayList;
import java.util.EmptyStackException;
import java.util.Stack;

public class ArrayListStack<E> extends Stack<E> {
    private ArrayList<E> list; // 데이터를 저장할 ArrayList

    // 생성자: ArrayList 초기화
    public ArrayListStack() {
        this.list = new ArrayList<>();
    }

    // push: 데이터를 스택에 추가
    @Override
    public E push(E item) {
        list.add(item); // ArrayList의 끝에 데이터 추가
        return item;    // 추가된 데이터 반환
    }

    // pop: 스택에서 최상단 데이터를 제거하고 반환
    @Override
    public E pop() {
        if (isEmpty()) {
            // 스택이 비어 있으면 예외 발생
            throw new EmptyStackException();
        }
        return list.remove(list.size() - 1); // 마지막 데이터를 제거하고 반환
    }

    // peek: 스택의 최상단 데이터를 반환 (제거하지 않음)
    @Override
    public E peek() {
        if (isEmpty()) {
            // 스택이 비어 있으면 예외 발생
            throw new EmptyStackException();
        }
        return list.get(list.size() - 1); // 마지막 데이터 반환
    }

    // isEmpty: 스택이 비어 있는지 확인
    @Override
    public boolean isEmpty() {
        return list.isEmpty(); // ArrayList가 비어 있는지 확인
    }

    // size: 스택에 저장된 데이터 개수 반환
    @Override
    public int size() {
        return list.size(); // ArrayList의 크기를 반환
    }

    public static void main(String[] args) {
        ArrayListStack<Integer> stack = new ArrayListStack<>();

        // 데이터 추가 (push)
        stack.push(10);
        stack.push(20);
        stack.push(30);

        System.out.println("Stack size: " + stack.size()); // 3
        System.out.println("Top element: " + stack.peek()); // 30

        // 데이터 제거 (pop)
        System.out.println("Popped: " + stack.pop()); // 30
        System.out.println("Stack size after pop: " + stack.size()); // 2
        System.out.println("Top element after pop: " + stack.peek()); // 20
    }
}

 

메서드 별  코드

1. push 메서드 

데이터는 항상 ArrayList의 끝에 추가된다. 

@Override
public E push(E item) {
    list.add(item); // 데이터를 ArrayList의 끝에 추가
    return item;    // 추가된 데이터 반환
}

 

2. pop 메서드 

스택의 최상단 데이터를 제거하고 반환한다.
스택이 비어 있으면 EmptyStackException 을 발생시킨다.

@Override
public E pop() {
    if (isEmpty()) {
        throw new EmptyStackException(); // 스택이 비어 있는 경우 예외 발생
    }
    return list.remove(list.size() - 1); // 마지막 데이터를 제거하고 반환
}

 

3. peek 메서드 

스택의 최상단 데이터를 반환한다.

스택이 비어 있으면 EmptyStackException  을 발생시킨다.

@Override
public E peek() {
    if (isEmpty()) {
        throw new EmptyStackException(); // 스택이 비어 있는 경우 예외 발생
    }
    return list.get(list.size() - 1); // 마지막 데이터를 반환
}

 

4. isEmpty 메서드 

스택이 비어 있는지 확인한다. 

@Override
public boolean isEmpty() {
    return list.isEmpty(); // ArrayList가 비어 있는지 확인
}

 

5. size 메서드 

@Override
public int size() {
    return list.size(); // ArrayList의 크기를 반환
}