스택과 큐

ADT (abstract data type)

• 추상자료형

• 개념적으로 어떤 동작이 있는지만 정의

• 구현에 대해서는 다루지 않음

DS(data structure)

• 자료구조

• ADT에서 정의된 동작을 실제로 구현한 것

스택(stack) -> Last In First Out 형태로 데이터를 저장하는 구조

자바 내부 구현 ArrayDeque -> FirstInFirstOut

• 스택 주요 동작

  • push

  • pop

  • peek

큐(queue) -> First In First Out 형태로 데이터를 저장하는 구조

• 큐 주요 동작

  • enqueue

  • dequeue

  • peek

스택 사용 사례 : stack memory & stack frame

큐 사용 사례 : producer/consumer architecture

• producer가 생산한 item을 consumer가 queue 자료구조를 통해 소비한다.

기술 문서에서 큐를 만났을 때 팁

• 큐가 반드시 FIFO를 의미하는 것은 아니다

• Priority queue와 같이 우선순위에 따라 먼저 소비되는 자료구조가 있기 때문이다.

스택/ 큐 자료구조 관련 에러

• StackOverflowError

  • 재귀함수(recursive funcition)에서 탈출 못해서 발생

    • 재귀 함수에서 탈출 조건이 올바르지 않을 때

    • 스택 프레임에 계속해서 쌓일 때

• OutofMemoryError

  • Java의 힙(heap) 메모리를 다 썼을 때 발생

  • 큐에 데이터가 계속 쌓이기만 한다면 발생

  • 큐의 사이즈를 고정시키는게 중요한데 만약 큐가 꽉 찬다면?

    • 예외 (exception) 던지기

    • 특별한 값(null or false)를 반환

    • 성공할 때까지 영원히 스레드 블락(block)

    • 제한된 시간만 블락되고 그래도 안되면 포기

LinkedBlockingQueue로 OutofMemoryError 방지하기

전제 : 고정 크기 LinkedBlockingQueue

1. 예외 던지기 (add())

   1. 큐가 꽉 차면 IllegalStateException 예외 발생

   BlockingQueue<Integer> queue = new LinkedBlockingQueue<>(2);
   try {
       queue.add(1);
       queue.add(2);
       queue.add(3); // 💥 IllegalStateException 발생
   } catch (IllegalStateException e) {
       System.out.println("큐가 가득 차서 add 실패: " + e.getMessage());
   }

2. 특별한 값 반환(Offer())

   1. 큐가 꽉 차면 false 반환

   2. 예외 없이 실패 여부를 판단 가능

queue.offer(1); // true
queue.offer(2); // true
boolean result = queue.offer(3); // false
if (!result) {
    System.out.println("offer 실패: 큐가 가득 참");
}

1. 무한 대기 (put)

new Thread(() -> {
    try {
        queue.put(1);
        queue.put(2);
        queue.put(3); // 여기가 블로킹됨
        System.out.println("put 성공");
    } catch (InterruptedException e) {
        e.printStackTrace();
    }
}).start();

Thread.sleep(1000); // 1초 후 소비
queue.take(); // 하나 꺼냄 -> put(3) 진행 가능

1. 제한 시간 대기 (offer(value, timeout, unit))

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

boolean result = queue.offer(3, 2, TimeUnit.SECONDS); // 2초 대기 후 실패 시 false
if (!result) {
     System.out.println("2초 내 공간 생기지 않아 offer 포기);
}