STL源码笔记（13）—序列式容器之栈和队列

ゝ一世哀愁。 2022-08-21 09:41 198阅读 0赞

# STL源码笔记（13）—序列式容器之栈和队列 #

## 栈stack ##

栈这种数据结构的特点就是后进先出/先进后出，他只能从一个口进一个口出，因为其特性，对应了其两个重要的操作压栈弹栈也就是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时用list作为模板实参替换，书中也给出例子），我们知道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
    };

## 队列queue ##

栈和队列这两兄弟是吧，队列的特性是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莫属了（list的实现书中也给出，修改模板实参即可），因此queue也是一个**`配接器adapter`**，类似于stack的STL实现，其方法都是直接调用deque的方法，然后就是和stack一样，queue只能在一端插入，一端删除，符合“先进先出”的条件，因此queue也不提供迭代器和遍历功能。

//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(); }
    };