스택

스택

• 후입선출(Last In First Out; LIFO) 자료구조
  • 마지막에 들어온 데이터가 먼저 나가는 구조
• 데이터가 입력된 순서의 역순으로 처리되어야할 때 사용
  • 함수 콜 스택, 수식 계산, 인터럽트 처리 등등

배열을 이용한 스택

class Stack {
    int[] arr;
    int top = -1;

    Stack(int size) {
        arr = new int[size];
    }

    public boolean isEmpty() {
        if (top == -1) {
            return true;
        }

        return false;
    }

    public boolean isFull() {
        if (top == arr.length - 1) {
            return true;
        }

        return false;
    }

    public void push(int data) {
        if (isFull()) {
            System.out.println("Stack is full!");
            return;
        }

        top++;
        arr[top] = data;
    }

    public Integer pop() {
        if (isEmpty()) {
            System.out.println("Stack is empty!");
            return null;
        }

        int data = arr[top];
        top--;

        return data;
    }

    public Integer peek() {
        if (isEmpty()) {
            System.out.println("Stack is empty!");
            return null;
        }

        return arr[top];
    }

    public void printStack() {
        System.out.print("[");
        for (int i = 0; i < top; ) {
            System.out.print(arr[i] + ", ");
            if (++i > top - 1) {
                System.out.print(arr[i]);
            }
        }
        System.out.println("]");
    }
}

 

리스트를 이용한 스택

class Stack {
    ArrayList list;

    Stack() {
        this.list = new ArrayList();
    }

    public boolean isEmpty() {
        if (list.size() == 0) {
            return true;
        }

        return false;
    }

    public void push(int data) {
        list.add(data);
    }

    public Integer pop() {
        if (isEmpty()) {
            System.out.println("Stack is empty!");
            return null;
        }

        int data = (int) list.get(list.size() - 1);
        list.remove(list.size() - 1);
        return data;
    }

    public Integer peek() {
        if (isEmpty()) {
            System.out.println("Stack is empty!");
            return null;
        }

        return (int) list.get(list.size() - 1);
    }

    public void printStack() {
        System.out.println(list);
    }
}