🛠️ Stack 자료구조 실전 구현 강의 (JAVA)

Stack 자료구조

Stack 특징으론 다음과 같이 요약이 가능하다.

• LIFO(Last In First Out), 후입선출(後入先出) 구조이다. 마지막에 들어온게 첫번째로 빠져나간다.
• 그래서 직전의 데이터를 빠르게 갖고 올 수 있다.
• 뒤로 가기, 실행 취소(redo/undo), 그리고 컴퓨터 구조에서의 스택 메모리가 대표적이다.
• 균형성 검사를 할 수 있기 때문에 수식, 괄호 등의 검사에서도 쓰인다.

[JCF] 🧱 Stack 구조 & 사용법 정리

---

Stack 실전 구현하기 (배열)

가장 기본적으로 스택(Stack) 자료 구조를 직접 구현할때 여느 프로그래밍 언어에서 공통적으로 사용하는 것이 배열(Array)을 이용한 스택 구현이다. 직접 한번 구현해보는 시간을 가져보자.

---

클래스 필드 & 생성자 정의하기

• DEFAULT_CAPACITY : 배열이 생성 될 때의 기본 할당 용량
• arr : 요소들을 담을 내부 배열
• top : 스택의 가장 마지막 원소를 가리키는 인덱스 필드. 초깃값은 -1로 설정한다. 이 top을 이용해서 스택의 요소 추가/삭제의 모든 동작이 이루어 진다.

public class MyStack<E> {
    private static final int DEFAULT_CAPACITY = 6; // 최소 용량 크기
    private Object[] arr; // 요소를 담을 내부 배열
    private int top; // 스택의 가장 마지막 요소를 가리키는 포인터

    // 생성자
    public MyStack() {
        this.arr = new Object[DEFAULT_CAPACITY]; // 6 용량으로 내부 배열 생성
        this.top = -1;
    }
}

---

isFull / isEmpty 구현하기

본격적인 push, pop 구현에 앞서 스택의 공간을 검사하는 메서드를 미리 정의한다. 이들은 스택의 배열이 꽉 차있는지 검사를 하고 아래에서 구현할 resize 동작을 행하는 분기문 형태로 사용되어질 것이다.

• isFull() : 꽉차있을 경우 true
• isEmpty() : 비어있을 경우 false

public boolean isFull() {
    // 마지막 요소 위치인 top이 배열 길이 - 1 과 같은 경우 끝까지 차있는 것과 같음
    return top == arr.length - 1;
}

public boolean isEmpty() {
    // 마지막 요소 위치인 top이 -1을 가리키는 경우, 배열이 비어있는 것과 같음
    return top == -1;
}

---

resize 구현하기

배열은 크기가 고정 되어있기 때문에 만일 배열 용량(capacity)가 꽉차게 되면 더이상 원소를 추가할 수 가 없다. 그래서 몇몇 스택 구현 예제에서는 배열이 꽉차렴 배열의 크기를 늘리지 않고 더이상 원소를 받지 않도록 예외를 구현한 경우도 있는데, 이 포스팅에서는 좀더 유연하게 자료구조를 처리하기 위해 가변 배열 처리를 통해 구현해볼 것이다.

resize() 메서드는 스택에 요소가 추가, 삭제 등의 동작이 될때 기본적으로 호출된다. 마지막 원소를 가리키는 top의 인덱스 값과 배열의 용량(arr.length)을 비교하여, 크거나 작은 경우 이를 감지해서 리사이징을 처리하여 메모리 최적화를 노린다고 보면 된다.

// 클래스 내부에서만 실행되는 메소드이니 private
private void resize() {
    int arr_capacity = arr.length - 1; // 현재 배열의 용량에 -1 한 값을 얻음 (배열 인덱스는 0부터 시작하니까)
 
    // 용량이 꽉찬 경우
    if() ... 사이즈를 늘린다
 
    // 용량에 비해 데이터 양이 적은 경우
    if() ... 사이즈를 줄인다
}

 

1. 용량이 꽉찬 경우

아래 코드에서 용량의 2배로 설정하는 이유는 넉넉하게 공간을 유지하기 위해서이다. 왜냐하면 resize 메서드가 자주 호출되어 배열을 복사하여 새로 만드는 행위가 빈번히 일어난다면 성능에 마이너스가 될 수 있기 때문이다. 빈 공간은 자동으로 null로 채워지기 때문에 문제는 없다. 다만 자료구조 알고리즘에 따라 확장 기준이 다를수 있다는 점은 유의하자. 

