Stack, Queue, Deque

스택(Stack)

박스 쌓기에 비유할 수 있다.
선입후출(FILO) 구조 또는 후입선출 구조

스택의 메서드

큐

대기 줄에 비유할 수 있다.
선입선출(FIFO) 구조

큐의 매서드

간단한 스택과 큐 구현

public static void main(String[] args) { 
    Stack st = new Stack(); 
    Queue q = new LinkedList();

    st.push("0");
    st.push("1");
    st.push("2");
    q.offer("0");
    q.offer("1");
    q.offer("2");

    while(!st.isEmpty()) {
        System.out.print(st.pop());
    }

    while(!q.isEmpty()) {
        System.out.print(q.poll());
    }
}

실행결과 : 210 012

Deque(Double-Ended Queue)

Deque는 양쪽 끝에서 추가와 삭제가 가능하다.

개념: 덱(Deque)은 양쪽 끝에서 원소를 추가하거나 삭제할 수 있는 자료 구조
인터페이스: Java에서는 Deque를 인터페이스로 제공하며, 다양한 구현체가 있습니다. 주요 메서드로는 addFirst(), addLast(), removeFirst(), removeLast(), getFirst(), getLast() 등이 있습니다.
기능: 스택(Stack)과 큐(Queue)의 모든 기능을 지원, 양쪽 끝에서의 원소 추가/삭제가 O(1) 시간 복잡도로 가능
구현체: Java에서는 ArrayDeque 외에도 LinkedList도 Deque 인터페이스를 구현하여 사용할 수 있다.

Stack VS ArrayDeque

자바로 스택을 구현할 때에는 주로 ArrayDeque을 이용한다.

Stack이 상속하는 Vector의 문제점

Stack이 상속하는 Vector의 가장 큰 문제점은 주요 메서드들이 각각 동기화를 진행한다는 것이다.

// add, addElement, get 등 주요 public 메서드들이 synchronized 키워드를 달고 있다.
public synchronized boolean add(E e) {
    modCount++;
    add(e, elementData, elementCount);
    return true;
}

Vector<Integer> vector = new Vector<>();
for (int i = 0; i < 100_000_000; i++) {
    vector.add(i);
} // 3484ms

ArrayList<Integer> arrayList = new ArrayList<>();
for (int i = 0; i < 100_000_000; i++) {
    arrayList.add(i);
} // 2319ms

거의 1.5배의 속도 차이가 발생하며 이는 vector의 동기화 작업 때문일 것으로 예상된다.
Stack은 Vector의 메서드를 그대로 사용하며 동기화 관련 문제가 그대로 발생한다.

ArrayDeque는 불필요한 동기화 없이 offerLast 메서드와 pollLast 메서드로 Stack의 기능을 완벽히 대체할 수 있다.

Queue VS ArrayDeque

Queue(LinkedList)	ArrayDeque
이중 연결 리스트로 구현	크기가 조정 가능한 배열로 구현
각 요소는 데이터와 두 개의 포인터(이전 요소와 다음 요소를 가리킴)를 포함하므로, 추가 메모리 사용	배열을 사용하므로, LinkedList 보다 메모리 오버헤드가 적다. 하지만 배열이 꽉 차면 새로운 배열을 할당하고 기존 요소를 복사해야 한다.
리스트의 양 끝에서 요소를 삽입하거나 삭제하는 작업이 빠르다(O(1)). 중간 요소의 삽입/삭제도 포인터 조작만으로 처리되므로 효율적이다.	배열의 양 끝에서 요소를 삽입하거나 삭제하는 작업이 빠르다(O(1)). 단, 배열 크기를 조정하는 경우 성능이 저하될 수 있다.
특정 인덱스의 요소에 접근하는 시간이 O(n)으로, 리스트의 크기가 커질수록 성능이 저하된다.	특정 인덱스의 요소에 접근하는 시간이 O(1)이다.

ArrayList vs ArrayDeque vs LinkedList??

인덱스로 데이터에 접근하고 끝에 삽입, 삭제만 할 경우에는 ArrayList를 사용
stack, queue, 혹은 deque로 ArrayDeque를 사용
리스트를 순회할때 삽입, 삭제하거나 O(1)인 최악의 경우에 마지막에 삽입시 LinkedList를 사용