컨테이너 어댑터 (Container Adapter)

컨테이너 어댑터(container adapter)를 간단ㄷ하게 요약하면, 다른 컨테이너를 기반으로 새로운 기능을 제공하는 컨테이너 라고 말할 수 있다. 즉, 기존의 컨테이너를 감싸서 새로운 인터페이스를 제공한다.

예를 들어 std::stack 컨테이너 어댑터는 std::vector 컨테이너를 기반으로 LIFO (Last In First Out) 자료 구조를 제공하고, std::queue 컨테이너 어댑터는 std::deque 컨테이너를 기반으로 FIFO (First In First Out) 자료 구조를 제공한다.

컨테이너

헤더

설명

스택 (std::stack)

std::stack은 C++ 표준 템플릿 라이브러리에서 제공하는 컨테이너 어댑터 중 하나로, 스택(stack) 자료구조를 구현하는 데 사용한다.

스택은 데이터를 차례대로 쌓고 가장 마지막에 넣은 데이터를 가장 먼저 꺼낸다. 이를 후입 선출, 영어로는 Last In First Out (LIFO)라고 한다. 이러한 특성 때문에 스택은 데이터를 임시로 저장하거나 역순으로 처리할 때 주로 사용한다.

std::stack<데이터_형식> 객체_이름;

• 스택에 데이터를 넣을 때는 push 함수를 사용하고 데이터를 맨 위쪽에 쌓는다.
• 스택에 데이터를 꺼낼 때는 pop 함수를 사용하고 맨 위쪽의 데이터를 제거한다.
• 스택에서 맨 위쪽의 값은 top 함수로 확인할 수 있다.

다음은 스택 컨테이너를 활용하는 예제이다.

#include <iostream>
#include <stack>

using std::cout;
using std::endl;


int main()
{
    std::stack<int> myStack;

    // 스택에 데이터 추가
    myStack.push(1);
    myStack.push(2);
    myStack.push(3);

    // 스택의 맨 위쪽 값 확인
    cout << "맨 위의 원소: " << myStack.top() << endl;

    // 스택에서 데이터 제거(맨 위쪽 값 제거)
    myStack.pop();
    cout << "맨 위의 원소 제거 후, 새로운 맨 위의 원소: " << myStack.top() << endl;

    // 스택의 크기(데이터 개수) 확인
    cout << "스택 크기: " << myStack.size() << endl;

    // 스택이 비었는지 확인
    if (myStack.empty()) {
        cout << "스택이 비어있습니다." << endl;
    }
    else {
        cout << "스택이 비어있지 않습니다." << endl;
    }

    return 0;
}

실행 결과

맨 위의 원소: 3
맨 위의 원소 제거 후, 새로운 맨 위의 원소: 2
스택 크기: 2
스택이 비어있지 않습니다.

스택은 컴퓨터 과학과 프로그래밍에서 중요한 자료 구조로, 다양한 응용 분야에서 사용된다. 특히 함수 호출과 관련된 작업을 효율적으로 처리하기 위해 만들어졌다고 할 수 있다.

스택이 만들어진 주된 이유와 목적을 정리하면 다음과 같다.

• 함수 호출 관리
  • 함수가 호출될 때 스택에 호출 정보(지역 변수, 반환 주소 등)를 저장하고, 함수가 반환될 때 스택에서 이 정보를 제거하여 이전 함수로 복귀한다. 이로써 함수 호출과 반환을 효율적으로 추적하고 관리할 수 있다.
• 데이터 임시 저장
  • 스택은 데이터를 임시로 저장하고 나중에 처리해야 할 때 사용한다. 예를 들어 그래프 탐색 알고리즘에서 방문할 노드를 스택에 추가하고, 이후에 방문할 노드를 스택에서 꺼내어 처리한다.
• 역순 처리
  • 스택은 데이터나 작업을 역순으로 처리할 때 유용하다. 데이터를 스택에 쌓고 나중에 역순으로 꺼내어 처리하면 역순 처리를 구현할 수 있다.
• 재귀 알고리즘
  • 일부 재귀 알고리즘은 스택을 사용하여 반복해서 호출하고 결과를 누적한다. 예를 들어 팩토리얼 계산, 피보나치 수열 등의 재귀 알고리즘ㅈ을 구현할 때 스택을 활용할 수 있다.
