[자료구조] 자바로 Stack 직접 구현해보기

오랜만에 자료구조를 직접 구현해보는 연습을 해보고있다.

스택은 자주 사용하는 자료구조이며, 어느정도 개념도 잘 알고 있다보니 직접 구현하는 게 어렵진 않았다.

그래서 나 스스로에게 미션(?)을 부여하면서 구현해보았다.

 

첫번째는, 제네릭을 사용해서 구현할 것.

두번째는, 스택의 구성은 배열과 링크드리스트 두가지 버젼을 구현해볼것.

 

이를 구현하기 위해서 인터페이스를 사용했다.

보통 스택에서 사용하는 메소드들을 인터페이스를 통해 선언해놓고 배열 스택과 링크드리스트 스택에서 구현하도록 했다.

역시 이때 요소의 타입은 제네릭을 사용하여 지정하도록 하였다.

 

Stack

public interface Stack<E> {
    boolean add(E data);
    E pop();
    E peek();
    E get(int idx);
    boolean isEmpty();
    void clear();
}

 

 

 

1) 배열을 이용한 스택 - ArrayStack

import java.util.Arrays;

public class ArrayStack<E> implements Stack<E> {
    private final int initCapacity = 100;
    private Object[] arr = new Object[initCapacity];
    private int size = 0;

    private void increaseCapacity() {
        int newSize = arr.length + initCapacity;
        arr = Arrays.copyOf(arr, newSize);
    }

    @Override
    public boolean add(E data) {
        if(size >= arr.length-1) {
            increaseCapacity();
        }

        arr[size++] = data;
        return true;
    }

    @Override
    public E pop() {
        E data = (E) arr[--size];
        arr[size] = 0;
        return data;
    }

    @Override
    public E peek() {
        return (E) arr[size-1];
    }

    @Override
    public E get(int idx) {
        if(idx >= size) {
            throw new ArrayIndexOutOfBoundsException();
        }
        return (E) arr[idx];
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public void clear() {
        size = 0;
        arr = new Object[initCapacity];
    }
}

배열용 스택은 배열의 크기를 처음에 100만큼 할당해준다음, 꽉차면 배열의 크기를 100씩 늘려주는 식으로 구현했다.

 

 

 

2) 링크드 리스트를 이용한 스택 - LinkedListStack

public class LinkedListStack<E> implements Stack<E> {
    private Node<E> head;
    private Node<E> top;
    private int size = 0;

    private class Node<E> {
        private Node<E> next;
        private E data;

        public Node(E data) {
            this.data = data;
        }
    }

    public Node<E> search(int idx) {
        if(size <= idx) {
            throw new ArrayIndexOutOfBoundsException(idx);
        }
        Node node = head;

        for (int i = 0; i < idx; i++) {
            node = node.next;
        }

        return node;
    }

    @Override
    public boolean add(E data) {
        Node<E> newNode = new Node<>(data);

        if(isEmpty()) {
            head = newNode;
            top = newNode;
        } else {
            Node<E> tmp = top;
            tmp.next = newNode;
            top = newNode;
        }
        size++;
        return true;
    }

    @Override
    public E pop() {
        Node<E> deleted = top;
        E data = deleted.data;

        if(size == 1) {
            head = null;
            top = null;
        } else {
            Node<E> node = search(size - 2);
            node.next = null;
            top = node;
        }
        deleted = null;
        size--;
        return data;
    }

    @Override
    public E peek() {
        return top.data;
    }

    @Override
    public E get(int idx) {
        return search(idx).data;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public void clear() {
        Node<E> node = head;

        while(node != null) {
            Node<E> tmp = node;
            node = node.next;
            tmp = null;
        }
        head = null;
        top = null;
        size = 0;
    }
}

링크드리스트 스택은 head와 top 노드 정보를 가지며 각 노드는 다음 노드 정보를 가지고 있다.

링크드리스트를 구현해봤다면 어렵지 않게 구현할 수 있을 것이다.

 

 

 

혹시 잘못된 부분이 있으면 댓글 남겨주세요!