Stack ADT 정의, Java 구현

일단 Stack의 ADT부터 정의해보자.

https://ko.wikipedia.org/wiki/%EC%8A%A4%ED%83%9D

스택은 대표적인 LIFO 나열 구조로서 한 쪽 끝에서만 자료를 넣고 빼는 선형구조이다.
따라서 최상단에 자료를 추가 - O(1), 최상단 자료를 삭제 - O(1), 최상단 자료를 조회 - O(1), 비었는지 확인 - O(1) 하는 연산이 존재한다.

또한 자료를 정적 배열에 저장하는지 혹은 LinkedList로 저장하는 지에 따라 resizing을 해주는 연산이 필요할 수도, 필요하지 않을 수도 있다. 여기서는 단방향 링크드리스트 구조로 정의 하였다.

1. Stack과 Node에 필요한 필드를 정의한다.

public class Stack {
    private Node top;

    private class Node {
        Object data;
        Node link;

        Node(Object input, Node link) {
            this.data = input;
            this.link = link;
        }
    }
}

 

2. 추가 - push(data), 삭제 - pop(), 조회 - peek(), isEmpty() 를 정의하였다.

public void push(Object o) {
	top = new Node(o, top);
}

public Object pop() {
	if(isEmpty()) throw new IllegalStateException();
    
    Object data = top.data;
    top = top.link;
    return data;
}

public Object peek() {
	if(isEmpty()) throw new IllegalStateException();
    return top.data;
}

public boolean isEmpty() {
	return top == null;
}

 

- 정리

interface StackInterface {
    boolean isEmpty();
    void push(Object o);
    Object pop();
    Object peek();
}

public class Stack implements StackInterface {
    private Node top;

    private class Node {
        Object data;
        Node link;

        Node(Object input, Node link) {
            this.data = input;
            this.link = link;
        }
    }

    public boolean isEmpty() {
        return top == null;
    }

    public void push(Object o) {
        top = new Node(o, top);
    }

    public Object pop() {
        if(isEmpty()) throw new IllegalStateException();

        Object data = top.data;
        top = top.link;
        return data;
    }

    public Object peek() {
        if(isEmpty()) throw new IllegalStateException();
        return top.data;
    }

    public String toString() {
        if(isEmpty()) throw new IllegalStateException();
        StringBuilder sb = new StringBuilder("[");
        Node tmp = top;
        while(tmp.link != null) {
            sb.append(tmp.data).append(",");
        }
        sb.append(tmp.data).append("]");
        return sb.toString();
    }
}