[C++] STL_stack && queue接口的模拟实现

小灰灰 2024-02-18 12:56 40阅读 0赞

![在这里插入图片描述][59f58cd657d4419db0b643ae0cca17ba.gif_pic_center]

#### 文章目录 ####

*  1、stack
 *   *  1.1 stack的介绍
     *   *  1.2.1 stack的构造
         *  1.2.2 进、出栈等接口的模拟实现
 *  2、queue
 *   *  2.1 queue的介绍
     *  2.2 queue的使用
     *   *  2.2.1 queue构造
         *  2.2.2 入、出队等接口的模拟实现

## 1、stack ##

### 1.1 stack的介绍 ###

[stack的文档介绍][stack]  
![在这里插入图片描述][1d8ab7ba6d5e4cf4921cd32490486d42.png]

> 1. stack是一种容器适配器，专门用在具有**后进先出** 操作的上下文环境中，其删除只能从容器的一端进行元素的插入与提取操作。  
> 2. stack是作为容器适配器被实现的，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定的成员函数来访问其元素，将特定类作为其底层的，元素特定容器的尾部(即栈顶)被压入和弹出。  
> 3. stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类，这些容器类应该支持以下操作： empty：判空操作 back：获取尾部元素操作 push\_back：尾部插入元素操作 pop\_back：尾部删除元素操作  
> 4. 标准容器vector、deque、list均符合这些需求，**默认情况下，如果没有为stack指定特定的底层容器，默认情况下使用deque。**

1.2 stack的使用

<table> 
 <thead> 
  <tr> 
   <th>函数说明</th> 
   <th>接口说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td><a href="https://cplusplus.com/reference/stack/stack/stack/" rel="nofollow">stack()</a></td> 
   <td>构造空的栈</td> 
  </tr> 
  <tr> 
   <td><a href="https://cplusplus.com/reference/stack/stack/empty/" rel="nofollow">empty()</a></td> 
   <td>检测stack是否为空</td> 
  </tr> 
  <tr> 
   <td><a href="https://cplusplus.com/reference/stack/stack/size/" rel="nofollow">size()</a></td> 
   <td>返回stack中元素的个数</td> 
  </tr> 
  <tr> 
   <td><a href="https://cplusplus.com/reference/stack/stack/top/" rel="nofollow">top()</a></td> 
   <td>返回栈顶元素的引用</td> 
  </tr> 
  <tr> 
   <td><a href="https://cplusplus.com/reference/stack/stack/push/" rel="nofollow">push()</a></td> 
   <td>将元素val压入stack中</td> 
  </tr> 
  <tr> 
   <td><a href="https://cplusplus.com/reference/stack/stack/pop/" rel="nofollow">pop()</a></td> 
   <td>将stack中尾部的元素弹出</td> 
  </tr> 
 </tbody> 
</table>

#### 1.2.1 stack的构造 ####

![在这里插入图片描述][010f0308a3e6449c8a4040a04a7d3648.png]  
栈的构造、析构等默认成员函数不需要我们自己写，因为它是自定义类型，会自动调用默认成员函数。

#### 1.2.2 进、出栈等接口的模拟实现 ####

栈是deque（双端队列）容器适配器构造的对象，因此stack的这些接口，只需要调用deque的接口来完成就可以，本质是对deque的接口再封装一层。  
所以这些接口实现的都很简单

template<class T, class Container = deque<T>> // 双端队列
    class stack
    {
        
    public:
        stack()
        {
        }
    
        void push(const T& x)
        {
        
            _c.push_back(x);
        }
    
        void pop()
        {
        
            _c.pop_back();
        }
    
        T& top()
        {
        
            return _c.back();
        }
    
        const T& top()const
        {
        
            return _c.back();
        }
    
        size_t size()const
        {
        
            return _c.size();
        }
    
        bool empty()const
        {
        
            return _c.empty();
        }
    
    private:
        Container _c;
    };

## 2、queue ##

### 2.1 queue的介绍 ###

[queue的介绍文档][queue]  
![在这里插入图片描述][97d8ab858c5d4fd1930b707c0469cd82.png]

