STL 용기 어댑터 quue 구현 프레임 워 크

설명: 본 고 는 학습 교류 만 제공 합 니 다. 전재 출처 를 표시 해 주 십시오. 전재 환영 합 니 다!
         이전 글 에서 STL 의 용기 어댑터 stack 의 실현 프레임 워 크 는 STL 이 기초 용 기 를 통 해 자주 사용 하 는 데이터 구조 stack (스 택) 을 어떻게 실현 하 는 지 소개 했다. 본 고 는 다른 STL 내부 에서 정의 하 는 또 다른 STL 용기 어댑터 quue (대기 열) 를 소개 한다.
        데이터 구 조 를 접 한 사람 에 게 대기 열 은 낯 설 지 않 습 니 다. FIFO (first in first out) 의 데이터 구조 입 니 다. 스 택 에 비해 대기 열의 차이 점 은 다음 과 같 습 니 다. (1) 대기 열 은 선진 적 으로 먼저 나 온 데이터 구조 이 고 스 택 은 후진 적 으로 먼저 나 오 는 수치 구조 입 니 다. (2) 대기 열 은 앞 뒤 양쪽 의 방문 작업 을 지원 하 며 스 택 은 한 끝 (즉 정상) 만 지원 합 니 다.스 택 의 삽입 과 팝 업 은 스 택 꼭대기 에 있 습 니 다. 물론 용기 어댑터 quue 와 stack 은 옮 겨 다 니 는 작업 을 지원 하지 않 고 내부 에 교체 기 를 제공 하지 않 는 다 는 공통점 이 있 습 니 다.
        위의 비교 에서 우 리 는 이 두 어댑터 가 기초 용기 에 대한 요구 가 다르다 는 것 을 추측 할 수 있다. 위 에서 언급 한 제 (3) 점 과 같다. queue 의 기초 용 기 는 첫 번 째 에서 튀 어 나 올 수 있 도록 지원 해 야 하고 stack 의 기초 용 기 는 꼬리 에서 튀 어 나 올 수 있 도록 지원 해 야 한다. 다시 말 하면 queue 의 기초 용 기 는 pop front () 를 지원 해 야 한다.작업, stack 의 기본 용 기 는 pop back () 작업 을 지원 해 야 합 니 다. 이 때문에 순서 용기 vector, list, deque 는 stack 의 기본 용기 로 사용 할 수 있 으 며, list 와 deque 는 quue 의 기본 용기 로 사용 할 수 있 으 며, vector 는 quue 의 기본 용기 (vector) 로 서 pop front () 작업 을 제공 하지 않 습 니 다. 이 두 어댑터 의 기본 기본 용 기 는 모두 deque 입 니 다.
        stack 과 quue 작업 의 차이 에 따라 stack 과 quue 가 제공 하 는 작업 의 차 이 를 비교 분석 할 수 있 습 니 다.
        quue 가 제공 하 는 동작 은 다음 과 같 습 니 다.
       (1) 현재 대기 열 에 있 는 요소 의 개 수 를 가 져 옵 니 다. size type size (), stack 도 이 동작 을 제공 합 니 다.
       (2) 팀 의 첫 번 째 요 소 를 가 져 옵 니 다 (팝 업 하지 않 음). T & front (), stack 은 이 동작 을 제공 하지 않 습 니 다.
       (3) 팀 의 꼬리 요 소 를 가 져 옵 니 다 (팝 업 하지 않 음). T & back (), stack 에 대응 하 는 함 수 는 T & top () 입 니 다.
       (4) 입단 작업. void push (const T & t), stack 도 같은 함 수 를 제공 하여 스 택 작업 에 대응 합 니 다.
       (5) 파티 작업. void pop (), stack 도 같은 함 수 를 제공 하여 스 택 작업 에 대응 합 니 다.
       (6) 대기 열 이 비어 있 는 지 판단 합 니 다. bool empty (), stack 도 같은 함 수 를 제공 합 니 다.
         STL 에서 정의 하 는 quue 어댑터 를 사용 하려 면 quue 헤더 파일 을 참조 해 야 합 니 다. \ # include < quue >.
         다음은 quue 어댑터 의 실현 코드 와 테스트 코드 를 드 립 니 다.

#include<iostream>
#include<deque>
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;
}

참고 자료
[1] 《 STL 소스 분석 후 첩 》
[2] 'C + + Primer 4 판'