스택(Stack)과 큐(Queue)

개요

스택(Stack)과 큐(Queue)는 **자료구조(Data Structure)**에서 가장 기본적인 개념으로, 데이터를 저장하고 관리하는 방식이 다릅니다. 스택은 LIFO(Last In, First Out) 구조를 가지며, 큐는 FIFO(First In, First Out) 방식을 따릅니다. 이러한 구조적인 차이로 인해 각각의 데이터 구조는 다양한 프로그래밍 및 알고리즘 문제에서 중요한 역할을 합니다. 본 글에서는 스택과 큐의 개념, 차이점, 주요 연산 및 활용 사례를 살펴봅니다.

---

1. 스택(Stack)이란?

스택(Stack)은 후입선출(LIFO, Last In First Out) 방식으로 데이터를 저장하고 처리하는 자료구조입니다. 즉, 마지막에 들어온 데이터가 가장 먼저 제거되는 구조입니다.

1.1 스택의 주요 연산

연산	설명
push(삽입)	스택의 최상단(Top)에 새로운 데이터를 추가
pop(삭제)	스택의 최상단(Top)에 있는 데이터를 제거
peek(조회)	스택의 최상단 데이터를 제거하지 않고 확인
isEmpty(공백 확인)	스택이 비어 있는지 확인
isFull(포화 확인)	스택이 가득 찼는지 확인 (배열 기반 스택의 경우 필요)

1.2 스택의 특징

✅ 후입선출(LIFO) 방식
✅ 재귀 호출 및 백트래킹(Backtracking) 문제 해결에 적합
✅ 연결 리스트(Linked List) 또는 배열(Array)로 구현 가능

1.3 스택의 활용 사례

사용 사례	설명
함수 호출 스택(Call Stack)	프로그램 실행 중 함수 호출 및 반환 관리
웹 브라우저의 뒤로 가기(Back Button)	방문한 페이지를 스택에 저장하여 뒤로 가기 구현
괄호 검사(Parenthesis Matching)	소스 코드에서 괄호 짝을 확인하는 알고리즘
DFS(Depth-First Search, 깊이 우선 탐색)	그래프 탐색 알고리즘에서 사용

---

2. 큐(Queue)란?

큐(Queue)는 선입선출(FIFO, First In First Out) 방식으로 데이터를 저장하고 처리하는 자료구조입니다. 즉, 먼저 들어온 데이터가 먼저 나가는 구조입니다.

2.1 큐의 주요 연산

연산	설명
enqueue(삽입)	큐의 뒤(Rear)에 데이터를 추가
dequeue(삭제)	큐의 앞(Front)에서 데이터를 제거
peek(조회)	큐의 앞(Front)에 있는 데이터를 제거하지 않고 확인
isEmpty(공백 확인)	큐가 비어 있는지 확인
isFull(포화 확인)	큐가 가득 찼는지 확인 (배열 기반 큐의 경우 필요)

2.2 큐의 특징

✅ 선입선출(FIFO) 방식
✅ 데이터가 순차적으로 처리되는 환경에서 유용
✅ 연결 리스트(Linked List) 또는 배열(Array)로 구현 가능

2.3 큐의 활용 사례

사용 사례	설명
프린터 작업 큐(Printer Queue)	먼저 요청한 문서가 먼저 출력됨
프로세스 스케줄링(Process Scheduling)	CPU 작업을 순차적으로 처리하는 스케줄러
네트워크 패킷 처리(Network Packet Processing)	네트워크에서 데이터 패킷을 전송 순서대로 처리
BFS(Breadth-First Search, 너비 우선 탐색)	그래프 탐색 알고리즘에서 사용

---

3. 스택과 큐의 차이점

비교 항목	스택(Stack)	큐(Queue)
데이터 저장 방식	후입선출(LIFO)	선입선출(FIFO)
삽입 연산	push() - 최상단(Top)에 추가	enqueue() - 뒤(Rear)에 추가
삭제 연산	pop() - 최상단(Top)에서 제거	dequeue() - 앞(Front)에서 제거
사용 사례	함수 호출 스택, 웹 브라우저 뒤로 가기, DFS	프린터 대기열, CPU 스케줄링, BFS
구현 방식	배열 또는 연결 리스트	배열 또는 연결 리스트

---

4. 확장된 큐의 개념: 원형 큐와 우선순위 큐

큐의 기본 개념을 확장하여 원형 큐(Circular Queue), 우선순위 큐(Priority Queue), 이중 큐(Deque) 등의 변형 구조가 존재합니다.

4.1 원형 큐(Circular Queue)

• 큐의 크기를 고정하고, 배열의 처음과 끝을 연결하여 순환 구조로 관리
• 큐가 가득 차도 비어 있는 공간이 남을 수 있는 문제를 해결

4.2 우선순위 큐(Priority Queue)

• 데이터의 삽입 순서가 아니라 우선순위(Priority)에 따라 먼저 처리
• 예: 운영체제의 프로세스 스케줄링, 네트워크 트래픽 관리

4.3 이중 큐(Deque, Double-Ended Queue)

• 앞(Front)과 뒤(Rear)에서 삽입 및 삭제가 모두 가능한 큐
• 예: 브라우저의 앞으로 가기/뒤로 가기 기능

---

5. 최신 트렌드 및 활용 사례

트렌드	설명
스택과 큐의 병렬 처리 최적화	멀티스레드 환경에서 락리스(Lock-free) 데이터 구조 연구 활성화
클라우드 기반 메시지 큐(Message Queue)	RabbitMQ, Kafka 등을 활용한 대용량 데이터 처리
GPU 가속 큐 활용	AI 및 데이터 과학에서 큐를 이용한 병렬 연산 최적화
블록체인 트랜잭션 처리	트랜잭션 대기열을 FIFO 방식으로 관리하여 처리 속도 향상

---

6. 결론

스택(Stack)과 큐(Queue)는 프로그래밍과 알고리즘에서 필수적인 자료구조입니다. 스택은 후입선출(LIFO) 방식으로 함수 호출, 웹 브라우저 내비게이션, DFS에 활용되며, 큐는 선입선출(FIFO) 방식으로 프로세스 스케줄링, 네트워크 패킷 처리, BFS 등에 사용됩니다. 최신 기술에서는 GPU 가속, 클라우드 메시지 큐, 블록체인 트랜잭션 관리 등 다양한 분야에서 스택과 큐의 효율적인 활용이 중요해지고 있습니다.