[매일메일] Java의 Stack, Queue, Deque란? (BE.2501223)

자료구조 전공 수업을 배우거나, 코딩 테스트 문제를 몇 번 풀어봤다면 주구장창 봤을 개념.

• Stack이란? 좁고 긴 통에 나무 블록을 넣었다면, 다시 꺼낼 땐 가장 최근에 넣었던 블록부터 꺼내게 될 것.
  • 후입선출 Last In First Out(LIFO). 삭제(pop)는 가장 최상단(top)에서 이루어짐.
  • Stack Underrflow: 비어있는 스택에서 값을 추출하려고 시도하는 경우
  • Stack Overflow: 스택이 넘치는 경우
  • Stack 활용 사례: 스택 메모리, 브라우저 뒤로가기, undo, 수식 괄호 검사
• Java에서 Stack/Queue/Deque
  • Stack Class: 재귀 호출, 수식 계산, Undo/Redo, 문자열 역순 처리
    • Java에 Stack이라는 Class가 있음.
      • List Collection의 Vector를 상속받은 스택 메모리 구조의 Class임.
      • 배열 기반 데이터 구조라서 index를 통한 접근/삽입/제거가 가능함.
      • 하지만 index를 통한 임의 원소 접근은 LIFO의 특성에 맞지 않음.

      • Stack<Integer> stack = new Stack<>();
        stack.push(10);
        stack.push(20);
        stack.push(30);
        
        System.out.println(stack); // [10, 20, 30]
        
        // 잘못된 사용: Vector에서 상속받은 메서드로 임의 위치에 삽입
        stack.add(1, 15); // [10, 15, 20, 30]
        System.out.println(stack);
        
        // 이는 스택의 LIFO 원칙을 위반함

    • Vector method는 synchronized로 구현되어 있음.
      • Multi-thread 환경에서는 동기화의 이점이 있음.
      • Single-thread 환경에서는 불필요한 동기화 작업으로 성능 측면에서 안좋음.
      • 모든 작업에 Lock이 사용되어 단순한 Iterator 탐색을 위한 get() 실행에도 Lock 발생.
      • Vector 상속을 받았기 때문에 다중상속을 지원하지 않음.
    • 초기 크기 지정을 지원하지 않음.

    • import java.util.Stack;
      
      public class StackExample {
          public static void main(String[] args) {
              Stack<Integer> stack = new Stack<>();
      
              // Push elements
              stack.push(10);
              stack.push(20);
              stack.push(30);
      
              System.out.println("Stack: " + stack); // [10, 20, 30]
      
              // Peek
              System.out.println("Top element: " + stack.peek()); // 30
      
              // Pop elements
              System.out.println("Popped: " + stack.pop()); // 30
              System.out.println("Popped: " + stack.pop()); // 20
      
              System.out.println("Stack after pops: " + stack); // [10]
          }
      }

  • Queue interface: 작업 스케줄링, 메시지 처리, 이벤트 큐
    • 선입 선출. First In First out. 밑이 뚫린 원통에 나무 조각을 집어넣기.
    • index 요소로 접근/삽입/제거를 허용하지 않음.
    • java.util.Queue 인터페이스 사용하며, 주요 구현체는 LinkeList, PriorityQueue

    • import java.util.LinkedList;
      import java.util.Queue;
      
      public class QueueExample {
          public static void main(String[] args) {
              Queue<Integer> queue = new LinkedList<>();
      
              // Add elements
              queue.offer(10);
              queue.offer(20);
              queue.offer(30);
      
              System.out.println("Queue: " + queue); // [10, 20, 30]
      
              // Peek
              System.out.println("Front element: " + queue.peek()); // 10
      
              // Poll elements
              System.out.println("Polled: " + queue.poll()); // 10
              System.out.println("Polled: " + queue.poll()); // 20
      
              System.out.println("Queue after polls: " + queue); // [30]
          }
      }

  • Deque(Double -Ended Queue) Interface: 캐시 구현, 양방향 큐
    • Queue interface를 확장함. 자료 입출력이 양 끝에서 가능함. (FIFO+LIFO)
    • index 요소로 접근/삽입/제거를 허용하지 않고, push/pop/peek 메서드만 제공함. LIFO 완벽히 따름.
    • 필요에 따라 동기화 작업을 선택해 overhead를 피하고 성능을 최적화할 수 있음.
      • Lock을 사용하지 않아 단일 스레드에서도 문제가 발생하지 않음.
      • 멀티 스레드에서는 Collections.synchronizedDeque로 동기화 사용해 안정성 확보.
    • 생성자로 배열의 초기 크기를 지정할 수 있음.
    • java.util.Deque 인터페이스 사용하며, 주요 구현체는 ArrayDeque, LinkedList
    • Deque로 캐시 구현은 LRU(Least Recently Used) 쓴다고 함.
    • (가장 오랫동안 사용되지 않은 데이터를 캐시에서 제거.

    • import java.util.ArrayDeque;
      import java.util.Deque;
      
      public class DequeExample {
          public static void main(String[] args) {
              Deque<Integer> deque = new ArrayDeque<>();
      
              // Add elements to both ends
              deque.addFirst(10);
              deque.addLast(20);
      
              System.out.println("Deque: " + deque); // [10, 20]
      
              // Peek elements
              System.out.println("First element: " + deque.peekFirst()); // 10
              System.out.println("Last element: " + deque.peekLast()); // 20
      
              // Remove elements from both ends
              System.out.println("Removed First: " + deque.pollFirst()); // 10
              System.out.println("Removed Last: " + deque.pollLast()); // 20
      
              System.out.println("Deque after removals: " + deque); // []
          }
      }

       

특징	Stack	Queue	Deque
동작 방식	LIFO	FIFO	둘 다
구현클래스	Stack	LinkedList, PriorityQueue	ArrayDeque, LinkeList
유연성	제한적	단방향	매우유연
예시	재귀호출, Undo	작업스케줄링	캐시 구현

 

---

 

용어 정리

인터페이스: 클래스가 가져야 할 동작(메서드)를 구격화함. 메서드의 선언부만 있고 구현부는 없음. 다중 상속 가능.

클래스: 객체의 설계도. 객체가 가져야할 속성(필드), 동작(메서드) 정의함.

구현체: 인퍼페이스에서 정의한 메서드를 실제로 구현한 클래스. 인터페이스(설계도)를 기반으로 동작으로 정의함.

 

인터페이스(클래스 설계도) -> 구현체(설계도를 모두 구현한 클래스) ->클래스(객체를 생성하는 정의)

차의 설계도(이런 기능이 필요함)->설계도를 충족한 차(차 부품들 견적)->부품들의 세부 동작(부품들 내부 직접 만들기)

---

출처

[1] 매일메일. 250123. 자료구조 스택에 대해 설명해주세요. 104번. https://maeil-mail.kr

[2] Tecoble. Java의 Stack 대신 Deque https://tecoble.techcourse.co.kr/post/2021-05-10-stack-vs-deque/

[3] gpt에게 Java의 Stack, Deque, Queue에 대해 묻다