[Java] 스택, 큐, 우선순위 큐, 덱 이란?

 

남궁성님의 Java의 정석(3rd Edition)을 보고 정리한 글입니다.

 

스택과 큐 LIFO, FIFO 구조를 가진다. 스택과 큐를 알아보기 전에 LIFO, FIFO 구조에 대해서 알아보자.

 

1. LIFO 구조와 FIFO 구조

---

LIFO 구조는 입구가 하나인 구조로, 가장 마지막에 들어간 요소가 가장 먼저 나오는 후입선출 구조이다.

FIFO 구조는 입구와 출구가 서로 다른 구조로, 가장 먼저 들어간 요소가 가장 먼저 나오는 구조이다.  

LIFO 구조와 FIFO 구조

 

2. Stack이란?

---

• LIFO(Last In First Out) 구조(가장 마지막으로 들어간 요소가 가장 먼저 나온다.)
• Java에서 클래스로 구현되어 있음
• 스택 활용 예시
  • 수식계산, 괄호검사, 웹브라우저 뒤로/앞으로
• Java에서는 Stack 클래스를 사용하는 것을 권장하지 않음.(ArrayDeque를 사용 권장)
  • Vector를 확장하고 있기 때문에 동기화 처리가 되어 있는데, 멀티쓰레드 환경이 아니라면 lock을 거는 작업 때문에 오베헤드가 발생한다.
  • 스택은 LIFO 구조인데 Vector를 확장했기 때문에 데이터를 중간에서 삽입, 삭제가 가능 (자바 설계 실수)

 

자바 Stack 클래스

 

 

3. Queue란?

---

• FIFO(First In First Out) 구조(가장 먼저 들어간 요소가 가장 먼저 나온다.)
• 큐 활용 예시
  • 최근사용문서, 인쇄작업 대기 목록
• Java에서 인터페이스로 구현되어 있음
  • Queue 인터페이스로 구현되어 있는 클래스

자바 Queue 인터페이스의 구현체

 

4. Stack, Queue 예제

스택과 큐에  0 -> 1 -> 2 순서로 데이터를 삽입한 후 데이터를 하나씩 꺼내는 코드이다.

public class Main {
    public static void main(String[] args) {
        Stack stack = new Stack();
        Queue queue = new LinkedList();

        for (int i = 0; i < 3; i++) {
            stack.push(i);
            queue.offer(i);
        }

        System.out.println("== Stack == ");
        while (!stack.isEmpty()) {
            System.out.println(stack.pop());
        }

        System.out.println("== Queue ==");
        while (!queue.isEmpty()) {
            System.out.println(queue.poll());
        }
    }
}

실행결과
== Stack == 
2
1
0
== Queue ==
0
1
2

스택의 경우 후입선출 구조로 2 -> 1 -> 0 순서로 데이터를 꺼낸다.

큐의 경우 선입선출 구조로 0 -> 1 -> 2 순서로 데이터가 꺼내지는 것을 확인할 수 있다. 

 

 

5. PriorityQueue(우선순위 큐)

---

• Queue 인터페이스의 구현체 중 하나
• 저장한 순서에 관계없이 우선순위가 높은 것부터 꺼냄.
  • 우선순위를 사용하기 때문에 Comparable를 구현해야 한다.
• null 저장할 수 없음
• 가장 큰 값이나 가장 작은 값을 빠르게 찾을 수 있음. ⇒ Heap 자료구조의 형태로 저장하기 때문
  • 힙은 완전이진트리 구조로 모든 노드에 저장된 값(우선순위)들은 자식 노드들의 값(우선순위)보다 크거나 같다.

 

PriorityQueue 예제

public class Main {
    public static void main(String[] args) {
        Queue pq = new PriorityQueue();
        pq.offer(3);
        pq.offer(1);
        pq.offer(5);
        pq.offer(2);
        pq.offer(4);
        // pq.offer(null) // 에러 
        
        // 힙이라는 자료구조 형태로 저장해서 pq가 내부적으로 가지고 있는 배열 내용의 출력
        System.out.println(pq); 

        while (!pq.isEmpty())
            System.out.println(pq.poll());
    }
}

출력결과
[1, 2, 5, 3, 4]    => 완전이진트리 구조로 출력
1
2
3
4
5

저장순서는 3 -> 1 -> 5 -> 2 -> 4 인데 출력결과는 1 -> 2 -> 3 -> 4 -> 5 이다.

 

 

6. Deque(덱)

---

• Queue 변형으로 양쪽 끝에서 추가, 삭제가 가능하다.
• 구현체로 ArrayDeque, LinkedList 등이 있음

  

Deque 예제

public class Main {
    public static void main(String[] args) {
        Deque deque = new ArrayDeque();

        deque.offerLast(3);  // [3]
        deque.offerLast(10);  // [3, 10]
        deque.offerFirst(2); // [2, 3, 10]

        System.out.println(deque);

        System.out.println(deque.pollLast());

        System.out.println(deque.pollFirst());
    }
}

실행결과
[2, 3, 10]
10
2

offerLast, offerFirst  메서드로 양쪽 끝에 데이터를 삽입할 수 있고, pollLast, pollFirst 메서드로 양쪽 끝에서 데이터를 꺼낼 수 있다.