Stack and Queue

Stack and Queue

배열에서 조금 더 발전한 형태의 자료구조

Stack (스택)

개념

• LIFO(Last In First Out): 후입선출
• 나중에 들어온 데이터가 먼저 나가는 구조

주요 연산

1. push: 데이터를 스택의 맨 위에 삽입
2. pop: 스택의 맨 위 데이터를 제거하고 반환
3. top: 스택의 맨 위 데이터를 확인 (제거하지 않음)

동작 과정

1. 빈 스택 → push(새 값) → 스택에 값 추가
2. 데이터 있는 스택 → pop() → 맨 위 값 제거
3. top 포인터가 항상 스택의 최상단을 가리킴

활용

• 깊이 우선 탐색(DFS: Depth First Search)
• 백트래킹 종류의 코딩 테스트에 효과적
• LIFO(후입선출) 개념 자체가 재귀 함수 알고리즘의 원리와 일맥상통

---

Queue (큐)

개념

• FIFO(First In First Out): 선입선출 자료구조
• 스택과 달리 양쪽 끝에서 삽입과 삭제가 이루어짐

큐의 구조

[새 값] → [값] [값] [값] [값] [지울 값] → [pop]
        ↑                           ↑
      back                       front
      (rear)                    (head)

주요 연산

• push: back 부분에 새로운 데이터를 삽입하는 연산
• pop: front에서 데이터를 제거하는 연산
• back: 큐에서 가장 끝 데이터를 가리키는 영역
• front: 큐에서 가장 앞의 데이터를 가리키는 영역

동작 원리

1. 새 데이터 추가: back(rear) 위치에 push
2. 데이터 제거: front(head) 위치에서 pop
3. 먼저 들어온 데이터가 먼저 나감

큐 관련 용어

• back = rear: 큐의 뒤쪽 (삽입 위치)
• front = head: 큐의 앞쪽 (삭제 위치)

활용 예시

• 프린터 대기열
• BFS(너비 우선 탐색)
• 작업 스케줄링
• 버퍼링 시스템

핵심 차이점

구조	삽입/삭제 위치	데이터 순서	예시
스택	한쪽 끝(top)	후입선출	접시 쌓기
큐	양쪽 끝	선입선출	대기줄

---

우선순위 큐 (Priority Queue)

• 들어간 순서와 상관없이 우선순위가 높은 데이터가 먼저 나오는 자료구조
• 일반적으로 힙(heap)을 이용해 구현

---

알고리즘과의 연관성

• 스택 → DFS (깊이 우선 탐색)
• 큐 → BFS (너비 우선 탐색)