[Java] 스택, 큐, 데크

목차

• 스택(Stack)
  • 주의할 점
• 큐(Queue)
  • 스택과 큐의 메서드 정리
• 양방향 큐(Deque)
  • ArrayDeque와 LinkedList의 성능 차이
    • LinkedList의 특징
    • ArrayDeque의 특징
    • ArrayDeque와 LinkedList 비교 정리
  • 스택과 큐를 사용할 때는 Deque(ArrayDeque)를 사용하자
• 스택과 큐의 활용
  • 스택의 활용
  • 큐의 활용
• 참고 자료

스택(Stack)

스택의 핵심 키워드는 LIFO(Last In First Out)이다. 마지막(최근)에 들어온 값이
가장 먼저 나가는 특징을 갖는 자료구조이다.

refs) https://www.programiz.com/dsa/stack

해당 그림만으로도 모든 흐름을 알 수 있다. 가장 나중에 들어온 3번이 pop(스택에서 값을 제거하는 연산)을 했을 때, 가장 먼저 나간다!

주의할 점

자바에서는 Stack이라는 클래스가 존재하는데 이는 사용하면 안된다. Stack이라는 클래스는 Vector라는 JDK 1.0 시절에 있던 클래스를 사용하고 있기 때문이다.

Stack에서 사용하는 push는 내부에서 Vector의 addElement를 사용하고 있다.
맨 위, 주석에서 알 수 있듯이 Deque을 구현한 ArrayDeque를 사용할 것을 권장하고 있다.
Stack 및 Vector를 사용하는 것은 성능상 문제도 있으며, 애초에 이들은 현재 사용되지 않는, 하위호환을 위해 존재하는 클래스이기 때문이다.

큐(Queue)

큐의 핵심 키워드는 FIFO(First In First Out)이다. 먼저(최근에) 들어온 값이 먼저 나가는 특징을 가진 자료구조이다. 이러한 특징으로 인해 대기열 시스템을 구현할 때, 큐가 많이 사용된다.

refs) https://kdg-is.tistory.com/232

큐에 데이터를 넣을 때는 Enqueue라는 표현을 쓰기도 하지만 자바에서 제공하는 메서드 이름은 offer()다. 또한 데이터를 제거할 때는 Dequeue라는 표현을 쓰기도 하지만 자바에서 제공하는 메서드 이름은 poll()이다.

대략적인 구조는 다음과 같다. 해당 그림은 인텔리제이에서 인터페이스 및 클래스 구조를 확인하며 그린 구조도이다. 여기서 LinkedList는 Deque와 List를 구현하였음을 알 수 있는데. 선언하는 타입에 따라 Deque의 기능을 사용할 수도 있고, List의 기능을 사용할 수도 있다.

하지만 Queue 자료구조를 구현하는 경우 구현체는 ArrayDeque를 추천한다. 그 이유는 성능상 LinkedList보다 ArrayDeque가 좋기 때문인데 그 이유는 Deque을 소개한 이후 설명하겠다.

스택과 큐의 메서드 정리

• 스택 (push / pop) : 입구와 출구가 같다.
  • ex) 가정 냉장고
• 큐 (offer / poll) : 입구와 출구가 각각 있다.
  • ex) 편의점 음료 냉장고 (편의점 직원이 뒤에서 음료를 넣으면 순서대로 앞으로 내려간다)

스택과 큐의 데이터 추가/삭제는 모두 데이터의 개수에 영향을 받지 않으므로 O(1)이다.

양방향 큐(Deque)

양방향 큐, 이하 데크는 Double Ended Queue로 양쪽에 데이터를 추가할 수도 있고, 삭제할 수도 있있다. 앞서 소개한 스택과 큐와 비교했을 때 매우 유연한 자료구조이다. 여기서 유연하다는건 데이터를 추가/삭제할 때 제약사항이 비교적 덜하다는 뜻이다. 먼저 들어온 값이 먼저 나갈 수도 있고, 나중에 나갈 수도 있다. 반대로 나중에 들어온 값이 나중에 나갈 수도 있고, 먼저 나갈 수도 있다.

데크는 기본적으로 큐에서 변형된 형태이기 때문에 데이터의 추가/삭제 또한 큐의 이름에서 비롯된다. 그림을 통해 데크의 추가/삭제 메서드 이름을 직관적으로 이해할 수 있다. 데크 또한 데이터의 추가/삭제에 데이터 개수에 영향을 받지 않으므로 O(1)이다.

ArrayDeque와 LinkedList의 성능 차이

Deque의 대표적인 구현체는 ArrayDeque와 LinkedList이다. 하지만 앞서 Deque 혹은 Queue를 사용할 때, LinkedList 보다는 ArrayDeque를 사용하는 것이 성능상 더 이점이 많다고 하였다.

refs) https://stackoverflow.com/questions/6163166/why-is-arraydeque-better-than-linkedlist

Linked 자료구조는 더 많은 메모리를 사용한다고 한다. LinkedList와 ArrayDeque가 갖고 있는 필드 타입을 확인해보면 쉽게 이해할 수 있다.

LinkedList의 특징

LinkedList는 기본적으로 Node라는 클래스로 데이터를 관리한다. 즉, Node 인스턴스의 주소 값을 갖는 Pointer로 데이터를 관리하고 있다. 따라서 데이터들은 물리적으로 연속적인 공간에 있지 않을 수 있다. (배열과 달리 메모리에서 각각의 노드가 일렬로 있지 않을 수 있다는 뜻)

LinkedList는 데이터를 추가할 때, 먼저 추가하려는 데이터를 Node 타입으로 감싼다.

