🧱 스택(Stack)과 큐(Queue) 기본 개념과 활용 예시

1. 스택(Stack)이란? 

스택은 "쌓는다"는 개념과 가장 잘 어울리는 자료구조다. 데이터를 차곡차곡 쌓아 올리는 형태로 저장하며 가장 마지막에 들어간 데이터가 가장 먼저 제거되는 후입선출(LIFO, Last-In-First-Out) 방식으로 동작한다.

주요 연산

스택은 구조적으로 한쪽 끝(Top)에서만 데이터의 접근, 삽입, 삭제가 이루어진다.

• push(item): 스택의 맨 위에 새로운 데이터를 추가한다.
• pop(): 스택의 맨 위에 있는 데이터를 제거하고 그 값을 반환한다.
• peek() 또는 top(): 스택의 맨 위에 있는 데이터를 제거하지 않고 어떤 값인지 확인만 한다.
• isEmpty(): 스택에 데이터가 존재하지 않고 비어있는지 여부를 논리값(boolean)으로 반환한다.

시간 복잡도

삽입 및 삭제 (push, pop)
스택은 항상 최상단에서만 데이터를 추가하거나 제거하므로 데이터의 개수와 상관없이 O(1)의 시간 복잡도를 가진다.

탐색
특정 요소를 찾으려면 최상단부터 순차적으로 데이터를 확인해야 한다. 따라서 최악의 경우 모든 데이터를 확인해야 하므로 O(n)의 시간 복잡도를 가진다.

주요 활용 사례

스택은 데이터의 작업 순서를 추적하고 가장 최근의 상태로 되돌아가야 하는 기능에 주로 사용된다.

실행 취소 (Undo)
문서 편집기 등에서 사용자가 가장 최근에 실행한 작업부터 순차적으로 취소한다.

웹 브라우저 방문 기록
뒤로 가기 기능 작동 시 가장 마지막에 방문한 페이지부터 순서대로 로드한다.

함수의 콜 스택 (Call Stack)
프로그램 실행 중 함수가 호출될 때 해당 함수의 지역 변수와 복귀 주소 등을 저장하고 함수 종료 시 이전 실행 위치로 돌아가는 데 사용된다.

수식 및 괄호 검사
프로그래밍 코드나 수식에서 열린 괄호와 닫힌 괄호의 짝이 올바르게 맞는지 검증할 때 사용된다.

DFS (Depth-First Search, 깊이 우선 탐색)
그래프 탐색 과정에서 깊이를 우선적으로 탐색할 때 스택 구조가 활용될 수 있다.


[연습 문제 링크]
1. 스택
2. 괄호
3. 쇠막대기
4. 탑

2. 큐(Queue)란?

큐는 데이터를 순서대로 저장하며 가장 먼저 들어간 데이터가 가장 먼저 제거되는 선입선출(FIFO, First-In-First-Out) 방식으로 동작한다.

즉 먼저 들어온 데이터가 먼저 나가며 마치 매표소에서 줄을 선 사람이 먼저 표를 구매하고 나가는 구조와 같다.

주요 연산

큐는 구조적으로 한쪽 끝(Rear)에서는 데이터의 삽입, 반대쪽 끝(Front)에서는 데이터의 삭제가 이루어진다.

• enqueue(item): 큐의 맨 뒤에 새로운 데이터를 추가한다.
• dequeue(): 큐의 맨 앞에 있는 데이터를 제거하고 그 값을 반환한다.
• peek() 또는 front(): 큐의 맨 앞에 있는 데이터를 제거하지 않고 어떤 값인지 확인만 한다.
• isEmpty(): 큐에 데이터가 존재하지 않고 비어있는지 여부를 논리값(boolean)으로 반환한다.

시간 복잡도

삽입 및 삭제 (enqueue, dequeue)
위치를 찾는 과정 없이 큐의 양 끝단에서 바로 연산이 수행되므로 데이터의 개수와 무관하게 O(1)의 시간 복잡도를 가진다.

탐색
특정 요소를 찾기 위해서는 맨 앞부터 순차적으로 데이터를 확인해야 하므로 최악의 경우 O(n)의 시간 복잡도를 가진다.

주요 활용 사례

큐는 주로 데이터가 입력된 순서대로 순차적인 처리가 필요한 상황에 사용된다.

운영체제의 작업 스케줄링
CPU를 할당받기 위해 대기하는 프로세스들이나 디스크 스케줄링 등을 순서대로 관리한다.

프린터 인쇄 대기열 (Spooling)
여러 인쇄 요청이 들어왔을 때 먼저 요청된 문서부터 순차적으로 출력한다.

메시지 큐 (Message Queue)
시스템 간 비동기적인 데이터 교환 환경에서 트래픽을 제어하고 데이터를 순차적으로 전달하기 위한 버퍼 역할을 한다.

너비 우선 탐색 (BFS, Breadth-First Search)
그래프 탐색 알고리즘에서 시작 정점으로부터 가까운 정점부터 순서대로 방문하기 위해 큐를 활용한다.


[연습 문제 링크]
1. 큐
2. 요세푸스 문제
3. 카드1
4. 프린터 큐