개발 학습 실습실

이 사이트의 실습은 자바스크립트를 켜야 움직입니다. 아래는 같은 내용을 글로 적은 것입니다.

공부 › Java › 컬렉션

스택·큐·우선순위 큐

넣은 순서와 꺼내는 순서

같은 숫자 다섯 개를 같은 순서로 넣어도, 자료구조에 따라 꺼내지는 순서가 다릅니다. 스택은 나중에 넣은 것부터, 큐는 먼저 넣은 것부터, 우선순위 큐는 가장 작은 것부터 나옵니다.

실행으로 대조 · JDK 21의 실제 ArrayDeque·PriorityQueue와 대조

이 실습에 나오는 개념

스택, 큐, 덱
스택은 나중에 넣은 것을 먼저 꺼내는(LIFO) 구조, 큐는 먼저 넣은 것을 먼저 꺼내는(FIFO) 구조, 덱은 양쪽 끝에서 넣고 뺄 수 있는 구조다. 자바에서는 스택과 큐 모두 ArrayDeque로 구현하는 것이 권장된다.
힙과 우선순위 큐
힙은 부모 노드가 자식 노드보다 항상 작거나 같은(최소 힙), 또는 크거나 같은(최대 힙) 완전 이진 트리다. 가장 작은(큰) 값을 O(1)에 확인하고 O(log n)에 꺼낼 수 있어 우선순위 큐를 구현하는 데 쓰인다. 자바의 PriorityQueue가 힙으로 구현되어 있다. JVM의 메모리 영역인 힙과는 이름만 같다.
시간 복잡도(Big-O)
입력 크기 n이 커질 때 알고리즘의 연산 횟수가 얼마나 빠르게 늘어나는지를 나타내는 표기다. O(1)은 크기와 무관하게 일정, O(log n)은 크기가 두 배가 되어도 한 단계만 늘어남, O(n)은 크기에 비례, O(n²)은 크기의 제곱에 비례함을 뜻한다. 데이터가 많아질 때 어떤 방식이 버티는지 판단하는 기준이다.

이렇게 바꿔 보세요

처음 설정으로 실행하면

  1. offer(5): 배열 맨 끝에 넣은 뒤, 부모보다 작으면 자리를 바꾸며 위로 올라갑니다. 첫 값이라 맨 위에 그대로 놓입니다.
  2. offer(2): 배열 맨 끝에 넣은 뒤, 부모보다 작으면 자리를 바꾸며 위로 올라갑니다. 1번 올라가 맨 위(가장 작은 값의 자리)에 도착했습니다.
  3. offer(8): 배열 맨 끝에 넣은 뒤, 부모보다 작으면 자리를 바꾸며 위로 올라갑니다. 부모보다 작지 않아 그 자리에 머뭅니다.
  4. offer(1): 배열 맨 끝에 넣은 뒤, 부모보다 작으면 자리를 바꾸며 위로 올라갑니다. 2번 올라가 맨 위(가장 작은 값의 자리)에 도착했습니다.
  5. offer(9): 배열 맨 끝에 넣은 뒤, 부모보다 작으면 자리를 바꾸며 위로 올라갑니다. 부모보다 작지 않아 그 자리에 머뭅니다.
  6. poll(): 맨 위의 가장 작은 값(1)을 꺼냅니다. 빈 맨 위에 배열의 마지막 값을 올린 뒤, 두 자식 중 작은 쪽과 자리를 바꾸며 내려갑니다(2번 내려감).
  7. poll(): 맨 위의 가장 작은 값(2)을 꺼냅니다. 빈 맨 위에 배열의 마지막 값을 올린 뒤, 두 자식 중 작은 쪽과 자리를 바꾸며 내려갑니다(1번 내려감).
  8. poll(): 맨 위의 가장 작은 값(5)을 꺼냅니다. 남은 값이 있으면 배열의 마지막 값이 빈 맨 위로 올라옵니다. 이번에는 자리를 바꿀 일이 없었습니다.
  9. poll(): 맨 위의 가장 작은 값(8)을 꺼냅니다. 남은 값이 있으면 배열의 마지막 값이 빈 맨 위로 올라옵니다. 이번에는 자리를 바꿀 일이 없었습니다.
  10. poll(): 맨 위의 가장 작은 값(9)을 꺼냅니다. 남은 값이 있으면 배열의 마지막 값이 빈 맨 위로 올라옵니다. 이번에는 자리를 바꿀 일이 없었습니다.

실행 결과

코드

PriorityQueue<Integer> pq = new PriorityQueue<>();   // 작은 값이 먼저
for (int x : List.of(5, 2, 8, 1, 9)) pq.offer(x);

while (!pq.isEmpty()) System.out.print(pq.poll() + " ");

이 모형의 전제

꺼낸 순서와 우선순위 큐 내부 배열의 변화는 이 PC의 JDK 21에서 실제 ArrayDeque와 PriorityQueue를 실행해 대조했습니다(내부 배열은 넣을 때마다, 꺼낼 때마다 모두 일치). PriorityQueue는 기본적으로 작은 값이 먼저 나오며, Comparator를 주면 기준을 바꿀 수 있습니다.

앞 실습: Set과 Map의 종류 · 다음 실습: 순회 중 삭제

이 실습에 나오는 개념

이 실습에서 보는 것

설정

코드


      
    


    

      
그림

      

      

    


    

      

      

      

    


  


  

    

      
실행 비교

      

      

    

    

      
이렇게 바꿔 보세요