또한 각 Node는 다음/이전 노드의 주소, 실제 데이터의 주소 총 세 개의 주소를 갖고 있다.
하나의 Node를 생성할 때, 세 개의 인스턴스가 생성되는 것이기에 그만큼 메모리 상 효율이 떨어진다.

refs) https://stackoverflow.com/questions/6163166/why-is-arraydeque-better-than-linkedlist

또한 데이터를 삭제한다고 할 경우, LinkedList에서 하나의 데이터를 삭제한다면 총 세 개의 인스턴스를 제거해야 한다. 이는 곧, 가비지 컬렉션이 더 많은 작업을 수행해야하는 꼴이 되어버린다.

ArrayDeque의 특징

ArrayDeque는 데이터를 관리할 때, Node 타입이 아닌 Array를 사용한다.

데이터를 추가할 때도, 내부 Array의 head 인덱스에 값을 추가한다. 참고로 ArrayDeque는 원형 큐를 사용하기 때문에 내부 Array를 변경하지 않고, 인덱스 만으로 head와 tail을 결정한다.

refs) https://stackoverflow.com/questions/6163166/why-is-arraydeque-better-than-linkedlist

Array를 사용하기 때문에 각각의 요소를 탐색할 때도 O(1)이 소요되기에 성능 상으로 LinkedList보다 훨씬 좋을 수 밖에 없다. 왜냐하면 LinkedList는 물리적으로 각 노드가 연속적으로 있지 않기 때문에 탐색이 O(N)이기 때문이다.

ArrayDeque와 LinkedList 비교 정리

• ArrayDeque는 Array로 데이터를 관리하며, 원형 큐 형식을 사용하기에 메모리 효율 및 조회가 빠르다 (O(1) - Random Access)
• LinkedList는 Node 타입으로 데이터를 관리하며, 데이터 추가 시 생성해야 하는 인스턴스가 많기에 메모리 효율이 떨어지며, 삭제 시에도 가비지 컬렉션의 일이 많아진다. 또한 데이터를 조회할 때, head 또는 tail에서부터 조회하기 때문에 비교적 느리다 (O(N))

스택과 큐를 사용할 때는 Deque(ArrayDeque)를 사용하자

스택과 큐 관련 문제를 풀거나 해당 특징을 가진 자료구조를 사용할 경우, ArrayDeque를 사용하는 것이 좋다. 앞서 데크 설명에서 알 수 있듯이, 데크는 스택과 큐에 비해 가장 유연한 구조이다. 데크는 스택과 큐에서 제공하는 연산 이름도 제공한다. 무슨 말이냐면 데크를 사용하되, push/pop 그리고 offer/poll을 쓸 수 있다. 물론, 데크라는 자료구조를 사용하는 것은 동일하다. 데크의 push/pop을 쓴다고 해서 데크가 갑자기 큐가 되는 것은 아니다. 논리적으로만 스택/큐의 형태를 가질 수 있는 것이다.

물리적으로는 동일한 ArrayDeque(데크)를 사용한다. 하지만 각각 스택/큐라는 논리적인 데이터 구조로 활용할 수 있도록, 데크는 다양한 메서드를 지원한다.

ArrayDeque의 push 메서드를 자세히 보면 addFirst() 라는 메서드를 사용하고 있는데, 이는 offerFirst()에서 사용하는 메서드이기도 하다. 즉, push/pop, offer/poll 모두 Deque가 제공하는 기능을 사용한다.

스택과 큐의 활용

스택의 활용

스택은 먼저 들어온 값이 먼저 나간다. 웹 브라우저에서 뒤로가기 혹은 컨트롤 + Z를 통해 되돌리기를 할 경우, 우리는 가장 최근에 방문한 사이트 혹은 했던 작업으로 돌아간다. 이것이 스택이 활용되는 주된 예시다.

public void visitPage(String url) {  
    if (currentPage != null) { // history는 방문 기록임.  
        history.push(currentPage);
        // 첫 번째 방문에는 history에 쌓이지 않으며, 두 번째로 다른 사이트를 방문했을 때            첫 번째에 방문했던 값이 history로 추가됨  
    }  
    currentPage = url;  
    System.out.println("방문 : " + url);  
}

public String goBack() {  
    if (!history.isEmpty()) {  
        currentPage = history.pop();
        // 뒤로가기를 눌렀을 때,
        // 히스토리에서 가장 최근에 추가된 사이트가 최신 사이트가 됨.  
        System.out.println("뒤로가기 : " + currentPage);  
        return currentPage;  
    }  
    return null;  
}

큐의 활용

큐는 먼저 들어온 데이터가 먼저 나간다. 이는 작업 대기열을 만드는 데에 큐가 활용되는 이유이다.
서버에서 리소스를 많이 활용하는 작업을 새벽 시간대(사용자가 비교적 적은 시간대)로 미루고자 할 경우, 대기열에 작업을 추가할 수 있을 것이다. 그러면 새벽 시간대가 됐을 때, 대기열에 있는 작업들을 순서대로 실행할 것이며, 이때는 먼저 들어온 작업부터 진행될 것이다.

이는 큐의 형태를 떠올려보면 쉽게 이해할 수 있으므로 따로 그림은 그리지 않고, 구현된 코드만 첨부하겠다.

public void addTask(Task task) {  
    tasks.offer(task);  
}

• 작업이 큐에 추가한다.(offer)

public void processNextTask() {  
    if (!tasks.isEmpty()) {  
        Task task = tasks.poll();  
        task.execute();  
    }  
}

• 큐에 있는 작업이 실행될 때, 먼저 들어온 작업부터 꺼내어(poll) 실행한다.

참고 자료

1. 인프런 김영한 자바 중급 2편