컨테이너 어댑터 (스택, 큐, 우선순위 큐)

컨테이너 어댑터(container adapter)란 기존 컨테이너의 인터페이스를 제한하여 만든 기능이 제한되거나 변형된 컨테이너를 의미한다. 이러한 컨테이너 어댑터는 각각의 기초가 되는 클래스의 인터페이스를 제한하여, 특정 형태의 동작만을 수행하도록 한다. 단, 반복자를 지원하지 않으므로 STL 알고리즘에서는 사용할 수 없다.

컨테이너 어댑터의 종류

STL에서는 컨테이너 어댑터로 다음과 같은 클래스 템플릿을 제공한다.

1. stack
2. queue
3. priority_queue

스택(stack)

스택(stack) 컨테이너는 vector 클래스의 인터페이스를 제한하여, 전형적인 스택 메모리 구조의 인터페이스를 제공한다. 스택 컨테이너는 stack 헤더 파일에 정의되어 있다. 스택 메모리 구조는 선형 메모리 공간에 데이터를 저장하면서 후입선출(LIFO)의 시멘틱을 따르는 자료 구조이다. 가장 나중에 저장된(push) 데이터가 가장 먼저 인출(pop)되는 구조.

 

스택 컨테이너는 스택 메모리 구조를 표현하기 위해 다음과 같은 멤버 함수를 제공한다.

empty()	스택이 비어 있으면 true를, 비어 있지 않으면 false를 반환함.
size()	스택 요소의 총 개수를 반환함.
top()	스택의 제일 상단에 있는(제일 마지막으로 저장된) 요소에 대한 참조를 반환함.
push()	스택의 제일 상단에 요소를 삽입함.
pop()	스택의 제일 상단에 있는 요소를 삭제함.

다음 예제는 스택 컨테이너를 사용하여 10진수를 2진수로 변환하는 예제.

int decimal = 123;
stack<int> st;

// 10진수를 2진수로 변환
do 
{
    st.push(decimal % 2);
    decimal /= 2;
} while(decimal);

// 스택의 모든 요소를 인출
while(!st.empty())
{
    cout << st.top();
    st.pop();
}

// 결과 : 1111011

큐(queue)

큐(queue) 컨테이너는 deque 클래스의 인터페이스를 제한하여, 전형적인 큐 메모리 구조의 인터페이스를 제공한다.

큐 컨테이너는 queue 헤더 파일에 정의되어 있다. 큐 메모리 구조는 선형 메모리 공간에 데이터를 저장하면서 선입선출(FIFO)의 시멘틱을 따르는 자료 구조이다. 가장 먼저 저장된(push) 데이터가 가장 먼저 인출(pop)되는 구조.

큐 컨테이너는 큐 메모리 구조를 표현하기 위해 다음과 같은 멤버 함수를 제공한다.

empty()	큐가 비어 있으면 true를, 비어 있지 않으면 false를 반환함.
size()	큐 요소의 총 개수를 반환함.
front()	큐의 맨 앞에 있는(제일 먼저 저장된) 요소에 대한 참조를 반환함.
back()	큐의 맨 뒤에 있는(제일 나중에 저장된) 요소에 대한 참조를 반환함.
push()	큐의 맨 뒤에 요소를 삽입함.
pop()	큐의 맨 앞의 요소를 삭제함.

다음 예제는 큐 컨테이너를 사용하여 정해진 수만큼의 피보나치 수열을 출력하는 예제.

int n = 20;  // 20개의 피보나치 수열을 출력함.
queue<int> que;
que.push(0); // 초깃값인 0과 1을 저장함.
que.push(1);

// 피보나치 수열
for(int i = 2; i < n; i++)
{
    int temp = que.front();
    cout << temp << " ";
    que.pop();
    que.push(temp + que.front());
}

// 결과 : 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597

우선순위 큐(priority_queue)

우선순위 큐(priority_queue) 컨테이너는 큐와는 달리 큐의 맨 앞의 요소로 가장 먼저 저장된 요소가 아닌, 가장 큰 값을 지닌 요소가 위치하게 된다. 또한, 큐가 deque 클래스를 기반으로 하는 것과는 달리, 우선순위 큐는 vector 클래스를 기반으로 한다. 하지만 사용할 수 있는 멤버 함수는 큐 컨테이너와 같습니다. 우선순위 큐 컨테이너는 queue 헤더 파일에 정의되어 있다.

 

다음 예제는 우선순위 큐의 동작 방식을 보여주는 예제.

priority_queue<int> pq;

pq.push(10);
pq.push(20);
pq.push(100);
pq.push(3);

// 우선순위 큐의 모든 요소를 인출
while(!pq.empty())
{
    cout << pq.top() << " ";
    pq.pop();
}

// 결과 : 100 20 10 3

출처 : http://www.tcpschool.com/cpp/cpp_container_adapter