STL 소스 노트 (13) - 시퀀스 용기 스 택 과 대기 열

STL 소스 노트 (13) - 시퀀스 용기 스 택 과 대기 열
창고
스 택 이라는 데이터 구조의 특징 은 바로 후진 선 출 / 선진 후 출 이다. 그 는 한 입 에서 한 입 만 들 어 갈 수 있다. 그 특성 때문에 두 가지 중요 한 조작 스 택 인 push () 와 pop () 에 대응 하고 SGI STL 소스 코드 를 떠 나 한 마디 도 맞지 않 기 때문에 먼저 간단 한 것 을 써 보 았 다.

#include <iostream>
#include<deque>
#include <algorithm>
#include <vector>
using namespace std;
#define STACKSIZE 20//   
template <typename T>
class MyStack{
private:
    T array[STACKSIZE];//        
    int index;
public:
    MyStack()
    {
        index = -1; //   
    }
    int  size(){ return (index + 1); }//      
    bool empty(){ return index == -1; }//    
    void push(T value);//  
    void pop();//  
    T& top();//      
};

template <typename T>
T& MyStack<T>::top()
{
    return array[index];
}
template <typename T>
void MyStack<T>::push(T value)
{
    array[++index] = value;
}
template <typename T>
void MyStack<T>::pop()
{
    if (!this->empty())
    {
        --index;
    }
    else
    {
        cerr << "stack is empty" << endl;
    }
}

int main()
{
    MyStack<int> mystack;
    mystack.push(1);
    mystack.push(2);
    mystack.push(3);
    cout << "size="<<mystack.size() << endl;//   3
    int tmp = mystack.top();
    cout << tmp << endl;//  3
    mystack.pop();
    mystack.pop();
    mystack.pop();
    mystack.pop();//   stack is empty
    if (mystack.empty())
    {
        cout << "myStack is empty" << endl;//   myStack is empty
    }

    system("pause");
    return 0;
}

STL 소스 코드 에서 stack 의 내용 은 이전의 vector, deque, list 만큼 많 지 않 습 니 다. 그 이 유 는 stack 의 바 텀 이 기본적으로 deque 를 용기 로 하기 때 문 입 니 다.책 에 따 르 면 stack 은 상단 에서 만 작 동 하기 때문에 stack 은 옮 겨 다 니 는 행 위 를 허용 하지 않 고 stack 도 교체 기 가 없다.stack 처럼 ， 의 성질 을 가 진 사람 은 adapter (어댑터) 라 고 불 린 다.따라서 STL stack 이 container adpter 로 분류 되면 SGI STL 소스 코드 는 간단 합 니 다.

//stl_stack.h
template <class _Tp, 
          class _Sequence __STL_DEPENDENT_DEFAULT_TMPL(deque<_Tp>) >
class stack;//  ， deque       

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:
  stack() : c() {}//            
  explicit stack(const _Sequence& __s) : c(__s) {}//      

  bool empty() const { return c.empty(); }//      empty
  size_type size() const { return c.size(); }//      size
  reference top() { return c.back(); }//      back
  const_reference top() const { return c.back(); }
  void push(const value_type& __x) { c.push_back(__x); }//    push_back
  void pop() { c.pop_back(); }//    pop_back
};

