Stack

Stack?

구현

먼저 stack에서 구현해야 하는 기능은 다음과 같다.

public interface Stack<E> {

    int size();

    boolean isEmpty();

    void push(E e);

    E top();

    E pop();

}

stack을 구현하는 방법은 배열을 사용하는 방법과 linked list를 사용하는 방법이 있다.

배열을 사용한 Stack, ArrayStack

배열을 사용하여 구현한 stack을 ArrayStack이라 칭한다. 구현한 코드는 아래와 같다.

public class ArrayStack <E> implements Stack<E>{
    public static final int CAPACITY = 1000;
    private E[] data;
    private int t = -1;

    public ArrayStack(){
        this(CAPACITY);
    }

    public ArrayStack(int capacity){
        data = (E[]) new Object[capacity];
    }

    public int size(){
        return (t+1);
    }

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

    public void push(E e) throws IllegalStateException{
        if(size() == data.length)
            throw new IllegalStateException("Statck is full");
        data[++t] = e;
    }

    public E top(){
        if(isEmpty())
            return null;
        return data[t];
    }

    public E pop(){
        if(isEmpty())
            return null;
        E answer = data[t];
        data[t] = null;
        t--;
        return answer;
    }

}

linked list를 사용한 Stack, Linked Stack

linked list를 사용하여 구현한 stack을 linked stack이라 칭한다. 구현한 코드는 아래와 같다.

public class LinkedStack<E> implements Stack<E> {

    private SinglyLinkedList<E> list = new SinglyLinkedList<>();
    public LinkedStack(){}
    public int size(){
        return list.size();
    }

    public boolean isEmpty(){
        return list.isEmpty();
    }

    public void push(E element){
        list.addFirst(element);
    }

    public E top(){
        return list.first();
    }

    public E pop(){
        return list.removeFirst();
    }

}

linked list를 구현한 코드는 여기서 볼 수 있다.