// 용량이 꽉찬 경우
if(top == arr_capacity) {
    // 넉넉하게 공간을 유지하기 위해 현재 용량의 두배로 설정
    int new_capacity = arr.length * 2;

    // 복사할 배열을 new_capacity 용량 만큼 설정하고 arr 원소들을 전체 복사해서 넣고 반환 (빈공간은 null)
    arr = Arrays.copyOf(arr, new_capacity);
    return;
}

 

2. 용량에 비해 데이터 양이 적은 경우

적정한 공간을 유지하다 너무 배열 원소가 공간에 비해 적게 들어있을 경우 최적화를 위해 리사이징 하는 작업이다.

크기 계산 기준은 현재 배열 원소 갯수(size)가 현재 배열 용량(capacity)의 절반 보다 작을 경우로 정하였다. 그리고 배열을 복사할때 축소할 배열의 용량을 정할때 Math.max() 메서드를 이용하였는데, 위에서 리스트의 기본 할당 용량을 정하였으니, 이에 대한 원칙을 따르기 위해 절반으로 줄인 용량보다 기본 용량이 더 클 경우 기본 용량으로 설정하기 위해서다.

// 용량에 비해 데이터 양이 적은 경우
if (top < (arr_capacity / 2)) {
    // 기존 용량의 반을 설정
    int half_capacity = arr.length / 2;

    // half_capacity 와 디폴트 용량 중 큰걸 복사
    arr = Arrays.copyOf(arr, Math.max(half_capacity, DEFAULT_CAPACITY));
    return;
}

---

Push 구현하기

스택에서 데이터를 추가하는 작업을 push 라고 한다. (리스트에서의 add와 같은 역할이다)

데이터를 스택에 push 하기 앞서 반드시 스택이 꽉 차있는지 검사를 하고, 빈 공간이 없다면 위에서 구현한 리사이징 처리를 해주면 된다.

public E push(E value) {
    // 1. 배열이 꽉 차있는지 검사한다.
    if (isFull())
        resize(); // 꽉 찼으면 배열 리사이징 실행

    // 2. 원소를 추가할 예정이니 마지막 요소 위치인 top을 1 증가시킨다.
    top++;

    // 3. 그리고 해당 배열 위치에 요소를 추가한다.
    arr[top] = value;

    // 4. 넣은 요소의 값을 반한다.
    return value;
}

 

1. 먼저 스택에 빈공간이 있는지 검사한다.

 

2. 빈공간이 있다면 Top을 하나 증가시킨다.

 

3. Top 위치에 원소를 추가한다.

---

Pop 구현하기

스택에서 데이터를 제거하는 작업을 pop 이라고 한다. (리스트에서의 remove와 같은 역할이다)

데이터를 스택에 pop 하기 앞서 반드시 스택에 꺼낼 데이터가 있는지 검사를 하고, 꺼낼 원소가 없으면 EmptyStackException 예외를 발생 시킨다.

@SuppressWarnings("unchecked")
public E pop() {
    // 1. 배열이 비어있으면 예외 발생
    if (isEmpty())
        throw new EmptyStackException();

    // 2. 먼저 arr[top] 원소를 백업한다.
    E value = (E) arr[top];

    // 3. 해당 위치의 요소를 삭제한다.
    arr[top] = null;

    // 4. top을 1 감소 시킨다.
    top--;

    // 5. 혹시 들어있는 요소에 비해 빈공간이 많으면 최적화를 위해 리사이징을 해준다.
    resize();

    // 6. 백업한 요소를 반환한다.
    return value;
}

@SuppressWarnings("unchecked")

Object 배열인 arr에서 가져오게 되는 요소가 Object 타입이라 제네릭 E 타입으로 형변환해줘야 하는데, 형변환 하는 과정에서 아마 에디터에서 경고창이 뜨게 될 것이다. 왜냐하면 제네릭 자체가 확인되지 않은 모호한 타입이라 그렇다.
하지만 어차피 스택 클래스에서 제네릭 타입으로만 요소를 다루기 때문에 형 안정성이 확보되므로 ClassCastException이 뜨지 않으니 이 경고들을 무시하겠다는 의미인 어노테이션인 @SuppressWarnings("unchecked") 을 메서드 위에 붙여준다.
다만 이 어노테이션을 남발하면 안되고, 캐스팅시 예외 가능성이 확실히 없을 경우에만 써주는 것이 좋다. 그렇지 않으면 중요한 경고 메세지를 놓칠 수도 있다.

 

1. 먼저 스택에 꺼낼 요소가 있는지 검사하고, 요소를 꺼낸다.

 

2. 요소를 꺼냈으면 스택의 Top을 1 감소 시킨다. 그러면 계속 스택의 마지막 원소 위치를 가리키게 된다.

---

Peek 구현하기