대기 열 큐
창고 와 대열 이라는 두 형 제 는 그 렇 죠? 대열 의 특성 은 FIFO 가 먼저 나 가 줄 을 서서 밥 을 먹 는 상황 을 상상 하면 대열 의 작업 체 제 를 쉽게 볼 수 있 고 대열 이 쌍방 향 으로 입 을 열 었 다 는 것 을 알 수 있 습 니 다. 팀 의 머리 는 이쪽 에서 나 오고 팀 의 끝 은 이쪽 에서 들 어 갑 니 다.
한 가지 상황 을 고려 하 다.
한 무리의 사람들 이 줄 을 서서 밥 을 짓 고 앞 에 있 는 사람들 이 밥 을 먹고 떠 난 후에 (팀 을 나 가) 뒤에 있 는 사람들 은 앞으로 나 아가 빈 자 리 를 메 워 야 한다. 이런 행 위 는 우리 의 정상 적 인 논리 적 사고 에 부합된다. 그러나 이 일 을 컴퓨터 에 맡 기 면 그의 시간 복잡 도 는 상수 시간 으로 완성 할 수 있 는 것 이 아니 라 사실상 이동 요소 의 시간 복잡 도 는 O (n) 이다.만약 대열 에 원소 수가 비교적 많 을 때 출대 조작 은 매우 비효 율 적일 것 이다.입 대 · 출 대 작업 이 모두 상수 시간 내 에 진행 되 기 위해 서 대기 열 은 front (팀 헤드) 와 rear (팀 꼬리) 색인 을 유지 하 는 것 입 니 다. 이렇게 하면 이동 색인 을 통 해 상수 시간 내 에 대기 열 을 조작 할 수 있 습 니 다.
한 가지 상황 을 다시 고려 하 다.
만약 에 당신 이 줄 을 서 있 은 후에 (줄 을 나 가) 바로 대열 에 들어간다 고 가정 하면 대열 이 허용 하 는 최대 요소 범위 내 에서 이 일련의 조작 은 순환 하 는 것 입 니 다. 순환 대기 열 이 잖 아 요. 그러면 당신 의 요소 가 끊임없이 괴 롭 히 고 대열 의 크기 가 실제 적 으로 변 하지 않 았 다 는 것 을 의미 합 니 다. 그러나 이렇게 하면 front 와 rear 는 배열 아래 표 시 된 최대 치 까지 계속 이동 할 수 있 습 니 다.이렇게 하면 반드시 모형 을 뽑 고 다시 앞으로 돌아 가 야 한다. 이렇게 하면 팀 이 비어 있 고 팀 이 꽉 차 며 팀 에 들 어가 서 작업 을 할 때 반드시 모형 을 뽑 는 연산 을 더 해 야 한다. 일반적으로 말 하면:

rear=(rear+1)%QUEUESIZE;

front=(front+1)%QUEUESIZE;

(rear+1)%QUEUESIZE==front;

rear==front;

(rear-front+QUEUESIZE)%QUEUE;

그래서 스스로 대기 열 을 써 보 았 습 니 다.

#define QUEUESIZE 20 //          QUEUESIZE-1
template <typename T>
class MyQueue{
private:
    int front;//  
    int rear;//  
    T array[QUEUESIZE];
public:
    MyQueue()
    {
        rear = 0;
        front = 0;
    }
    bool empty(){ return rear == front; }
    bool isFull(){ return (rear + 1) % QUEUESIZE == front; }
    int size(){ return (rear - front + QUEUESIZE) % QUEUESIZE; }
    void push(T&t);//  
    T pop();//  
};

template <typename T>
void MyQueue<T>::push(T&t)
{
    if (!isFull())
    {
        cout << t << "is enqueue" << endl;
        array[rear]=t;
        rear = (rear + 1) % QUEUESIZE;
    }
    else
    {
        cerr << "queue is full" << endl;
    }
}
template <typename T>
T MyQueue<T>::pop()
{
    if (!empty())
    {
        int tmp = front;
        front = (front + 1) % QUEUESIZE;
        return array[tmp];
    }
    else
    {
        cerr << "queue is empty" << endl;
        return -1;
    }
}
int main()
{
    MyQueue<int> q;
    for (int i = 0; i < 20; i++)
    {
        q.push(i);
    }
    cout << q.size() << endl;
    for (int i = 0; i < 20; i++)
    {
        if (!q.empty())
        {
            int t = q.pop();

            cout << t << "is dequeue" << endl;
        }
    }
    system("pause");
    return 0;
}

STL 에 서 는 대기 열 양 방향 으로 시작 하 는 특성 상 기본 바 텀 용기 도 deque 가 아 닙 니 다.'선진 선 출' 의 조건 이기 때문에 quue 도 교체 기와 옮 겨 다 니 는 기능 을 제공 하지 않 습 니 다.

//stl_queue.h
template <class _Tp, 
          class _Sequence __STL_DEPENDENT_DEFAULT_TMPL(deque<_Tp>) >
class queue;//  ，    deque

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(); }
  void push(const value_type& __x) { c.push_back(__x); }
  void pop() { c.pop_front(); }
};