스택(Stack)

1. 스택이란?

스택이란 가장 뒤에 들어온 데이터가 가장 먼저 나가는 구조의 자료구조다.

스택은 맨 위의 원소만 접근 가능한 것이 특징이며 맨 위의 원소를 스택 탑(top)이라고 한다.

새 원소를 삽입할 때는 스택 탑 바로 윗자리에 원소를 저장한 후 새 원소가 스택 탑이 된다.

그리고 원소를 삭제할 때는 무조건 탑에 있는 원소를 삭제한 후 바로 아래 원소가 스택 탑이 된다.

 

2. 배열 스택의 구현

public interface StackInterface<E> {
    public void push(E newItem);
    public E pop();
    public E top();
    public boolean isEmpty();
    public void popAll();
}

public class ArrayStack<E> implements StackInterface<E> {
    private E stack[];
    private int topIndex;
    private static final int DEFAULT_CAPACITY = 64;
    private final E ERROR = null;

    public ArrayStack() {
        stack = (E[]) new Object[DEFAULT_CAPACITY];
        topIndex = -1;
    }

    public ArrayStack(int n) {
        stack = (E[]) new Object[n];
        topIndex = -1;
    }

    public void push(E newItem) {
        if(isFull()) {
            //에러처리
        } else {
            stack[++topIndex] = newItem;
        }
    }

    public E pop() {
        if(isEmpty()) return ERROR;
        else return stack[topIndex--];
    }

    public E top() {
        if(isEmpty()) return ERROR;
        else return stack[topIndex];
    }

    public boolean isEmpty() {
        return (topIndex < 0);
    }

    public boolean isFull() {
        return (topIndex == stack.length-1);
    }

    public void popAll() {
        stack = (E[]) new Object[stack.length];
        topIndex = -1;
    }
}

ArrayStack의 생성자는 2개다.

파라미터 없이 호출되면 DEFAULT_CAPACITY 크기의 배열을 할당하고, 아니면 지정한 크기의 배열을 할당한다.

// size=DEFAULT_CAPACITY
ArrayStack<Integer> s = new ArrayStack<>();

// size=n
ArrayStack<Integer> s = new ArrayStack<>(n);

그리고 topIndex는 -1로 셋팅한다.

배열의 시작 인덱스는 0이기 때문에 스택이 비어있을 경우 topIndex는 -1이 되어야 한다.

 

3. 연결 리스트 스택의 구현

public class Node<E> {
    public E item;
    public Node<E> next;
    
    public Node(E newItem) {
        item = newItem;
        next = null;
    }
    
    public Node(E newItem, Node<E> nextNode) {
        item = newItem;
        next = nextNode;
    }
}

public interface StackInterface<E> {
    public void push(E newItem);
    public E pop();
    public E top();
    public boolean isEmpty();
    public void popAll();
}

public class LinkedStack<E> implements StackInterface<E> {
    private Node<E> topNode;
    private final E ERROR = null;
    public LinkedStack() {
        topNode = null;
    }

    public void push(E newItem) {
        topNode = new Node<>(newItem, topNode);
    }

    public E pop() {
        if(isEmpty()) return ERROR;
        else {
            Node<E> temp = topNode;
            topNode = topNode.next;
            return temp.item;
        }
    }

    public E top() {
        if (isEmpty()) return ERROR;
        else return topNode.item;
    }

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

    public void popAll() {
        topNode = null;
    }

}