스택(Stack) & 큐(Queue) & 덱(Deque)

스택(Stack)

스택은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조(LIFO - Last In First Out)으로 되어 있다. 

자료를 넣는 것을 '밀어넣는다' 하여 푸쉬(push)라고 하고 반대로 넣어둔 자료를 꺼내는 것을 팝(pop)이라고 하는데, 이때 꺼내지는 자료는 가장 최근에 푸쉬한 자료부터 나오게 된다.

이처럼 나중에 넣은 값이 먼저 나오는 것을 LIFO 구조라고 한다.

스택은 컴퓨터에서 포인터라고 하는 자료의 위치 표시자와 넣고 빼는 명령어를 사용해서 스택을 이용한다.

주로 함수를 호출할 때 인수의 전달 등에 이용되며 대표적인 예시는 아래와 같다.

• 웹 브라우저 방문 기록
• 후위 표기법 계산
• 실행 취소(Undo)
• 역순 문자열 생성

Java에서 Stack은 Vector를 상속하여 만들어졌다. 따라서 Stack 역시 Synchronized 키워드가 붙어있다.

addElement(), removeElementAt(), elementAt, lastIndexOf() 같은 메소드들은 Vector가 가지고 있는 메소드를 사용한 것이다.

public class Stack<E> extends Vector<E> {
    public E push(E item) {
        addElement(item);
        return item;
    }
    
    public synchronized E pop() { //요소 제거
        E       obj;
        int     len = size();

        obj = peek();
        removeElementAt(len - 1);

        return obj;
    }
    
    public synchronized E peek() { //요소 반환
        int     len = size();

        if (len == 0)
            throw new EmptyStackException();
        return elementAt(len - 1);
    }
    
    public synchronized int search(Object o) {
        int i = lastIndexOf(o);

        if (i >= 0) {
            return size() - i;
        }
        return -1;
    }
}

코드에서 알 수 있듯이 Stack 은 리스트 구조에서 맨 마지막 요소에서만 삽입/삭제가 일어나는 형태이다.

---

큐(Queue)

큐(Queue)는 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out)구조로 저장하는 형식을 말한다.

영어 단어 그 자체도 '대기줄'을 뜻한다.

큐에서 삽입/삭제는 '큐'라는 것을 강조하기 위해 Enqueue, Dequeue를 사용한다.

(이외에도 put/get, offer/poll, insert/delete 등이 있지만 의미만 알 수 있으면 된다.)

또한, 스택과 다르게 앞과 뒤를 구분하는 Front와 Rear가 있다.

Front는 요소를 꺼내오는 방향이고, Rear는 요소는 집어넣는 방향이다.

 

집어넣는 순서와 꺼내오는 순서가 동일해야 하는 상황에서 주로 사용한다. (선착순, 버퍼 등)

 

Java에서 큐는 인터페이스다. 그만큼 순서대로 처리해야 하는 상황이 많고, 그에 따른 자료구조도 많기 때문에 이를 추상화시킨 것이다.

대표적인 구현클래스는 LinkedList, PriorityQueue 등이 있다.

정확히는 LinkedList의 경우 확장성을 위해 Queue 인터페이스를 상속하는 Deque 인터페이스를 상속하고 있다. (자세한 건 Deque에서..)

PriorityQueue의 경우 Queue 인터페이스를 상속하는 AbstractQueue라는 추상화 클래스를 상속하고 있다.

public interface Queue<E> extends Collection<E> {
    //add, remove, element는 예외 발생 시 Exception을 반환한다.
    //offer, poll, peek는 예외 발생 시 false를 반환한다.
    //따라서 offer, poll, peek를 사용하는 것이 일반적으로 바람직하다.
    boolean add(E e);
    boolean offer(E e);
    E remove();
    E poll();
    E element();
    E peek();
}

---

덱(Deque)

덱(Deque)은 스택의 후입선출과 큐의 선입선출을 혼합해서 만든 자료구조이다.

따라서, 양방향에서 요소를 삽입/삭제 할 수 있다.

Deque을 통해 스택을 구현할 수도, 큐를 구현할 수도 있기 때문에 많이 사용한다.

하지만, 주어진 상황이 굳이 양방향 삽입/삭제가 필요한 것이 아니라면, 코드를 가볍게하기 위해 필요한 것을 선택하는 것이 좋다.

('디큐'라고 발음하는 분들도 계시지만, 큐의 삭제(Dequeue)와 구분하기 위해서는 덱 혹은 데크가 맞는것 같다.)

 

Java에서 Deque 역시 인터페이스이다. 앞/뒤에서 요소를 삽입/삭제할 수 있도록 정의되어 있다.

위에서 언급했던 것처럼 LinkedList는 Deque를 구현했기 때문에, 다양한 기능을 사용할 수 있다.

 

public interface Deque<E> extends Queue<E> {
    void addFirst(E e);
    void addLast(E e);
    boolean offerFirst(E e);
    boolean offerLast(E e);
    E removeFirst();
    E removeLast();
    E pollFirst();
    E pollLast();
    E getFirst();
    E getLast();
    E peekFirst();
    E peekLast();
    boolean removeFirstOccurrence(Object o); //앞쪽부터 탐색해서 o 객체 remove
    boolean removeLastOccurrence(Object o); //뒷쪽부터 탐색해서 o 객체 remove
    
    // *** Queue methods ***

    boolean add(E e);
    boolean offer(E e);
    E remove();
    E poll();
    E element();
    E peek();
    boolean addAll(Collection<? extends E> c);

    // *** Stack methods ***

    void push(E e);
    E pop();

    // *** Collection methods ***

    boolean remove(Object o);
    boolean contains(Object o);
    int size();
    Iterator<E> iterator();
    Iterator<E> descendingIterator();
}

---

Ref.

https://cotak.tistory.com/69

https://jud00.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%8A%A4%ED%83%9DStack%EA%B3%BC-%ED%81%90Queue%EC%97%90-%EB%8C%80%ED%95%B4%EC%84%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EC%9E%90