💡스택(Stack)

• 정의 : 팬케이크를 먹는 것처럼 마지막에 올린 것을 가장 먹는 구조(LIFO)
• 시간 복잡도 : 평균적으로 push, pop, peek 모두 O(1)
• 연산
  - push(x) : 스택 맨 위(top)에 x 추가
  - pop() : 맨 위 원소 제거 + 반환
  - peek() : 맨 위 원소 조회(제거 하지 않음)
• 사용 사례
  - 재귀 호출 관리 ( 함수 콜 스택)
  - 괄호 유효성 검사
  - 컴파일러/파서 (중위 -> 후위 변환)

💡큐(Queue)

• 정의 : 줄 서기 처럼 먼저 들어온 것이 먼저 나오는 구조(FIFO)
• 시간 복잡도 : 평균적으로 offer/poll/peek 모두 O(1)
• 연산
  - enqueue(x) 또는 offer(x) : 맨 뒤(tail)에 x 추가
  - dequeue() 또는 poll() : 앞(front) 원소 제거 + 반환
  - peek() : 맨 앞 원소 조회(제거 하지 않음)
  
• 사용 사례
  - BFS 탐색(그래프/트리 최단 거리)
  - 작업 대기열(Job Queue), 메시지 큐(Kafka, RabbitMQ)
  - 운영체제 스케줄러 (CPU 라운드로빈)

💡변형된 큐

• 원형 큐(Circular Queue)
  배열 기반에서 당기는 비용 제거 → head/tail 포인터를 순환시켜 공간 재사용.

• 우선순위 큐(Priority Queue)
  먼저 들어온 순서가 아니라 우선순위 값 기준. (Java: PriorityQueue)

• 이중 큐(Deque)
  앞/뒤 양쪽에서 삽입·삭제 가능. (Java: ArrayDeque)

1. 스택과 큐의 차이를 설명해보세요.
스택은 LIFO, 큐는 FIFO 구조이며, 스택은 최근 작업을 우선처리하며 큐는 먼저 도착한 작업을 우선처리합니다. 각 연산의 복잡도는 평균 O(1)입니다.

2. 스택의 대표 사례를 말해주세요
최근 작업을 되돌리거나 중첩 구조를 관리할때 사용되며, 대표사례로는
함수 호출 스택(콜 스택), 문자열 역순, 괄호 검사/파서, 백트래킹, DFS

3. 큐의 대표 사례를 말해주세요.
공평하게 순차적으로 처리해야할 때 사용되며, 대표 사례로는
BFS, 작업/메시지큐(비동기 처리), 운영체제 스케줄러
👉BFS는 뭔가요?
그래프/트리 탐색 알고리즘 중 하나로, 시작 노드에서 가까운 노드부터 차례로 탐색하는 방식입니다. 탐색순서는 큐 덕분에 가까운 것부터 진행됩니다.

4. 큐를 배열 OR 연결리스트로 구현했을 때의 차이점은 무엇인가요?
배열 : 캐시 친화, 상수 시간 빠르지만 크기 제한 있어 리사이즈가 필요합니다.
링크드리스트 : 유연한 크기, 하지만 메모리 오버헤드와 캐시 비우호적입니다.
대체로 배열 기반이 성능면에서 유리합니다.

5. 원형 큐는 왜쓰나요?
단순 배열 큐는 dequeue 시 O(n)복사가 필요하지만, 원형 큐는 인덱스를 회전시켜 복잡도를 O(1)로 유지합니다.

6. 스택/큐를 이용하여 괄호 검사문제는 어떻게 푸나요?
괄호 검사는 스택을 이용하는게 유리합니다.
위에서 부터 검사해서 여는 괄호를 만나면 push하고, 닫는 괄호를 만나면 top이 대응하는 괄호인지 확인 후, 짝을 만나면 pop, 전부 처리 후 스택이 비었으면 유효
시간복잡도, 공간복잡도 O(n)
👉왜 큐가 아니라 스택을 사용하나요?
닫는 괄호가 나오면 가장 최근에 열린 괄호와 매칭해야하므로 후입 선출 특성의 스택이 자연스럽습니다.