STL 용기 어댑터 의 stack, queue 구현

stack
stack 은 교체 기 가 없 는 것 이 고 STL 은 모든 용기 에 하나의 교체 기 를 내장 해 야 하기 때문에 stack 은 용기 가 아 닙 니 다.스 택 은 선진 적 인 데이터 구조 로 한 스 택 의 삽입, 삭제 또는 수 치 는 스 택 꼭대기 에서 만 이 루어 질 수 있 고 요소 가 팝 업 되 지 않 는 전제 에서 내부 의 모든 요 소 를 옮 겨 다 닐 수 없습니다.스 택 의 특성 에 따라 스 택 꼭대기 요 소 는 반드시 마지막 으로 들 어 가 는 요소 여야 합 니 다. 이 점 에 따라 우 리 는 쉽게 결론 을 얻 을 수 있 습 니 다. 말단 삽입 push_back, 삭제 pop_back, 방문 back 은 모두 stack 용기 에 의 해 포장 되 고 수식 되 는 것 을 말 합 니 다. 포장 은 stack 대상 을 통 해 봉 인 된 바 텀 용 기 를 직접 방문 할 수 없습니다.수식 이란 stack 이 바 텀 용 기 를 포장 할 때 필요 한 인 터 페 이 스 를 제공 하여 사용자 의 수 요 를 만족 시 키 는 것 을 말한다.우 리 는 어댑터 에 봉 인 된 밑바닥 용 기 를 기초 용기 라 고 부른다
어댑터 는 원시 사물 을 한 번 에 포장 하고 수식 할 수 있 으 며 다른 인 터 페 이 스 를 제공 할 수 있다. 이 인 터 페 이 스 는 사용자 의 수 요 를 더욱 잘 만족 시 키 고 일정한 전일 성 을 가진다.
이전에 배 운 순서 용기 에서 말단 의 삽입, 삭제, 접근 조작 을 제공 할 수 있 으 면 stack 어댑터 의 기초 용기 로 사용 할 수 있 기 때문에 vector, list, deque 모두 stack 의 기초 용기 로 사용 할 수 있 습 니 다. stack 의 기본 적 인 기초 용 기 는 deque,
stack 에 대해 우리 가 일반적으로 제공 해 야 할 인터페이스 함 수 는 다음 과 같다.

스 택 에 있 는 현재 요소 의 개 수 를 가 져 옵 니 다 size_type size();

창고 꼭대기 원소 획득 T top();

입고 void push(const T &t);

출고 void pop();

빈 창고 여 부 를 판단 bool empty();

STL 이 정의 하 는 용기 어댑터 stack 을 사용 하려 면 stack 헤더 파일 #include 을 참조 해 야 합 니 다.
stack 의 소스 코드

밑바닥 은 deque

#include
#include
using namespace std;

stack 어댑터 의 정의

template<class T,class Sequence=deque<T> >
class stack
{
	friend bool operator==(const stack&,const stack&);//friend       ，  private   
	friend bool operator<(const stack&,const stack&);//    ，    ，     friend
	public:
		typedef typename Sequence::value_type value_type;//typename    ,    
		typedef typename Sequence::size_type size_type;//    
		typedef typename Sequence::reference reference;//    
		typedef typename Sequence::const_reference const_reference;//     
	protected:
		Sequence c;//       ，  deque
	public:
		bool empty()const;//    
		size_type size()const;//  
		reference top();//     
		const_reference top()const;
		void push(const value_type &x);//  
		void pop();//  
};

각 함수 인터페이스의 클래스 외 실현

template<class T,class Sequence>
bool operator==(const stack<T,Sequence> &x, const stack<T,Sequence> &y)//           
{
	return x.c==y.c;
}
 
