학습 목표

• Stack 개념과 ADT
• Stack 구현
  • Array
  • LinkedList
  • Java.util.Stack
• 결론

Stack 개념과 ADT

스택이란 어떠한 데이터들을 순차적으로 저장할 수 있으며 입구와 출구가 하나밖에 존재하지 않는 자료구조다.

스택의 특징

• LIFO(Last-In-First-Out)
• 입구와 출구가 한 곳밖에 없기에 마지막으로 들어간 자료가 가장 먼저 나온다.
  
  접시를 한 곳에 쌓아두었을 때 맨위에 접시부터 꺼낼 수 박에 없는 것을 생각하면 된다.
  데이터의 위치를 따로 지정할 수 없기에 데이터의 연산은 push(넣기)와 pop(꺼내기)밖에 존재하지 않는다.
• top을 이용하여 스택의 위치를 파악한다.

Array Stack 구현

public class arrStack {
    static class Stack {
        private int top;
        private int stackSize;
        private int stackArr[];

        public Stack(int stackSize) {
            top = -1;
            stackArr = new int[stackSize];
            this.stackSize = stackSize;
        }

        public void push(int data) {
            stackArr[++top] = data;
        }

        public int pop(){
            if (top == -1) {
                throw new ArrayIndexOutOfBoundsException();
            }
            return stackArr[top--];
        }

        public int peek() {
            if (top == -1) {
                throw new ArrayIndexOutOfBoundsException();
            }
            return stackArr[top];
        }

        public void printStack() {
            System.out.println("stack list");
            for (int i = top; i >= 0; --i) {
                System.out.println(stackArr[i]);
            }
        }

    }
    public static void main(String[] args) {
        Stack st = new Stack(100);
        st.push(1);
        st.push(2);
        st.push(3);
        st.push(4);
        st.push(5);
        st.printStack(); // 5 4 3 2 1
        System.out.println("peek: " + st.peek()); // peek : 5
        st.pop();
        st.printStack(); // 4 3 2 1
        st.pop();
        st.pop();
        st.pop();
        st.pop();
        st.printStack(); // 없음 
    }
}

배열을 통한 스택 구현의 경우 top의 초기값에 따라 top 연산이 달라진다.
-1로 잡으면 스택의 top은 데이터의 위치와 동일하고, 0으로 잡으면 다음 데이터의 위치를 가리키게 된다.

Stack Singly Linked List 구현

public class implementStack {
    static class Stack<T> {
        static class Node<T> {
            private T data;
            private Node<T> next;

            public Node(T data) {
                this.data = data;
            }
        }

        private Node<T> top;

        public void push(T data) {
            Node<T> node = new Node<>(data);
            node.next = top;
            top = node;
        }

        public T pop() {
            if (top == null) {
                throw new EmptyStackException();
            }
            T data = top.data;
            top = top.next;
            return data;
        }

        public T peek(){
            if (top == null) {
                throw new EmptyStackException();
            }
            return top.data;
        }

        boolean isEmpty(){
            return top == null;
        }
    }
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.push(1);
        stack.push(2);
        System.out.println(stack.peek()); // 2
        System.out.println(stack.pop()); // 2
        System.out.println(stack.peek()); // 1
        System.out.println(stack.pop()); // 1
        System.out.println(stack.isEmpty()); // true
    }
}

리스트에 따른 스택 구현은 처음 생성 된 노드의 top

결론

Stack의 특성상 마지막 데이터를 쉽게 빼낼 수 있다.
마지막 기록, 최근 기록 등 데이터를 저장하고 제거할 경우만 사용한다.
조회(검색)은 다른 자료구조에 비해 느려 데이터 조회가 필요할 경우 사용하지 않는다.
--> 이로 인해 연결 리스트로 스택 구현 시 연결 리스트의 단점은 상관이 없어짐.

결국 링크드스택의 단점은 사실상 없게 되며 연속된 메모리를 할당하는 배열보다 유동적으로 메모리를 할당할 수 있는 리스트를 통한 스택 구현이 보다 효율적이다.