Stack

Stack의 구조는 수직으로 쌓인 물건의 더미를 생각할 수 있다. 그러므로 물체를 걷어낼 때 마지막 추가된 것이 가장 먼저 제거될 것이다. 접시나 책이 쌓여있는 것을 상상해 보면 이해할 수 있을 것이다.

이러한 구조는 LIFO 구조이다. LIFO가 무엇이냐면 후입(Last In) 선출(First Out)을 의미한다. Java의 메모리 구조에서 스택 메모리에도 스택 프레임이 push 되거나 pop 된다. 또한 함수의 메모리 호출 순서도 stack 구조와 동일하다.

간단한 예시로 브라우저가 존재한다고 하자. 웹 브라우저는 아래와 같이 방문 순서를 저장하고 있다.

naver부터 순차적으로 접근했다면 스택에는 위와 같이 브라우저의 url이 담겨있을 것이다. 그리고 뒤로가기를 누르면 최상단에 존재하는 likedin 부터 순차적으로 스택에서 제거될 것이다.

스택의 구현

1. Array

스택을 배열로 구현하면 구현이 쉽다는 장점이 있다. 그러므로 스택의 기능(연산)들을 쉽게 구현할 수 있다. 단점으로는 배열 사용으로 인한 고정된 크기이다.

public class ArrayStack {
    int[] arr;
    int topOfStack; // 스택 상단을 -1로 설정. 스택에 요소가 없다면 맨 위가 -1이 된다는 의미이다.

    // 스택 생성시 초기화, 공간 복잡도 O(N) 발생
    public ArrayStack(int size) {
        this.arr = new int[size]; // 배열 초기화 --> O(1)
        this.topOfStack = -1;     // 변수 초기화 --> O(1)
        System.out.println("create stack size of: " + size);
    }

    public boolean isEmpty() {
        return topOfStack == -1;
    }

    public boolean isFull() {
        return topOfStack == arr.length - 1;
    }

    public void push(int value) {
        if (isFull()) {
            System.out.println("Stack is Full");
        } else {
            this.arr[++topOfStack] = value;
            System.out.println("successfully inserted");
        }
    }

    public int pop() {
        if (isEmpty()) {
            System.out.println("Stack is empty");
            return topOfStack; // - 1
        }
        return this.arr[topOfStack--];
    }

    public int peek() {
        if (isEmpty()) {
            System.out.println("Stack is empty");
            return topOfStack; // - 1
        }
        return this.arr[topOfStack];
    }

    public void deleteStack() {
        this.arr = null;
    }
}

1. Linked List

연결리스트로 스택을 생성하면 크기가 가변적이다. 즉, 원하는 만큼 요소를 삽입할 수 있다. 단점으로는 구현이 배열보다는 까다롭다.

public class LinkedListStack {

    LinkedList linkedList;

    public LinkedListStack() {
        this.linkedList = new LinkedList();
    }

    // push : 빈 노드를 생성하고 값을 할당한다음 헤드를 변경한다.
    public void push(int value) {
        linkedList.add(0, value);
    }

    public boolean isEmpty() {
        return linkedList.getHead() == null;
    }

    // pop : Head의 포인트를 다음 다음 노드로 변경한다. 연결이 해제된 노드는 가비지의 수집 대상이 되어 메모리에서 삭제된다.
    public int pop() {
        int result = -1;
        if (isEmpty()) {
            System.out.println("Stack is Empty");
        } else {
            result = linkedList.getHead().data;
            linkedList.removeFirst();
        }
        return result;
    }

    public int peek() {
        if (isEmpty()) {
            System.out.println("Stack is Empty");
            return -1;
        } else {
            return linkedList.getHead().data;
    }
}

Java에서 제공하는 Stack

import java.util.Stack;

java는 Stack 클래스를 제공하고 있다.

• Obejct push(Object Item) : stack에 Object(item)을 저장

  • O(1)

• Object pop() : 스택 최상단의 객체를 꺼내고 반환한다.

  • O(1)

• Object peek() : 스택 최상단의 객체를 반환하지만 꺼내지는 않는다.

  • O(1)

• boolean empty() : 스택이 비어있는지 확인한다.

  • O(1)

• int size() : 스택의 크기를 반환한다.

• int search(Object o) : 찾는 객체(o)를 찾아서 위치(index)를 반환한다.

  • 없으면 -1을 반환하고, 배열과 달리 index는 1부터 시작한다.

  • O(N)

Stack 대신 Deque?

A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to this class. https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/util/Stack.html

java 공식 문서를 보면 Stack 보다는 Dequeue를 권장한다.

Deque(덱)은 양방향으로 삽입하고 삭제가 가능한 queue 자료구조로 이해하면 된다.

dequeue를 권장하는 이유는 Stack은 Vector를 상속받아 구현되었는데 스택이 단점을 그대로 가지고 있다. (메서드들이 동기화를 진행한다는 문제.. etc)

결론은 Stack 대신 ArrayDeque, 단일 스레드에서도 ArrayDeque 멀티 스레드에서 스택을 사용한다면 LinkedBlockingDeque 또는 ConcurrentLinkedDeque의 사용을 권장한다.

LinkedBlockingDeque는 한 번에 단일 스레드에서만 데이터 접근이 가능하도록 하며

ConcurrentLinkedDeque는 여러 스레드에서 접근이 가능하나 효율적인 lock-free 알고리즘을 사용해 우선순위가 낮은 스레드가 락을 점유하는 상황이나 데드락에 걸리는 상황을 막아준다.