스택(Stack)

스택(Stack)

Stack이란?

한쪽끝에서만 원소를 넣거나 뺄 수 있는 자료구조이다.

Stack의 성질

• 원소의 추가 O(1)
• 원소 제거 O(1)
• 제일 상단의 원소 확인 O(1)
• 제일 상단이 아닌 나머지 원소들의 확인/ 변경이 원칙적으로 불가능

Stack 구현하기

array로 구현한 Stack

class Stack {
    private final int MAX = 100000001;
    private final int[] data = new int[MAX];
    private int pos = 0;

    void push(int item) {
        data[pos++] = item;
    }

    int pop() {
        return data[--pos];
    }

    int peek() {
        return data[pos];
    }

    int size() {
        return pos;
    }

    boolean isEmpty() {
        return pos == 0;
    }
}

LinkedList로 구현한 Stack

class Stack<E> {

    private Node<E> top;

    private static class Node<E> {
        E data;
        Node<E> next;
    }

    Stack() {
    }

    public void push(E item) {
        Node<E> newNode = new Node<>();
        newNode.data = item;
        newNode.next = top;
        top = newNode;
    }

    public E pop() {
        E item = top.data;
        top = top.next;
        return item;
    }

    public E peek() {
        return top.data;
    }

    public int size() {
        if(top ==null) return 0;
        int num = 1;
        Node<E> t = top;
        while (t.next != null) {
            t = t.next;
            num++;
        }
        return num;
    }

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