[Java] Stack & Queue

리스트

1. ArrayList
2. LinkedList
3. Vector
4. Stack

✍️ Stack

✏️ Stack 이란?

• Stack 은 마지막에 저장한 데이터를 가장 먼저 꺼내게 되는 LIFO(Last In First Out) 구조로 되어 있습니다.
• Stack 은 순차적으로 데이터를 추가하고 삭제하므로 ArrayList 와 같은 배열 기반의 컬렉션 클래스가 적합합니다.
  
  

✏️ 구현

import java.util.Stack;

class Main {
    public static void main(String[] args) {
        Stack stack = new Stack<>();

        stack.push(1);
        stack.push(2);
        stack.push(3);

        while (!stack.empty()) {
            System.out.println(stack.pop());
        }
    }
}

// 실행 결과
3
2
1

✏️ 주요 메서드

🎨  1. boolean empty()

• Stack이 비어있는지 알려줍니다.

🎨  2. Object peek()

• Stack의 맨 위에 저장된 객체를 반환합니다.
• pop() 과 달리 Stack에서 객체를 꺼내지는 않습니다.
• Stack이 비어 있을 때는 EmptyStackException 이 발생합니다.

🎨  3. Object pop()

• Stack의 맨 위에 저장된 객체를 꺼냅니다.
• Stack이 비어 있을 때는 EmptyStackException 이 발생합니다.

🎨  4. Object push(Object item)

• Stack에 객체(item)을 저장합니다.

🎨  5. int search(Object o)

• Stack에서 주어진 객체(o)를 찾아서 그 위치를 반환합니다. 못 찾으면 -1 을 반환합니다.
• 배열과 달리 위치는 0이 아닌 1부터 시작합니다.
  
  
  

✍️ Queue

✏️ Queue 란?

• Queue 는 처음에 저장한 데이터를 가장 먼저 꺼내게 되는 FIFO(First In First Out) 구조로 되어 있습니다.
• Queue 는 데이터를 꺼낼 때 항상 첫 번째 저장된 데이터를 삭제하므로, 데이터의 추가/삭제가 쉬운 LinkedList 로 구현하는 것이 적합합니다.
  
  

✏️ 구현

import java.util.LinkedList;
import java.util.Queue;

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

        queue.offer(1);
        queue.offer(2);
        queue.offer(3);

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

// 실행 결과
1
2
3

✏️ 주요 메서드

🎨  1. boolean add(Object o)

• 지정된 객체를 Queue에 추가합니다.
• 추가에 성공하면 true를 반환합니다.
• 저장공간이 부족하면 IllegalStateException 이 발생합니다.

🎨  2. Object remove()

• Queue에서 객체를 꺼내 반환합니다.
• Queue이 비어 있을 때는 NoSuchElementException 이 발생합니다.

🎨  3. Object element()

• 삭제 없이 요소를 읽어옵니다.
• peek() 와 달리 Queue가 비어있으면 NoSuchElementException 이 발생합니다.

🎨  4. boolean offer(Object o)

• Queue에 객체를 저장합니다.
• 저장에 성공하면 true, 실패하면 false 를 반환합니다.

🎨  5. Object poll()

• Queue에서 객체를 꺼내서 반환합니다.
• 비어있으면 null 을 반환합니다.

🎨  6. Object peek()

• 삭제없이 요소를 읽어옵니다.
• 비어있으면 null 을 반환합니다.
  
  

✏️ PriorityQueue

• 저장된 순서에 관계없이 우선순위(priority)가 높은 것부터 꺼냅니다.
• null 을 저장할 수 없으며, null 을 저장하면 NullPointerException 이 발생합니다.
• PriorityQueue 는 저장공간으로 배열을 사요ㅕㅇ하며, 각 요소를 힙(Heap) 자료구조 형태로 저장합니다.
• 우선순위는 숫자가 작을수록 높습니다.
• 1️⃣ PriorityQueue 가 내부적으로 가지고 있는 배열은 저장한 순서와 다르게 저장됩니다. (이는 자료구조 Heap의 형태로 저장되어서)

  ===== 오름차순 정렬 =====

  import java.util.PriorityQueue;
  import java.util.Queue;
  
  class Main {
  
      public static void main(String[] args) {
          PriorityQueue<Integer> pq = new PriorityQueue<>();
  
          pq.offer(3);
          pq.offer(2);
          pq.offer(1);
          pq.offer(5);
          pq.offer(4);
  
          System.out.println("PriorityQueue: " + pq); // --- 1️⃣
          
          while (!pq.isEmpty()) {
              System.out.println(pq.poll());
          }
      }
  }
  
  // 실행 결과
  PriorityQueue: [1, 3, 2, 5, 4]
  1
  2
  3
  4
  5

  ===== 반대로 정렬 =====

  import java.util.Collections;
  import java.util.PriorityQueue;
  
  class Main {
  
      public static void main(String[] args) {
          PriorityQueue<Integer> rpq = new PriorityQueue<>(Collections.reverseOrder());
  
          rpq.offer(4);
          rpq.offer(6);
          rpq.offer(5);
          rpq.offer(1);
  
          System.out.println("ReversePriorityQueue: " + rpq);
          
          while (!rpq.isEmpty()) {
              System.out.println(rpq.poll());
          }
      }
  }
  
  // 실행 결과
  ReversePriorityQueue: [6, 4, 5, 1]
  6
  5
  4
  1

✏️ Deque

• 한 쪽에서 추가하고 다른 한쪽에서 삭제하는 Queue 와 달리 양쪽 끝에서 추가/삭제가 가능합니다.
• Deque 은 Stack 과 Queue 를 하나로 합쳐 놓은 것과 같으며, Stack으로 사용할 수 있고 Queue 로 사용할 수 있습니다.