스택의 마지막 원소의 값만 확인하고 꺼내지는 않고 싶을 상황이 있을 수 있다. 그럴 때 쓰는 것이 peek 동작이다. 간단히 말하자면 pop 에서 삭제 과정만 없는 것이 peek 인 것이다.

@SuppressWarnings("unchecked")
public E peek() {
    // 1. 배열이 비어있으면 예외 발생
    if (isEmpty())
        throw new EmptyStackException();

    // 2. 스택의 마지막 원소 값만 반환한다. (삭제 X)
    return (E) arr[top];
}

---

search 구현하기

스택의 search 동작은 리스트의 indexOf 와 비슷하지만 약간 차이가 있다. search 의 반환 숫자는 스택의 상단의 위치로부터 얼마만큼 떨어져 있는 지에 대한 상대적 위치 값이다.

이를 그림으로 표현하면 아래와 같이 된다. 즉, 맨 마지막 데이터가 1이라는 의미는 첫번째로 꺼내질 요소라는 뜻이 되게 된다.

public int search(E value) {

    // 스택 맨 위 서부터 아래로 순회하여 찾고자 하는 값의 위치를 구한다.
    for (int i = top; i >= 0; i--) {
        if(arr[i].equals(value)) {
            return top - i + 1;
        }
    }

    // 만일 찾고자 하는 값이 없다면 -1을 반환
    return -1;
}

---

toString 구현하기

스택 배열을 콘솔 화면에 출력하기 위한 메서드이다. 간단하게 Arrays.toString(내부배열) 코드를 통해 구현해주면 된다.

@Override
public String toString() {
    return Arrays.toString(arr);
}

---

지금까지 스택의 기본적인 구조를 직접 구현해보았다. 마지막으로 직접 구현해본 스택 자료구조가 잘 동작되는지 아래 실행 코드로 테스트를 해보자.

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

    stack.push(1);
    stack.push(2);
    stack.push(3);
    stack.push(4);

    System.out.println(stack); // [1, 2, 3, 4]

    System.out.println(stack.peek()); // 4

    System.out.println(stack.search(4)); // 1
    System.out.println(stack.search(3)); // 2

    stack.pop();
    stack.pop();
    stack.pop();

    System.out.println(stack); // [1]
}

---

Stack 실전 구현하기 (ArrayList 재활용)

사실 자바에는 별도로 java.util.Stack 클래스가 존재한다. 하지만 이 Stack 클래스는 지원이 끊긴 구식 클래스인 Vector를 상속하고 있어 여러모로 문제점이 많다.

따라서 직접 스택 클래스를 만들어 사용하여야 하는데, 우리가 지금까지 직접 내부 배열을 이용해 한땀 한땀 스택을 만들어 사용하는 방법도 좋지만, 더 좋은 방법은 자바의 대표적인 가변 배열 클래스인 java.util.ArrayList를 이용하여, 리스트의 메서드를 위임을 통해 push, pop 동작만 별도로 추가해주는 식으로 보다 간단하게 스택 클래스를 만들 수 있다.

이미 공간 리사이징이 구현되어있는 ArrayList를 이용하면 별도로 빈 공간 검사할 필요가 없고 코드도 훨씬 간단해진다.

public class MyStack<E> {
    private ArrayList<E> list; // 요소를 담을 내부 리스트
    private int top; // 스택의 가장 마지막 요소를 가리키는 포인터

    // 생성자
    public MyStack() {
        this.list = new ArrayList<>();
        this.top = -1; // 기본 빈 값을 표현하기 위해 -1 로 초기화
    }

    public boolean isFull() {
        return top == list.size() - 1;
    }

    public boolean isEmpty() {
        return top == -1;
    }

    // ArrayList에서 알아서 리사이징 되니 구현할 필요가 없다.
    // private void resize() {}

    public E push(E value) {
        list.add(++top, value); // 리스트의 ++top 위치에 value를 추가
        return value;
    }

    public E pop() {
        E value = list.get(top);
        list.remove(top--); // 리스트의 top 위치의 요소를 삭제하고 top 감소
        return value;
    }

    public E peek() {
        return list.get(top);
    }

    public int search(E value) {
        // 스택은 같은 요소값이 있으면 가장 마지막에 추가한 요소를 먼저 반환하기 때문에 lastIndexOf() 메서드를 사용한다.
        int result = list.lastIndexOf(value);

        if (result != -1) {
            return top - result + 1;
        } else {
            return result;
        }
    }

    @Override
    public String toString() {
        return list.toString(); // ArrayList의 toString() 메서드만 호출 하면 된다.
    }
}

---

# 참고자료

https://www.programiz.com/dsa/stack