#3. 스택과 큐

1. 스택(Stack)

스택은 후입선출(Last In First Out, LIFO) 방식의 자료구조입니다. 나중에 들어온 데이터가 먼저 나가는 구조로, 접시를 쌓거나 되돌리기(Undo) 기능 등을 구현할 때 자주 사용됩니다.

 

 

스택의 특징

• LIFO 구조: 나중에 들어온 데이터가 먼저 나갑니다.
• 기본 연산:
  • push: 데이터를 스택에 추가
  • pop: 가장 마지막에 추가된 데이터를 제거 및 반환
  • peek or top: 삭제 없이 가장 위에 있는 데이터를 조회
• 일반적으로 배열(Array)이나 연결 리스트(Linked List)를 이용해 구현할 수 있습니다.

 

스택의 시간 복잡도

연산시간 복잡도

push	O(1)
pop	O(1)
peek	O(1)

 

스택의 활용 예시

• 웹 브라우저의 뒤로 가기(Back) 기능
• 괄호 검사, 수식 계산 (후위 표기법)
• DFS(깊이 우선 탐색) 구현
• 함수 호출 시의 콜 스택(Call Stack)

 

---

 

2. 큐(Queue)

큐는 선입선출(First In First Out, FIFO) 방식의 자료구조입니다. 먼저 들어온 데이터가 먼저 나가는 구조로, 줄 서기, 작업 예약 시스템 등에서 사용됩니다.

 

큐의 특징

• FIFO 구조: 먼저 들어온 데이터가 먼저 나갑니다.
• 기본 연산:
  • enqueue: 데이터를 큐에 추가
  • dequeue: 가장 앞에 있는 데이터를 제거 및 반환
  • peek or front: 삭제 없이 가장 앞의 데이터를 조회
• 배열 또는 연결 리스트로 구현 가능하며, 성능을 위해 원형 큐(Circular Queue)도 사용됩니다.

 

📊 큐의 시간 복잡도

연산시간 복잡도

enqueue	O(1)
dequeue	O(1)
peek/front	O(1)

 

큐의 활용 예시

• 은행의 대기열, 프린터 대기열
• BFS(너비 우선 탐색) 알고리즘
• 캐시(Cache)에서의 FIFO 교체 정책

 

---

 

3. 스택 vs 큐

항목스택(Stack)큐(Queue)

구조	후입선출 (LIFO)	선입선출 (FIFO)
주요 연산	push, pop, peek	enqueue, dequeue, peek
접근 방식	마지막 요소에 접근	첫 번째 요소에 접근
사용 예시	웹 뒤로가기, DFS	BFS, 대기열, 프로세스 관리