Stack 구현 해보기 (자바)

1. 배열을 통한 구현

import java.util.Arrays;

public class ArrayStack<T> {

    private static final int DEFAULT_CAPACITY = 16;
    private int top;
    private T[] stackArr;

    @SuppressWarnings("unchecked")
    public ArrayStack() {
        this.top = -1;
        this.stackArr = (T[]) new Object[DEFAULT_CAPACITY];
    }

    @SuppressWarnings("unchecked")
    public ArrayStack(int size) {
        this.top = -1;
        this.stackArr = (T[]) new Object[size];
    }

    public void push(T t) {
        if (isFull()) {
            resize(2 * stackArr.length);
        }
        stackArr[++top] = t;
    }

    public T pop() {
        if (top == -1) {
            throw new ArrayIndexOutOfBoundsException();
        }

        T item = stackArr[top--];

        if (isTooBigSize()) {
            resize(stackArr.length / 2);
        }

        return item;
    }

    public T peek() {
        if (top == -1) {
            throw new ArrayIndexOutOfBoundsException();
        }
        return stackArr[top];
    }

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

    private boolean isFull() {
        return top == stackArr.length - 1;
    }

    private boolean isTooBigSize() {
        return top < (stackArr.length / 4);
    }

    private void resize(int newCapacity) {
        stackArr = Arrays.copyOf(stackArr, Math.max(DEFAULT_CAPACITY, newCapacity));
    }
}

 

2. LinkedList 방식의 구현

public class Node<T> {
    private T data;
    private Node<T> nextNode;

    public Node(T data) {
        this.data = data;
        this.nextNode = null;
    }

    protected void linkNode(Node<T> node) {
        this.nextNode = node;
    }

    protected T getData() {
        return this.data;
    }

    protected Node<T> getNextNode() {
        return this.nextNode;
    }
}

public class ListStack<T> {
    Node<T> top;

    public ListStack() {
        this.top = null;
    }

    public void push(T data) {
        Node<T> node = new Node<>(data);
        node.linkNode(top);
        top = node;
    }

    public T peek() {
        if (empty()) {
            throw new ArrayIndexOutOfBoundsException();
        }
        return top.getData();
    }

    public T pop() {
        if (empty()){
            throw new ArrayIndexOutOfBoundsException();
        }
        T data = top.getData();
        top = top.getNextNode();
        return data;
    }

    private boolean empty() {
        return top == null;
    }
}

 

결론

사이즈의 동적할당을 통해서 메모리 상 이득, 리사이즈를 하지 않아도 되는 편의성 등 LinkedList 방식의 구현이 보다 좋다는 생각.