컨테이너 어댑터
컨테이너 어댑터(container adapter)
컨테이너 어댑터(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
f(n) = 1, n<=2일때
f(n) = f(n-1) + f(n-2), n>2일때
따라서 큐를 사용하는 것보다 재귀 호출을 통해 프로그램을 구현하는 편이 더욱 간단합니다.
우선순위 큐(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
위의 예제에서 볼 수 있듯이 우선순위 큐의 요소는 언제나 값의 내림차순으로 정렬되게 됩니다.
