스택(Stack), 큐(Queue)

스택 (Stack)

• 정의:
  후입선출(LIFO, Last-In First-Out) 구조.
  마지막에 들어간 데이터가 가장 먼저 나옴.
• 사용 예시:
  • 재귀 호출(함수 호출 스택)
  • 괄호 검사
  • 웹 브라우저 방문 기록
  • DFS(깊이 우선 탐색)
• 
  

  연산 항목	시간 복잡도
  n번째 참조	O(n)
  가장 위 참조	O(1)
  탐색	O(n)
  삽입/삭제(Top에서)	O(1)

큐 (Queue)

• 정의:
  선입선출(FIFO, First-In First-Out) 구조.
  먼저 들어간 데이터가 가장 먼저 나옴.
• 사용 예시:
  • 작업 스케줄링(CPU 프로세스 대기열)
  • 너비 우선 탐색(BFS)
  • 네트워크 요청 처리
  • 캐시(예: LRU 캐시)
• 시간 복잡도:
  

  연산 항목	시간 복잡도
  n번째 참조	O(n)
  가장 앞부분 참조	O(1)
  탐색	O(n)
  삽입/삭제(양 끝 제외)	O(1)

스택 vs 큐 요약 비교

항목	스택	큐
구조	LIFO (후입선출)	FIFO (선입선출)
삽입 위치	Top (맨 위)	Rear (뒤)
삭제 위치	Top (맨 위)	Front (앞)
사용 사례	재귀, DFS, 기록 등	BFS, 스케줄링, 캐시 등