• 컴퓨터 아키텍처
  • 스택은 프로세서 아키텍처에서 중요한 역할을 한다. 프로세서는 내부적으로 함수 호출과 반환을 위한 스택을 사용하며 스택 포인터(SP)를 통해 스택의 상태를 추적한다.
• 컴파일러와 언어 구현
  • 컴파일러와 인터프리터는 함수 호출과 반환을 처리하기 위해 스택을 사용한다. 프로그래밍 언어의 호출 스택을 관리하여 함수 호출과 반환을 지원한다.

큐 (std::queue)

std::queue는 C++ 표준 템플릿 라이브러리에서 제공하는 컨테이너 어댑터 중 하나로, 큐(queue) 자료 구조를 구현하는 데 사용한다. 큐는 가장 먼저 넣은 데이터를 가장 먼저 꺼낸다. 이를 선입 선출, 영어로는 First In First Out (FIFO)라고 한다.

C++ 표준 템플릿 라이브러리에서 큐는 내부적으로 덱(std::deque) 컨테이너를 사용한다. 덱은 양쪽 끝에서 삽입과 삭제가 효율적이므로 큐에 적합한 구조이다.

큐 컨테이너는 동작 방법이 매우 직관적이므로 활용 예를 보면서 각 멤버 함수를 어떻게 사용하는지 확인해보자.

#include <iostream>
#include <queue>

using std::cout;
using std::endl;


int main()
{
    std::queue<int> myQueue;

    // 삽입
    myQueue.push(1);
    myQueue.push(2);
    myQueue.push(3);

    cout << "큐의 맨 앞: " << myQueue.front() << endl;
    cout << "큐의 맨 뒤: " << myQueue.back() << endl;

    // 꺼내기
    myQueue.pop();

    cout << "pop() 후의 큐의 맨 앞: " << myQueue.front() << endl;
    cout << "pop() 후의 큐의 맨 뒤: " << myQueue.back() << endl;

    // 비었는지 확인
    cout << "큐가 비었는가? " << (myQueue.empty() ? "네" : "아니오") << endl;

    // 크기 구하기
    cout << "큐의 크기: " << myQueue.size() << endl;

    return 0;
}

실행 결과

큐의 맨 앞: 1
큐의 맨 뒤: 3
pop() 후의 큐의 맨 앞: 2
pop() 후의 큐의 맨 뒤: 3
큐가 비었는가? 아니오
큐의 크기: 2

큐는 데이터의 순서를 보장하고 특히 선입 선출 특성 덕분에 먼저 들어온 데이터가 먼저 처리되어야 하는 상황에서 효과적으로 사용된다. 대표적으로 다음과 같은 상황에서 유용하게 활용할 수 있다.

• 작업 대기열
  • 여러 작업이 도착하는 상황에서 먼저 도착한 작업을 먼저 처리할 때 queue를 사용한다.
    • 예를 들어 프로세스 스케쥴링에서 CPU가 실행할 프로세스를 대기열에 넣어 두고 먼저 도착한 프로세스를 먼저 실행할 때에 사용한다.
• 이벤트 처리
  • 이벤트 기반 시스템에서 이벤트가 발생하는 순서대로 처리할 때 queue를 사용한다.
    • 사용자 입력, 네트워크 메시지, 다양한 이벤트를 queue에 저장하고 차례로 처리할 때도 유용하다.
• 멀티스레딩 환경에서 동기화
  • 여러 스레드가 동시에 실행되는 상황에서 스레드 간에 작업이나 데이터 교환을 조절하기 위해 queue를 활용할 수 있다.
    • 하나의 스레드에서 생성된 작업을 queue에 넣고 다른 스레드에서 꺼내어 처리하는 방식으로 스레드 간에 동기화를 간단하게 구현할 수 있다.
• 너비 우선 탐색
  • 그래프나 트리 같은 자료 구조에서 너비 우선 탐색을 수행할 때 queue를 사용한다.
    • 너비 우선 탐색은 한 노드에서 시작하여 인접한 모든 노드를 먼저 방문하는 알고리즘이다.
• 캐시 구현
  • 캐시에서 데이터를 저장하고 검색할 때 queue로 구현할 수 있다.
    • 가장 먼저 들어온 데이터가 먼저 나가는 queue 구조를 사용하여 데이터를 관리한다.