template<class T,class Sequence>
bool operator<(const stack<T,Sequence>& x,const stack<T,Sequence>& y)//     x       y
{
	return x.c<y.c;
}
template<class T,class Sequence>
bool stack<T,Sequence>::empty()const//            const   
{
	return c.empty();
}
template<class T,class Sequence>//         
//    size_type stack::size()const    ，  size_type       ， typename     
typename stack<T,Sequence>::size_type stack<T,Sequence>::size()const
{
	return c.size();
}
template<class T,class Sequence>
typename stack<T,Sequence>::reference stack<T,Sequence>::top()//                
{
	return c.back();
}
template<class T,class Sequence>
typename stack<T,Sequence>::const_reference stack<T,Sequence>::top()const//top     
{
	return c.pop_back();
}
template<class T,class Sequence>
void stack<T,Sequence>::push(const value_type & x)//                 
{
	c.push_back(x);
}
template<class T,class Sequence>
void stack<T,Sequence>::pop()//                 
{
	c.pop_back();
}

queue
quue 내부 에 교체 기 가 없 기 때문에 quue 기능 을 실현 할 수 있 는 용 기 는 모두 바 텀 용기 로 포장 하고 수식 할 수 있 습 니 다. 본질 적 으로 어댑터 대열 의 특징 은 먼저 나 가 고 팀 꼬리 에서 팀 의 첫 번 째 팝 업 을 삽입 하 는 것 입 니 다. 그래서 pop_front 용기 가 바 텀 용기 로 적합 하지 않 고 vector deque, list 가 적합 합 니 다. 기본 적 으로 deque 입 니 다.
quue 가 제공 하 는 동작 은 다음 과 같 습 니 다. (1) 현재 대기 열 에 있 는 요소 의 개 수 를 가 져 옵 니 다.size_type size() (2) 팀 의 첫 번 째 요소 (팝 업 하지 않 음) T & front() (3) 팀 의 꼬리 요소 (팝 업 하지 않 음) T & back() (4) 입단 작업 void push(const T &t) (5) 팀 이탈 작업 void pop() (6) 대기 열 이 비어 있 는 지 판단 bool empty() 역시 quue 필요 #include소스 코드 구현

deque 는 밑바닥 용기

#include
#include
using namespace std;

queue 의 정의

#include
#include
using namespace std;
 
/****************queque   *************/
template<class T,class Sequence=deque<T> >
class queue
{
	friend bool operator==(const queue& x,const queue& y);
	friend bool operator<(const queue&x,const queue& y);
	/****************     queue    *********************/
	public:
		typedef typename Sequence::value_type value_type;//      
		typedef typename Sequence::size_type  size_type;//    
		typedef typename Sequence::reference  reference;//    
		typedef  typename Sequence::const_reference const_reference;//     
	protected:
		Sequence c;//    
		/*************queue     ****************/
	public:
		bool empty()const;//      
		size_type size()const;//    
		reference front();//      
		const_reference front()const;
		reference back();//      
		const_reference back()const ;
		void push(const value_type& x);//   
		void pop();//    
};

queue 류 외 실현

template<class T,class Seq>
bool queue<T,Seq>::empty()const//          ,const            
{
	return c.empty(); 
}
 
template<class T,class Seq>
typename queue<T,Seq>::size_type queue<T,Seq>::size()const//          
{
	return c.size();
}
 
template<class T,class Seq>
typename queue<T,Seq>::reference queue<T,Seq>::front()//      
{
	return c.front();
}
 
template<class T,class Seq>
typename queue<T,Seq>::const_reference queue<T,Seq>::front()const//          
{
	return c.front();
}
 
template<class T,class Seq>
typename queue<T,Seq>::reference queue<T,Seq>::back()//        
{
	return c.back();
}
 
template<class T,class Seq>
typename queue<T,Seq>::const_reference queue<T,Seq>::back()const//        
{
	return c.back();
}
 
template<class T,class Seq>
void queue<T,Seq>::push(const value_type& t)//   
{
	c.push_back(t);
}
 
template<class T,class Seq>
void queue<T,Seq>::pop()//   
{
	c.pop_front();
}

테스트 코드

int main()
{
	queue<int> q;
	q.push(1);
	q.push(2);
	q.push(3);
	q.push(4);
	while(!q.empty())
	{
		cout<<"size="<<q.size()<<" ";
		cout<<q.front()<<endl;
		q.pop();
	}
	return 0;
}