> 1. 队列是一种容器适配器，专门用于在FIFO上下文**(先进先出)**中操作，其中从容器一端插入元素，另一端提取元素。  
> 2. 队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列。  
> 3. 底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操作: empty：检测队列是否为空 size：返回队列中有效元素的个数 front：返回队头元素的引用 back：返回队尾元素的引用 push\_back：在队列尾部入队列  
> pop\_front：在队列头部出队列  
> 4. 标准容器类deque和list满足了这些要求。**默认情况下，如果没有为queue实例化指定容器类，则使用标准容器deque。**

### 2.2 queue的使用 ###

<table> 
 <thead> 
  <tr> 
   <th>函数声明</th> 
   <th>接口说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td><a href="https://cplusplus.com/reference/queue/queue/queue/" rel="nofollow">queue()</a></td> 
   <td>构造空的队列</td> 
  </tr> 
  <tr> 
   <td><a href="https://cplusplus.com/reference/queue/queue/empty/" rel="nofollow">empty()</a></td> 
   <td>检测队列是否为空，是返回true，否则返回false</td> 
  </tr> 
  <tr> 
   <td><a href="https://cplusplus.com/reference/queue/queue/size/" rel="nofollow">size()</a></td> 
   <td>返回队列中有效元素的个数</td> 
  </tr> 
  <tr> 
   <td><a href="https://cplusplus.com/reference/queue/queue/front/" rel="nofollow">front()</a></td> 
   <td>返回队头元素的引用</td> 
  </tr> 
  <tr> 
   <td><a href="https://cplusplus.com/reference/queue/queue/back/" rel="nofollow">back()</a></td> 
   <td>返回队尾元素的引用</td> 
  </tr> 
  <tr> 
   <td><a href="https://cplusplus.com/reference/queue/queue/push/" rel="nofollow">push()</a></td> 
   <td>在队尾将元素val入队列</td> 
  </tr> 
  <tr> 
   <td><a href="https://cplusplus.com/reference/queue/queue/pop/" rel="nofollow">pop()</a></td> 
   <td>将队头元素出队列</td> 
  </tr> 
 </tbody> 
</table>

#### 2.2.1 queue构造 ####

![在这里插入图片描述][ff39f40470e14ddf94928d97c0fef6b8.png]

这里与stack一样，调用自定义类型的默认成员函数。

#### 2.2.2 入、出队等接口的模拟实现 ####

队列也是deque（双端队列）容器适配器构造的对象，只要调用它的接口来实现就可以，也是封装了一层。

template<class T, class Container = deque<T>>
    class queue
    {
        
    public:
        queue()
        {
        }
    
        void push(const T& x)
        {
        
            _c.push_back(x);
        }
    
        void pop()
        {
        
            _c.pop_front();
        }
    
        T& back()
        {
        
            return _c.back();
        }
    
        const T& back()const
        {
        
            return _c.back();
        }
    
        T& front()
        {
        
            return _c.front();
        }
    
        const T& front()const
        {
        
            return _c.front();
        }
    
        size_t size()const
        {
        
            return _c.size();
        }
    
        bool empty()const
        {
        
            return _c.empty();
        }
    
    private:
        Container _c;
    };

[59f58cd657d4419db0b643ae0cca17ba.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/18/cf7e234ca31c4163b0395ce262cb6d26.png
[stack]: https://cplusplus.com/reference/stack/stack/?kw=stack
[1d8ab7ba6d5e4cf4921cd32490486d42.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/18/463a5808c8084557a7f6c0c78555c1a1.png
[010f0308a3e6449c8a4040a04a7d3648.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/18/890310bde6a84ffc9a275d4949387560.png
[queue]: https://cplusplus.com/reference/queue/queue/
[97d8ab858c5d4fd1930b707c0469cd82.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/18/1ee0da6d0fca41eaaa2a9cb52e08a0f9.png
[ff39f40470e14ddf94928d97c0fef6b8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/18/8169a2563d7a459696aedfbb91883792.png