一、 stack的介绍和使用

1、stack的介绍

stack文档阅读

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

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

2、stack的使用

例如：OJ题最小栈

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文档阅读

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

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

2、queue的使用

例题：OJ用队列实现栈

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;
	};
}