컨테이너 어댑터는 기존 컨테이너의 기능 중 일부만을 공개하여 기능이 제한되거나 변형된 컨테이너를 만든다. 기존 컨테이너의 구현 중 일부는 그대로 사용하되 외부에서 사용하는 인터페이스만 변경하는 것이다. STL은 스택, 큐, 우선 순위 큐 세 가지의 컨테이너를 어댑터로 제공한다.
스택이라는 자료 구조는 선형적인 기억 공간에 자료를 저장하되 반드시 넣은 역순으로 빼기(LIFO)를 할 수 있다. 그래서 기억 공간을 관리하는 능력과 넣기와 빼기 정도의 동작만 제공하면 쉽게 만들 수 있다. 임의 위치를 액세스한다거나 중간에서 삽입, 삭제하는 동작은 필요하지 않으며 스택이 이를 요구하지도 않는다.
스택은 벡터나 리스트에 비해서는 제공해야 할 기능 목록이 단순한 편인데 이런 컨테이너를 처음부터 다시 만들 필요없이 기존 컨테이너의 기능을 빌려서 구현할 수 있다. 기억 장소를 관리하는 기능은 시퀀스 컨테이너가 아주 훌륭하게 제공하고 있으므로 이 컨테이너들의 힘을 빌리고 스택은 필요한 인터페이스만 공개하면 되는 것이다. 스택의 템플릿 정의는 다음과 같다.
template<class T, class Cont=deque<T> >
class stack { ... }
두 개의 인수를 받아들이는데 스택에 들어갈 데이터 타입 T와 스택이 자료 저장을 위해 사용할 컨테이너 Cont이다. 이때 Cont는 스택의 요소 타입과 같은 타입을 저장하는 컨테이너여야 한다. Cont의 디폴트는 데크로 되어 있는데 원한다면 벡터나 리스트로 변경할 수도 있다. 시퀀스가 동적인 기억 장소 관리 기능을 제공하므로 이렇게 만들어진 스택의 크기는 사실상 무한하다고 할 수 있다.
스택이 제공하는 타입은 size_type, value_type, container_type 세 가지 밖에 없다. 이중 container_type은 스택이 자료 관리를 위해 사용하는 기본 컨테이너의 타입이며 템플릿 인수 Cont와 같은 타입이다. 생성자는 다음 하나밖에 없다.
explicit stack(const allocator_type& al = allocator_type());
인수로 할당기를 받을 수 있지만 디폴트가 지정되어 있으므로 결국 이 생성자는 인수를 취하지 않는 디폴트 생성자라고 할 수 있다. 스택은 만들자 마자 비어 있어야 하므로 초기화하는 방법이 별다른 게 없는 셈이다. stack<T> s; 식으로 저장할 타입만 템플릿 인수로 지정하면 된다.
스택의 고유한 동작은 push, pop, top 세 가지 뿐이다. 그 외의 불필요한 연산, 예를 들어 중간에 삽입, 삭제한다거나 구간 복사를 하는 기능은 숨겨서 쓸 수 없도록 되어 있다. 중간에 삽입, 삭제가 가능하면 그것은 더 이상 스택이 아니다. top은 상수, 비상수 버전이 따로 제공된다.
void push(const T& x);
void pop();
value_type& top();
const value_type& top() const;
push는 스택의 상단에 값을 추가하는데 인수로 추가할 값을 전달하면 된다. 기억 장소가 무한해서 추가는 항상 성공하므로 리턴값은 없다. pop은 상단의 값을 제거하여 버리는데 이 값은 가장 최근에 추가된 값이다. 스택에 값이 없는 상태에서는 pop을 해서는 안되는데 pop은 리턴값이 없으므로 이런 에러를 처리할 수 없다. 대신 대부분의 컴파일러에서 빈 스택에 대해 pop을 호출하면 assert가 호출되도록 되어 있다.
top은 스택 상단의 값을 읽어 레퍼런스로 리턴한다. 상수 버전과 비상수 버전이 따로 준비되어 있다. 시스템 스택을 비롯한 일반적인 스택은 값을 읽는 함수와 버리는 함수가 따로 제공되지 않으며 pop 함수를 호출하면 제일 상단의 값을 제거하면서 리턴하도록 되어 있는데 STL의 스택은 읽는 함수와 제거하는 함수가 분리되어 있다. 스택이라는 자료 구조의 원론을 지키지 않고 있는 셈인데 임의 타입에 대해 동작해야 하기 때문이다.
만약 pop이 상단 요소를 제거함과 동시에 레퍼런스를 리턴한다고 해 보자. 이렇게 되면 이미 제거되어 버린 요소를 가리키는 무효한 레퍼런스를 리턴하는 셈이므로 논리적으로 모순이다. 레퍼런스가 유효하려면 대상체가 건재하게 남아 있어야 한다. 빼내면서 동시에 리턴하려면 값을 리턴하는 수밖에 없으며 시스템 스택은 실제로 값을 리턴한다. 그러나 STL의 스택은 int, double같은 기본 타입뿐만 아니라 사용자 정의 타입을 포함한 임의의 타입을 다룰 수 있어야 하는데 이런 타입을 값으로 리턴하면 복사가 발생하므로 엄청난 효율 저하를 감수해야 한다.
그래서 값을 리턴하는 것은 바람직하지 않으며 어쨌든 레퍼런스를 리턴해야 하는 것이다. 요소가 아직 스택에 남아 있는 상태에서 레퍼런스를 리턴하는 top 함수를 따로 두고 다 사용한 요소를 제거하는 pop 함수를 따로 제공하면 문제가 해결된다. 상단의 값을 읽고 버리려면 일단 top으로 먼저 읽어서 사용하고 pop으로 빼서 버리는 것은 따로 해야 한다. 일반적인 기대와는 다르고 다소 번거롭지만 대신에 일반성을 얻을 수 있다.
이 외에 스택의 크기를 조사하는 size와 스택이 비어 있는지를 조사하는 empty 멤버 함수가 제공된다. 이 함수들이 스택이 제공하는 함수의 전부이다. 간단한 예제를 만들어 보자.
|
예 제 : stack |
#include <iostream>
#include <stack>
using namespace std;
void main()
{
stack<int> s;
s.push(4);
s.push(7);
s.push(2);
while (!s.empty()) {
cout << s.top() << endl;
s.pop();
}
}
정수형 스택 s를 만들고 세 개의 값을 밀어 넣은 후 다시 빼 보았다. top으로 읽고, pop으로 버리기를 스택이 빌 때까지 반복하면 된다. 템플릿의 두 번째 인수를 지정하면 s를 다음과 같이 선언할 수도 있다. 물론 사용하는 컨테이너의 헤더 파일은 적절히 인클루드해야 한다.
stack<int, vector<int> > s;
stack<int, list<int> > s;
데크나 벡터, 리스트 모두 스택을 위한 자료 관리는 충분히 제공하므로 어떤 컨테이너를 사용하나 근소한 속도 차이외에는 별다를 게 없다. 심지어 이미 작성되어 있는 스택의 기본 컨테이너를 다른 것으로 바꿔도 잘 컴파일되고 훌륭하게 동작한다. 스택이 사용하는 인터페이스가 세 시퀀스가 제공하는 기능의 교집합으로 제한되어 있기 때문에 말썽이 생길 여지가 없다.
19장에서 C로 계산기 예제를 만들어 보았고 31장에서 다시 스택 템플릿을 이용한 계산기를 만들어 보았는데 STL의 stack 클래스를 사용해서 만들 수도 있다. 지면 관계로 인해 소스의 일부부만 보이는데 관심있는 사람은 직접 수정해 보기 바란다.
|
예 제 : stlcalc |
#include <Turboc.h>
#include <math.h>
#include <stack>
using namespace std;
....
void MakePostfix(char *Post, const char *Mid)
{
stack<char> cS;
....
while (!cS.empty() && GetPriority(cS.top()) >= GetPriority(*m)) {
*p++=cS.top();
cS.pop();
}
....
stack 헤더 파일을 인클루드하고 스택 선언문은 stack<char> 타입으로 수정하며 Pop을 pop과 top의 조합으로만 변경하면 된다. 그리고 GetTop()!=-1을 !empty() 호출로만 수정하면 동일하게 동작하는 실행 파일을 얻을 수 있다. 언어가 제공하는 표준 라이브러리를 사용했으므로 이해하기도 쉽고 소스 분량도 훨씬 줄일 수 있어 여러 모로 좋다.