[Java] Stack 구현

스택이란?

출처 : https://devdojo.com/algonoob/stacks

• Stack은 쌓다, 쌓이다, 포개지다 와 같은 뜻을 가지고 있다.
• 뜻 그대로 데이터를 순서대로 쌓는 자료구조이다.
• 스택에 데이터를 넣는 작업을 push라 하며, 스택에서 데이터를 꺼내는 작업을 pop이라 한다.
  pop을 통해 데이터를 꺼내면 스택에서 제거된다.
• push와 pop이 이루어지는 부분을 top이라 하고, 가장 아랫부분을 bottom이라 한다.

스택의 특징

1. LIFO(Last In First Out) 또는 FILO(First In Last Out)
   데이터의 입력과 출력 순서는 후입선출로 가장 나중에 삽입된 데이터를 가장 먼저 꺼낼 수 있는 구조를 가지고 있다.
2. 즉, 스택의 마지막 위치에서 데이터의 삽입과 추출이 이루어진다.
3. 데이터는 하나씩만 넣고 뺄 수 있다.

Stack 구현 - 배열

장점

• 인덱스로 관리하기 때문에 매우 빠르게 접근 가능

단점

• 메모리 사용 비효율적
• 데이터 이동 및 재구성이 어렵다.

import java.util.EmptyStackException;

public class ArrayStack {
    private Object[] stack;
    private int capacity;
    private int top;

    // 배열 스택 생성자
    public ArrayStack(int length) {
        capacity = length;
        this.top = 0;
        try {
            stack = new Object[capacity];
        } catch (OutOfMemoryError e) { // 생성할 수 없음
            capacity = 0;
        }
    }

    // 데이터 삽입
    public void push(Object data) {
        if (top >= capacity) {throw new StackOverflowError();}
        stack[top++] = data;
    }
    // 데이터 빼기
    public Object pop() {
        if (top < 0) {
            throw new ArrayIndexOutOfBoundsException();
        }
        return stack[--top];
    }
    // 현재 top의 데이터 가져오기 (데이터 제외 x)
    public Object peek() {
        if (top < 0) {
            throw new EmptyStackException();
        }
        return stack[top - 1];
    }
    // 스택 비움
    public void clear() {
        top = -1;
    }
    // 스택이 비었는지 확인
    public boolean isEmpty() {
        return top == -1;
    }
    // 스택이 가득 찾는지 확인
    public boolean isFull() {
        return top == capacity;
    }
}

Stack 구현 - 연결리스트

장점

• 유동적으로 크기 값을 가지는 스택을 생성할 수 있다.
• 데이터 재구성 용이
• 대용량 데이터 처리 적합

단점

• 인덱스를 사용하지 못해 데이터를 꺼내오고 삭제할 때 처음부터 마지막 노드까지 순회해야 한다.

import java.util.EmptyStackException;

public class LinkedListStack {
    private Node head;
    private Node top;

    private class Node {
        private Object data;
        private Node next;

        public Node(Object data) {
            this.data = data;
        }
    }
    // 스택의 마지막 위치에 데이터 삽입 메서드
    public void push(Object data) {
        if (head == null) {
            head = new Node(data);
            top = head;
            return;
        }
        Node node = new Node(data);
        top.next = node;
        top = node;
    }
    // 스택의 마지막 데이터 추출 메서드
    public Object pop() {
        if (top == null) { // 빈 스택
            throw new EmptyStackException();
        }
        Node temp = head;
        Object data = this.peek();
        if (temp.next == null) {
            head = null;
            top = null;
            return data;
        }
        while (temp.next != null) {
            top = temp;
            temp = temp.next;
        }
        top.next = null;
        return data;
    }
    // 마지막 노드의 데이터 확인 메서드
    public Object peek() {
        return top.data;
    }
    // 빈 스택인지 확인 메서드
    public boolean isEmpty() {
        return top == null;
    }
}