스택(Stack)

---

스택의 정의

데이터의 삽입과 삭제가 top이라 불리는 한쪽 끝에서만 발생하는 선형 구조이다.

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

 

가장 늦게 들어간 데이터가 가장 먼저 삭제되고, 가장 먼저 들어간 데이터가 가장 늦게 삭제된다.

이를 LIFO(Last In First Out)구조 , 혹은 FILO(First In Last Out)구조라고 할 수 있다. 

 

스택의 연산

push

스택의 가장 위(top)에 데이터를 삽입한다.

pop

스택의 가장 위(top) 데이터를 삭제한다.

peek

스택의 가장 위(top) 데이터를 반환한다.

isEmpty

스택이 비어있는지 확인한다.

isFull

스택이 꽉 차있는지 확인한다.

getSize

스택에 현재 저장된 데이터의 수를 반환한다.

 

스택의 구현

스택을 구현하는 방법에는 두 가지 방법이 있다.

배열을 통해 구현하는 방법과, 연결리스트를 이용하여 구현하는 방법이다.

배열을 이용한 스택의 구현

public class ArrayStack {
    int top = -1;
    Object[] stack;

    public ArrayStack(int size) {
        this.stack = new Object[size];    
    }

    void push(Object data) {
        if(isFull()) {
            throw new IllegalStateException("Stack is full.");
        }
        stack[++top] = data;
    }

    Object pop() {
        if(isEmpty()) {
            throw new IllegalStateException("Stack is empty");
        }
        return stack[top--];
    }

    Object peek() {
        if(isEmpty()) {
            throw new IllegalStateException("Stack is empty");
        }
        return stack[top];
    }

    boolean isFull() {
        return top<=(stack.length-1);
    }

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

}

 

 

- push 연산 시, stack이 이미 꽉 차 있지 않은지 확인해주어야 한다. 꽉 찬 경우 에러 처리를 해주었다.

- pop/peek 연산 시, stack이 비어있지 않은지 확인해주어야 한다. 빈 경우 에러 처리를 해주었다.

 

연결리스트를 이용한 스택의 구현

import java.util.EmptyStackException;

class Node<T> {
    public Node(T data, Node<T> link) {
        this.data = data;
        this.next = link;
    }
    T data;
    Node<T> next;
}

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

    void push(T data) {
        Node<T> newNode = new Node<T>(data,top);
        top = newNode;
    }

    T pop() {
        if(isEmpty()) {
            throw new IllegalStateException("Stack is empty");
        }
        Node<T> pastTop = top;
        T popData = top.data;
        top = pastTop.next;
        pastTop.data = null;
        pastTop.next = null;
        return popData;
    }

    T peek() {
        if(isEmpty()) {
            throw new IllegalStateException("Stack is empty");
        }
        return top.data;
    }

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

}

- 연결 리스트로 구현된 스택의 경우, 메모리가 다 차지 않는한 크기 제한이 없기 때문에 isFull 메서드를 구현하지 않았다.

 

* pop()시  pastTop.data = null; pastTop.next = null; 을 해주는 이유

연결리스트에서 노드를 제거할 때 해당 노드의 참조를 제대로 해제하지 않으면 프로그램이 오래 실행됨에 따라 사용하지 않는 참조가 유지되면서 메모리 누수가 발생할 수 있다. 

따라서 노드의 참조를 모두 제거하여 가비지 컬렉터에 의해 해당 메모리가 제거될 수 있도록 한다.

 

각 구현의 장단점

배열

장점: 구현이 간단하다. 메모리를 동적으로 생성하지 않으므로 데이터의 삽입과 삭제가 빠르다.

단점: stack의 크기가 고정되어있다. 따라서 메모리가 낭비될 가능성이 있다. (고정된 크기의 배열을 전부 사용하지 않을 경우)

연결리스트

장점: stack의 크기를 가변적으로 사용할 수 있다.

단점: 메모리를 동적으로 생성하므로 배열보다 데이터 처리에 속도가 느리다.