STL中stack和queue的使用以及模拟实现

忘是亡心i 2023-09-28 15:18 85阅读 0赞

### STL中stack和queue的使用以及模拟实现 ###

*  一、 stack的介绍和使用
 *   *  1、stack的介绍
     *  2、stack的使用
 *  二、queue的介绍和使用
 *   *  1、queue的介绍
     *  2、queue的使用
 *  三、模拟实现
 *   *  1、模拟实现stack
     *  2、模拟实现queue

# 一、 stack的介绍和使用 #

## 1、stack的介绍 ##

[stack文档阅读][stack]

1.  stack是一种容器适配器，专门用在具有后进先出操作的上下文环境中，其删除只能从容器的一端进行元素的插入与提取操作。
2.  stack是作为容器适配器被实现的，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定的成员函数来访问其元素，将特定类作为其底层的，元素特定容器的尾部(即栈顶)被压入和弹出。
3.  stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类，这些容器类应该支持以下操作：

<table> 
 <thead> 
  <tr> 
   <th>empty</th> 
   <th>判空操作</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>back</td> 
   <td>获取尾部元素操作</td> 
  </tr> 
  <tr> 
   <td>push_back</td> 
   <td>尾部插入元素操作</td> 
  </tr> 
  <tr> 
   <td>pop_back</td> 
   <td>尾部删除元素操作</td> 
  </tr> 
 </tbody> 
</table>

1.  标准容器vector、deque、list均符合这些需求，默认情况下，如果没有为stack指定特定的底层容器，默认情况下使用deque。  
    ![fb3ad8d7fc2c417b8bdb43a14ddca5e4.png][]

## 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>

例如：OJ题[最小栈][Link 1]

class MinStack {
        
    public:
        void push(int val) {
        
            _st.push(val);
            if(_min_st.empty() || val <= _min_st.top()) {
        
                _min_st.push(val);
            }
        }
        void pop() {
        
            if(_st.top() == _min_st.top())
                _min_st.pop();
            _st.pop();
        }
        int top() {
        
            return _st.top();
        }
        int getMin() {
        
            return _min_st.top();
        }
    private:
        stack<int> _st;
        stack<int> _min_st;
    };

# 二、queue的介绍和使用 #

## 1、queue的介绍 ##

[queue文档阅读][queue]

1.  队列是一种容器适配器，专门用于在FIFO上下文(先进先出)中操作，其中从容器一端插入元素，另一端提取元素。
2.  队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列。
3.  底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操作:

<table> 
 <thead> 
  <tr> 
   <th>empty</th> 
   <th>检测队列是否为空</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>size</td> 
   <td>返回队列中有效元素的个数</td> 
  </tr> 
  <tr> 
   <td>front</td> 
   <td>返回队头元素的引用</td> 
  </tr> 
  <tr> 
   <td>back</td> 
   <td>返回队尾元素的引用</td> 
  </tr> 
  <tr> 
   <td>push_back</td> 
   <td>在队列尾部入队列</td> 
  </tr> 
  <tr> 
   <td>pop_front</td> 
   <td>在队列头部出队列</td> 
  </tr> 
 </tbody> 
</table>

1.  标准容器类deque和list满足了这些要求。默认情况下，如果没有为queue实例化指定容器类，则使用标准容器deque。  
    ![414cd648bef649d390e774513bc4b563.png][]

## 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>

例题：OJ[用队列实现栈][Link 2]

class MyStack {
        
    public:
        queue<int> q;
        /** Initialize your data structure here. */
        MyStack() {
        
        }
    
        /** Push element x onto stack. */
        void push(int x) {
        
            int n = q.size();
            q.push(x);
            for (int i = 0; i < n; i++) {
        
                q.push(q.front());
                q.pop();
            }
        }
        
        /** Removes the element on top of the stack and returns that element. */
        int pop() {
        
            int r = q.front();
            q.pop();
            return r;
        }
        
        /** Get the top element. */
        int top() {
        
            int r = q.front();
            return r;
        }
        
        /** Returns whether the stack is empty. */
        bool empty() {
        
            return q.empty();
        }
    };

# 三、模拟实现 #

## 1、模拟实现stack ##

stack.h

#pragma once
    #include<deque>
    
    namespace mystack
    {
        
    	template<class T, class Container = std::deque<T> >
    	class stack
    	{
        
    	public:
    		void push(const T& x)
    		{
        
    			_con.push_back(x);
    		}
    
    		void pop()
    		{
        
    			_con.pop_back();
    		}
    
    		const T& top()
    		{
        
    			return _con.back();
    		}
    
    		size_t size()
    		{
        
    			return _con.size();
    		}
    
    		bool empty()
    		{
        
    			return _con.empty();
    		}
    
    	private:
    		Container _con;
    	};
    }

## 2、模拟实现queue ##

queue.h

#pragma once
    #include<deque>
    
    namespace myqueue
    {
        
    		template<class T,  class Container = std::deque<T>>
    	class queue
    	{
        
    	public:
    		void push(const T& x)
    		{
        
    			_con.push_back(x);
    		}
    
    		void pop()
    		{
        
    			_con.pop_front();
    		}
    
    		const T& front()
    		{
        
    			return _con.front();
    		}
    
    		const T& back()
    		{
        
    			return _con, back();
    		}
    
    		size_t size()
    		{
        
    			return _con.size();
    		}
    
    		bool empty()
    		{
        
    			return _con.empty();
    		}
    
    	private:
    		Container _con;
    	};
    }

[stack]: https://cplusplus.com/reference/stack/stack/?kw=stack
[fb3ad8d7fc2c417b8bdb43a14ddca5e4.png]: https://img-blog.csdnimg.cn/fb3ad8d7fc2c417b8bdb43a14ddca5e4.png
[Link 1]: https://leetcode.cn/problems/min-stack/
[queue]: https://cplusplus.com/reference/queue/queue/
[414cd648bef649d390e774513bc4b563.png]: https://img-blog.csdnimg.cn/414cd648bef649d390e774513bc4b563.png
[Link 2]: https://leetcode.cn/problems/implement-stack-using-queues/submissions/