STL 학습 - Stack / Queue 편

3890 단어 QueuestackSTL
STL 학습 - Stack / Queue 편
Stack
  • stack 은 선진 적 인 데이터 구조 로 하나의 출구 만 있 고 stack 은 새로운 요 소 를 추가 하고 요 소 를 제거 하 며 최상 위 요 소 를 얻 을 수 있 습 니 다.그러나 맨 위 를 제외 하고 stack 의 다른 요 소 를 액세스 할 수 있 는 방법 은 없다.옮 겨 다 니 는 행 위 를 허용 하지 않 는 다 는 것 이다.
  • stack 실현 은 용 기 를 바닥 구조 로 하고 용기 의 인 터 페 이 스 를 바 꾸 어 '선진 선 출' 특성 에 부합 시 키 면 스 택 이 형성 된다.구체 적 으로 실현 하면 밑부분 deque 의 머리 끝 을 닫 을 수 있 고 stack 을 실현 할 수 있 습 니 다.stack 은 '어떤 물건 의 인 터 페 이 스 를 수정 하여 다른 모습 을 형성 하 는' 성질 을 가지 기 때문에 '어댑터' 라 고 부른다.stack 은 container adapter 로 분 류 됩 니 다.stack 에는 교체 기 가 없어 방문 기능 을 제공 하지 않 습 니 다.이 밖 에 stack 은 list 를 바 텀 용기 로 사용 할 수 있다.다음은 stack 의 소스 코드 분석 입 니 다.
    template <class _Tp, class _Sequence>
class stack {
...
public:
  typedef typename _Sequence::value_type      value_type;
  typedef typename _Sequence::size_type       size_type;
  typedef          _Sequence                  container_type;

  typedef typename _Sequence::reference       reference;
  typedef typename _Sequence::const_reference const_reference;
protected:
  _Sequence c;        //     
public:
  //       Squence c  ，  stack   
  stack() : c() {}
  explicit stack(const _Sequence& __s) : c(__s) {}
  //       
  bool empty() const { return c.empty(); }
  //        
  size_type size() const { return c.size(); }
  //         
  reference top() { return c.back(); }
  const_reference top() const { return c.back(); }
  //     
  void push(const value_type& __x) { c.push_back(__x); }
  //     
  void pop() { c.pop_back(); }
};
//      
template <class _Tp, class _Seq>
bool operator==(const stack<_Tp,_Seq>& __x, const stack<_Tp,_Seq>& __y)
{
  return __x.c == __y.c;
}
//      
template <class _Tp, class _Seq>
bool operator<(const stack<_Tp,_Seq>& __x, const stack<_Tp,_Seq>& __y)
{
  return __x.c < __y.c;
}
...

    • Queue
  • 개술 quue 는 선진 적 인 데이터 구조 이다.그것 은 출구 가 두 개 있다.이것 은 요 소 를 추가 하고 요 소 를 제거 하 며 맨 밑 에 요 소 를 추가 하여 맨 위 요 소 를 얻 을 수 있 습 니 다.맨 밑 에 요 소 를 넣 고 맨 위 에 요 소 를 제거 하 는 것 외 에 quue 의 다른 요 소 를 액세스 할 방법 이 없습니다.옮 겨 다 니 는 작업 도 존재 하지 않 는 다.
  • queue 를 실현 하 는 것 도 용 기 를 밑부분 구조 로 하고 인 터 페 이 스 를 바 꾸 어 선진 적 인 선 출 특성 에 부합 시 켜 queue 를 형성한다.그 실현 은 deque 의 저급 출구 와 전단 입 구 를 폐쇄 하면 quue 를 쉽게 실현 할 수 있다.quue 도 '어떤 물건 의 인 터 페 이 스 를 수정 하여 다른 모습 을 형성 하 는' 성질 을 가지 기 때문에 어댑터 이기 도 한다.그것 도 용기 어댑터 로 분류 된다.그것 도 교체 기 가 존재 하지 않 기 때문에 옮 겨 다 니 는 작업 을 할 수 없다.다음은 quue 의 소스 코드 분석 입 니 다.
    template <class _Tp, class _Sequence>
class queue {
...
public:
  typedef typename _Sequence::value_type      value_type;
  typedef typename _Sequence::size_type       size_type;
  typedef          _Sequence                  container_type;

  typedef typename _Sequence::reference       reference;
  typedef typename _Sequence::const_reference const_reference;
protected:
  _Sequence c;            //     
public:
  queue() : c() {}
  explicit queue(const _Sequence& __c) : c(__c) {}
  //         
  bool empty() const { return c.empty(); }
  //        
  size_type size() const { return c.size(); }
  //       
  reference front() { return c.front(); }
  const_reference front() const { return c.front(); }
  //       
  reference back() { return c.back(); }
  const_reference back() const { return c.back(); }
  // deque      ，queue    ，   （       ）
  //     
  void push(const value_type& __x) { c.push_back(__x); }
  //     
  void pop() { c.pop_front(); }
};
//         
template <class _Tp, class _Sequence>
bool 
operator==(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y)
{
  return __x.c == __y.c;
}
//       
template <class _Tp, class _Sequence>
bool
operator<(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y)
{
  return __x.c < __y.c;
}
...
  • 참고 문헌 STL 소스 코드 분석 - 후 제 STL 소스 코드
    • [HackerRank SQL] Population Density Difference
    면접 문 제 를 나 누 면 많은 사람들 이 걸 릴 것 같다.

    좋은 웹페이지 즐겨찾기

    개발자 우수 사이트 수집

    개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
    best100-homepage