📚 스택(Stack) & 큐(Queue) 정리

🔍 스택(Stack)과 큐(Queue)란?

스택(Stack)과 큐(Queue)는 데이터를 저장하고 관리하는 선형 자료 구조입니다.
각각의 특징을 살펴보면 다음과 같습니다.

✅ 스택(Stack)

• 후입선출(LIFO: Last In, First Out) 구조

• 마지막에 삽입된 데이터가 가장 먼저 삭제됨

• 대표적인 활용 예시:

  • DFS(깊이 우선 탐색)

  • 역순 문자열 생성

  • 실행 취소(Undo) 기능

  • java

    class Stack {
      private int[] arr;
      private int top;
      private int capacity;
    
      public Stack(int size) {
          arr = new int[size];
          capacity = size;
          top = -1;
      }
    
      // 요소 추가 (Push)
      public void push(int value) {
          if (top == capacity - 1) {
              System.out.println("Stack Overflow");
              return;
          }
          arr[++top] = value;
      }
    
      // 요소 제거 (Pop)
      public int pop() {
          if (isEmpty()) {
              System.out.println("Stack Underflow");
              return -1;
          }
          return arr[top--];
      }
    
      // 최상단 요소 확인 (Peek)
      public int peek() {
          if (isEmpty()) {
              System.out.println("Stack is empty");
              return -1;
          }
          return arr[top];
      }
    
      // 스택이 비어 있는지 확인
      public boolean isEmpty() {
          return top == -1;
      }
      
      // 스택 크기 확인
      public int size() {
          return top + 1;
      }
      
      public static void main(String[] args) {
          Stack stack = new Stack(5);
          stack.push(10);
          stack.push(20);
          stack.push(30);
          
          System.out.println("Top element: " + stack.peek()); // 30
          System.out.println("Popped element: " + stack.pop()); // 30
          System.out.println("Stack size: " + stack.size()); // 2
      }
    }

✅ 큐(Queue)

• 선입선출(FIFO: First In, First Out) 구조

• 먼저 삽입된 데이터가 가장 먼저 삭제됨

• 대표적인 활용 예시:

  • BFS(너비 우선 탐색)

  • 작업 스케줄링

  • 캐시 구현

  • java

    class Queue {
      class Node {
          int data;
          Node next;
          
          public Node(int data) {
              this.data = data;
              this.next = null;
          }
      }
    
      private Node front, rear;
      private int size;
    
      public Queue() {
          front = rear = null;
          size = 0;
      }
    
      // 요소 추가
      public void push(int value) {
          Node newNode = new Node(value);
          if (rear == null) {
              front = rear = newNode;
          } else {
              rear.next = newNode;
              rear = newNode;
          }
          size++;
      }
    
      // 요소 제거
      public int pop() {
          if (isEmpty()) {
              System.out.println("Queue Underflow");
              return -1;
          }
          int value = front.data;
          front = front.next;
          if (front == null) rear = null;
          size--;
          return value;
      }
    
      // 앞 요소 확인 (Peek)
      public int peek() {
          if (isEmpty()) {
              System.out.println("Queue is empty");
              return -1;
          }
          return front.data;
      }
    
      // 큐가 비어 있는지 확인
      public boolean isEmpty() {
          return front == null;
      }
      
      // 큐 크기 확인
      public int size() {
          return size;
      }
    
      public static void main(String[] args) {
          Queue queue = new Queue();
          queue.push(5);
          queue.push(15);
          queue.push(25);
          
          System.out.println("Front element: " + queue.peek()); // 5
          System.out.println("Dequeued element: " + queue.pop()); // 5
          System.out.println("Queue size: " + queue.size()); // 2
      }
    }

---

🔥 면접에서 자주 나오는 스택 & 큐 관련 질문

1️⃣ 스택과 큐의 차이점

Q: 스택과 큐의 차이는 무엇인가요?
A:

• 스택은 LIFO(Last In, First Out) 구조이며, 마지막에 삽입된 데이터가 가장 먼저 삭제됩니다.
• 큐는 FIFO(First In, First Out) 구조이며, 먼저 삽입된 데이터가 가장 먼저 삭제됩니다.

2️⃣ 스택을 사용하는 시스템은?

Q: 스택이 사용되는 시스템의 예시는 무엇이 있나요?
A:

• 컴퓨터 시스템의 호출 스택(Call Stack)
• 웹 브라우저의 뒤로 가기(History Back) 기능
• 알고리즘에서 DFS(깊이 우선 탐색)

3️⃣ 스택과 힙(Heap)의 차이점

Q: 스택(Stack)과 힙(Heap)의 차이는 무엇인가요?
A:

• 스택(Stack): 지역 변수 저장, 컴파일 시 크기 결정
• 힙(Heap): 동적 메모리 할당, 런타임 시 크기 변경 가능

---

📌 마무리

스택과 큐는 알고리즘 및 시스템 설계에서 중요한 자료 구조이며, 면접에서 자주 질문되는 개념입니다.
각 자료 구조의 특징을 이해하고, 실제 활용 사례를 파악하면 실무 및 코딩 테스트에서도 유용하게 사용할 수 있습니다.