자료구조 마스터: 스택과 큐의 구조, 차이, 응용

스택(Stack)의 개념과 작동 방식

스택(Stack)은 LIFO(Last In First Out) 구조를 가지는 선형 자료구조입니다. 즉, 나중에 삽입된 데이터가 먼저 제거되는 구조를 가지고 있습니다. 스택은 마치 한쪽 입구만 있는 상자처럼, 데이터를 넣고 빼는 작업이 모두 같은 방향에서 이루어집니다.

스택에서는 기본적으로 다음 두 가지 연산을 수행합니다:

• push: 데이터를 스택의 맨 위에 추가
• pop: 스택의 맨 위 데이터를 제거하고 반환

그 외에:

• peek 또는 top: 스택의 맨 위 데이터를 제거하지 않고 반환
• isEmpty: 스택이 비어 있는지 확인

스택은 배열(Array)이나 연결 리스트(Linked List)를 기반으로 구현할 수 있으며, 재귀 호출의 기본 구조, 웹 브라우저의 방문 기록 저장, 괄호 검사와 같은 다양한 곳에서 활용됩니다.

큐(Queue)의 개념과 작동 방식

큐(Queue)는 FIFO(First In First Out) 구조를 가지는 선형 자료구조입니다. 먼저 삽입된 데이터가 먼저 제거되는 구조이며, 일상생활의 줄 서기와 같은 원리를 따릅니다.

큐는 다음과 같은 연산을 가집니다:

• enqueue: 데이터를 큐의 뒤쪽(Rear)에 추가
• dequeue: 큐의 앞쪽(Front) 데이터를 제거하고 반환

그 외에:

• peek 또는 front: 큐의 앞 데이터를 제거하지 않고 반환
• isEmpty: 큐가 비어 있는지 확인

큐는 배열, 연결 리스트로 구현되며, 순환 큐(Circular Queue), 우선순위 큐(Priority Queue), 덱(Deque) 등 다양한 변형 구조로 확장됩니다.

스택의 활용 사례

• 함수 호출과 재귀 처리
  • 스택은 함수 호출 시 사용되는 콜 스택(Call Stack)의 구조로 동작합니다. 재귀 함수 호출 시 이전 상태를 저장하고 복귀하는 과정에서 스택 구조가 핵심입니다.
• 괄호의 유효성 검사 및 수식 계산
  • 컴파일러에서 괄호의 유효성 검사나 후위 표기법(Postfix Expression) 계산 시 스택이 필수적으로 사용됩니다.
• 웹 브라우저의 히스토리 관리
  • 이전 페이지로 되돌아가는 기능은 방문했던 URL을 스택에 저장하고, 뒤로가기 버튼을 누르면 가장 최근의 URL을 pop하여 동작합니다.
• 실행 취소(Undo) 기능 구현
  • 문서 편집기나 그래픽 편집 도구에서 실행 취소 기능은 작업 이력을 스택에 저장하여 이전 상태로 복원하는 방식으로 구현됩니다.

큐의 실무 활용 사례

• 작업 대기열(Task Queue)
  • 운영 체제나 백엔드 시스템에서 비동기 작업 처리 시, 작업 요청을 큐에 저장하고 순차적으로 처리하는 방식으로 활용됩니다.
• 프린터의 출력 대기열
  • 여러 사용자가 출력 명령을 내릴 때, 명령은 큐에 쌓이고 순서대로 처리되어 출력됩니다.
• 네트워크 패킷 처리
  • 라우터나 네트워크 장비에서 패킷은 도착 순서대로 큐에 저장되고 처리됩니다.
• BFS(너비 우선 탐색) 알고리즘
  • 그래프나 트리에서 너비 우선 탐색을 구현할 때 큐가 사용됩니다. 탐색 순서를 관리하는 데 필수입니다.

스택과 큐의 비교

항목	스택(Stack)	큐(Queue)
구조	LIFO	FIFO
삽입 위치	맨 위(Top)	뒤쪽(Rear)
삭제 위치	맨 위(Top)	앞쪽(Front)
사용 사례	함수 호출, 되돌리기	작업 처리, 이벤트 큐
구현 난이도	낮음	중간(순환 큐 등 포함 시)

스택과 큐 면접 대비 포인트

• 자료구조의 기본 개념, 작동 방식 정확히 이해
• 시간복잡도 분석: push/pop/enqueue/dequeue 연산은 일반적으로 O(1)
• 구현 방식: 배열 vs 연결 리스트
• 실무 응용 사례 제시 가능 여부 (예: 백엔드 작업 큐, undo 기능 등)
• 스택/큐 응용 알고리즘: DFS/BFS, 괄호 검사, 후위 표기법 등

정리

스택과 큐는 컴퓨터 과학의 기초이자, 다양한 소프트웨어 시스템에서 핵심적으로 활용되는 자료구조입니다. 각각의 구조적 차이와 실무 활용 방법을 명확히 이해하고 있다면, 개발 과정뿐만 아니라 기술 면접에서도 큰 장점으로 작용할 수 있습니다.