[기초 자료구조] Stack(스택) - Array 기반 / LinkedList 기반

Stack 기본 개념

• LIFO(Last In First Out) 형식의 기초 자료구조
  • 아래 그림처럼 한 쪽 끝에서만 데이터를 넣고 뺄 수 있다.
• 이러한 구조는 '뒤로 가기'나 '실행 취소(undo)', 컴퓨터 구조에서의 'stack memory'에서 사용된다.
• 구조 상 당연히 직전에 추가된 데이터를 빠르게 가지고 올 수 있다.
• 기본적으로 Java에서 Stack 클래스는 내부에서 최상위 타입 배열인 Object[] 배열을 사용해 데이터들을 관리하고 있다.

 

Stack 기본 연산

• push(item): item 하나를 스택의 가장 윗 부분에 추가한다.
• pop(): 스택에서 가장 위에 있는 항목을 제거한다.
• peek(): 스택의 가장 위에 있는 항목을 반환한다.
• isEmpty(): 스택이 비어 있을 때에 true를 반환한다.

 

구현 방법

• 배열(Array), 연결리스트(LinkedList) 2가지 방법으로 많이 구현된다.
• 배열 스택은 처음에 배열의 크기를 할당해서 사용한다.
• LinkedList는 값을 추가 하거나 뺄 때마다 크기를 조절한다.

Array Stack

// Array 기반 Stack
class ArrayStack<T> {
    private int top;
    private Object[] stack;
    private int size;

    ArrayStack(int size) {
        this.top = -1;
        this.stack = new Object[size];
        this.size = size;
    }

    boolean isEmpty() {
        return this.top < 0 ? true : false;
    }

    T peek() {
        return isEmpty() ? null : (T) this.stack[top];
    }

    void push(T value) {
        if (++top >= size)
            return;
        stack[top] = value;
    }

    T pop() {
        if (isEmpty())
            return null;
        else {
            T ret = (T) stack[top--];
            return ret;
        }
    }
}

• Stack 생성 시 크기를 할당한다.

 

LinkedList Stack

// LinkedList 기반 Stack Node
class StackNode<T> {
    T value;
    StackNode<T> next;

    StackNode(T value) {
        this.value = value;
        this.next = null;
    }
}


// LinkedList 기반 Stack
class LinkedStack<T> {
    private StackNode<T> list = null;

    boolean isEmpty() {
        return list == null ? true : false;
    }

    void push(T value) {
        StackNode<T> node = new StackNode<T>(value);
        node.next = list;
        list = node;
    }

    T pop() {
        if (isEmpty())
            return null;
        else {
            StackNode ret = list;
            list = list.next;
            return (T) ret.value;
        }
    }

    T peek() {
        if (isEmpty())
            return null;
        else
            return list.value;
    }
}

• LinkedList의 같은 방향에서 item을 추가하고 삭제하도록 구현된다.