2. 스택 stack

• Stack이란?
  LIFO(Last In, First Out) 후입, 선출 / 먼저 들어간게 먼저 나온다.
  리스트의 제한된 형태 넣고 빼기가 리스트의 한쪽 끝에서만 가능하다.(뒤에서만 넣고 빼기가 가능한 리스트)
  PUSH(넣기) POP(빼기) TOP(맨 위의 값 리턴)
  
  
• Stack ADT

public interface Stack<E> {
    public void clear(); // 전부 다 지우기
    
    public void push(E it); // 값을 맨 위에 넣기
    
    public E pop(); // 맨 위의 값을 빼서 쓰기 (return타입이 있는 이유)
    
    public E topValue(); // 맨 위의 값을 가져만 오기 (return타입이 있는 이유)
    
    public int length(); // 스택에 얼마나 많은 아이템이 들어가있는지를 리턴
}

• ADT의 구현 방법 ( Array, Link )

//Array의 경우
public class AStack<E> implements Stack<E> {

    public int maxSize;
    public int top;
    public E[] listArray;

    public AStack(int capacity) {
        maxSize = capacity;
        listArray = (E[]) new Object[capacity];
        top = -1;
    }

    @Override
    public void clear() {
        top = -1;
    }

    @Override
    public E top() {
        if (top == -1) {
            return null;
        } else {
            return listArray[top];
        }
        return null;
    }

    @Override
    public E pop() {
        if (top == -1) {
            return null;
        } else {
            // E ret = listArray[top];
            // top--;
            // return ret;
            return listArray[top--];
        }
    }

    @Override
    public void push(E it) {
        top++;
        listArray[top] = it;
    }

    @Override
    public int length() {
        return top + 1;
    }

}

//Linked List의 경우
class Link<E> {
    public E item;
    public Link<E> next;

    public Link(E item, Link<E> next) {
        this.item = item;
        this.next = next;
    }
}

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

    Link<E> head;
    int size;

    public LStack() {
        head = new Link<E>(null, null);
        size = 0;
    }

    @Override
    public void clear() {
        head.next = null;
        size = 0;
    }

    @Override
    public E top() {
        if (head.next == null)
            return null;
        else
            return head.next.item;
    }

    @Override
    public E pop() {
        if (head.next == null)
            return null;
        else {
            E ret = head.next.item;
            head.next = head.next.next;
            size--;
            return ret;
        }
    }

    @Override
    public void push(E it) {
        head.next = new Link(it, head.next);
        size++;
    }

    @Override
    public int length() {
        return size;
    }

}