[자료구조] 스택(Stack)&큐(Queue) 와 컨테이너(Container)

 

0. 컨테이너 어댑터(Container Adapter)

앞으로 설명할 std::stack과 std::queue 는 컨테이너 어댑터 이다.

컨테이너 어댑터란?
이미 있는 컨테이너를 기반으로, 특정한 인터페이스만 제공하도록 제한해서 만든 컨테이너

 

즉, 스택과 큐 자체는 데이터를 직접 저장하지 않고, 내부적으로 다른 컨테이너 (vector 또는 deque 또는 list)를 사용한다는 것.

 

스택과 큐의 개념은 간단하기 때문에, 컨테이너를 중심으로 설명해보고자 한다. 

 

 

1. 스택(Stack)

 

LIFO (Last In, First Out) 즉, 후입선출 구조 

• 주요 연산 : push (삽입), pop (삭제), top (맨 위 요소 조회)
• 기본 컨테이너 : deque 

 

 

1-1. 스택에 요구되는 멤버함수 

스택은 LIFO 구조이므로, 항상 끝(Top)에서만 삽입/삭제/참조가 일어나기 때문에

-> 내부 컨테이너는 반드시 끝에서만 작동하는 연산을 제공해야 한다. 

• 스택 내부 컨테이너는 다음 멤버 함수들을 반드시 제공해야 함:

멤버 함수	역할
push_back()	컨테이너 끝에 새 원소 추가 (push 구현)
pop_back()	컨테이너 끝 원소 제거 (pop 구현)
back()	컨테이너 끝 원소 참조 (top 구현)

 

 

1-2. 사용 가능한 컨테이너 예시 

컨테이너	사용 가능 여부	비고
vector<int>	✅ 가능	push_back, pop_back, back 지원
deque<int>	✅ 가능	push_back, pop_back, back 지원  (기본 사용)
list<int>	✅ 가능	push_back, pop_back, back 지원
array<int, N>	❌ 불가능	push_back, pop_back 없음

 

 

1-3. 스택의 활용 

“최근에 넣은 걸 가장 먼저 꺼낸다” 를 활용

 

1. 함수 호출(프로그램 실행)

• 우리가 함수를 호출할 때마다 호출 스택(Call Stack) 에 지역 변수, 반환 주소 등을 저장한다.
• 함수가 끝나면 마지막에 호출된 함수부터 역순으로 반환 → LIFO 구조 그대로.

 

2. Undo/Redo 기능

• 텍스트 에디터, 그래픽 툴 등에서 작업명령 push, pop
  • Undo: 가장 최근 작업을 pop
  • Redo: pop 했던 작업을 다시 push

 

3. 백트래킹 알고리즘

• 미로 찾기, 퍼즐 같은 문제 풀이에서 현재 상태를 push, 막히면 pop 하여 이전 상태로 돌아감.

 

4. 수식 계산

• 후위 표기법(Postfix) 계산기 구현
• 괄호가 포함된 중위 표기식 → 후위 표기식 변환
• 연산자 우선순위를 처리하는 과정에서 스택이 핵심.

 

 

 

 

 

2. 큐(Queue) 

FIFO (First In, First Out) 즉, 선입선출 구조 

• 주요 연산 : enqueue / push (삽입), dequeue / pop (삭제), front (앞 요소 조회), back (뒤 요소 조회)
• 기본 컨테이너 : deque 

 

2-1. 큐에 요구되는 멤버함수

큐는 FIFO 구조이므로, 삽입은 뒤에서, 삭제는 앞에서 일어나기 때문에

-> 내부 컨테이너는 앞/뒤에서 작동하는 연산을 제공해야 한다.

• 큐 내부 컨테이너는 다음 멤버 함수들을 반드시 제공해야 함:

멤버 함수	역할
push_back()	컨테이너 뒤에 새 원소 추가 (enqueue 구현)
pop_front()	컨테이너 앞 원소 제거 (dequeue 구현)
front()	컨테이너 앞 원소 참조
back()	컨테이너 뒤 원소 참조

 

2-2. 사용 가능한 컨테이너 예시

컨테이너	사용 가능 여부	비고
vector<int>	❌ 불가능	pop_front 미지원
deque<int>	✅ 가능	(기본 사용)
list<int>	✅ 가능	push_back, pop_front 지원
array<int, N>	❌ 불가능	push_back, pop_front 없음

 

2-3. 큐의 활용 

“먼저 들어온 걸 가장 먼저 꺼낸다” 를 활용

 

 

1. 운영체제(OS)에서의 큐 활용

운영체제에서는 자원을 관리하고 작업을 처리하는 데 큐 구조가 핵심 역할을 한다.

• 프로세스 스케줄링
  • CPU 스케줄링에서 프로세스가 CPU를 기다리는 순서를 관리할 때 사용
  • 예: Ready Queue
    • 준비 상태(Ready)인 프로세스를 FIFO 순서대로 CPU에 할당
    • 선입선출(FIFO) 스케줄링 알고리즘에서 큐 활용
• 입출력(I/O) 관리
  • I/O 장치가 요청을 처리할 때, 요청 순서를 관리
  • 예: Printer Queue, Disk I/O Queue
    • 먼저 요청한 작업이 먼저 처리됨 (FIFO)
• 작업 대기열 (Job / Task Queue)
  
  • CPU 스케줄링에서 Ready Queue로 사용.
  • 준비 상태인 프로세스를 FIFO 순서로 CPU에 할당

 

 

2. 프로그래밍에서의 큐 활용

프로그래밍에서는 큐를 데이터 처리 순서를 관리하거나 실시간 이벤트 처리에 활용한다.

• 이벤트 처리
  • GUI 프로그램이나 게임 엔진에서는 입력 이벤트(키보드, 마우스)를 이벤트 큐에 넣는다.
  • 메인 루프는 큐에서 이벤트를 꺼내 차례대로 처리 
• 멀티스레드 프로그래밍 (Producer-Consumer 문제)
  • 한 스레드가 데이터를 생산하고 다른 스레드가 이를 소비 할 때, 큐를 통해 안전하게 데이터 전달.
• 네트워크 패킷 처리
  • 수신한 패킷들을 큐에 넣어두고, 네트워크 스택이나 애플리케이션이 차례로 꺼내 처리
  • 송신할 패킷도 큐에 쌓았다가 순서대로 전송한다. 
• 버퍼 관리
  • 오디오/비디오 스트리밍, 센서 데이터, 로그 등에서 순차적 재생을 위해 큐 버퍼를 사용
  • 생산자는 데이터를 넣고, 소비자는 재생 순서대로 꺼낸다.

 

 

 

---

 

스택과 큐에 대한 간단한 개념을 정리해보았는데,

 

스택과 큐에 대해 정리하다 보니, 컨테이너와 컨테이너 어댑터에 대한 내용도 언급하게 되었다.

이후에는 C++ STL의 구성 요소에 대해 정리해볼까 한다.....