【C++初阶】queue的常见操作和模拟实现

一、queue的基本概念

• queue是一种容器适配器：现有的容器转化出来的（本质就是复用），也就是说queue是依靠其他容器来实现的。
• 队列queue是一种先进先出（First in First Out，简称FIFO）的数据结构， 其中从容器一端插入元素，另一端提取元素
• 容器适配器通常会限制对底层容器的访问方式，因此不支持随机访问。

二、 queue的常见操作

三、有关队列的力扣经典题

3.1 二叉树的层序遍历

链接：点击跳转

【题目描述】

【思路】

【代码实现】

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) 
    {
        queue<TreeNode*>q;
        vector<vector<int>> vv;
        int levelSize;

        // 如果根节点不为空，则入队列
        if (root)
        {
            q.push(root);
            // 并且根节点的root一定为1
            levelSize = 1;
        }

        while (!q.empty())
        {
            // 一层一层出
            vector<int> v;
            for (int i = 0;i < levelSize;i++)
            {
                // 记录当前节点
                TreeNode* front = q.front();
                // 删除节点并存入
                q.pop();
                v.push_back(front->val);
                // 并带入它的子节点
                if (front->left) q.push(front->left);
                if (front->right) q.push(front->right);
            }
            vv.push_back(v);
            // 一层出完更新一层的个数
            levelSize = q.size();
        }
        return vv;
    }
};

3.2 用队列实现栈

链接：点击跳转

【题目描述】

【思路】

队列的特点是先进先出，而栈是先进后出，首先定义两个队列

那如何模拟一个栈呢？首先往空的队列入数据

对于栈来说，先出的是4。因此我们可以把1 2 3移到另一个空队列中

【代码实现】

class MyStack {
public:
    MyStack() {}
    
    void push(int x) 
    {
    	// 往不是空的队列插入数据
        if (in.empty())
        {
            out.push(x);
        }
        else
            in.push(x);
    }
    
    int pop() 
    {
    	// 保持一个队列为空
    	// 将一个为空的队列的前n-1个移到空队列
    	// 剩下的那个这是栈顶元素
        if (in.empty())
        {
            while (out.size() > 1)
            {
                int front = out.front();
                out.pop();
                in.push(front);
            }
            int ans = out.front();
            out.pop();
            return ans;
        }
        else // out为空
        {
            while (in.size() > 1)
            {
                int front = in.front();
                in.pop();
                out.push(front);
            }
            int ans = in.front();
            in.pop();
            return ans;
        }
    }
    
    int top() 
    {
        if (in.empty())
        {
           return out.back();
        }
        else 
        {
            return in.back();
        }
    }
    
    bool empty()
    {
        return in.empty() && out.empty();
    }
private:
    queue<int> in;
    queue<int> out;
};

四、模拟实现queue

4.1 简介

queue同样也是一种容器适配器。对于容器适配器，大家可以理解为对已有的东西(容器)进行适配转换。因此就增加了模板参数Container。在数据结构中，队列我们是使用链表来实现的，而为啥模板参数的缺省值deque容器，而不是list容器，后面会讲解到

4.2 代码实现

队列需要满足先进先出，因此常见的操作有尾插、头删…

#pragma once

namespace wj
{
	template<class T, class Container = 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;
	};

注意：队列就不能用vector适配了，因为vector没有提供pop_front接口，但是也可以强制适配。只需要改动pop接口

void pop()                   
{
	_con.erase(_con.begin());      
}

但注意，库里是没有强制适配的

为了贴近库，最好不要进行强制适配。

那么为什么库里不适配vector？原因是：队列需要进行大量头删操作，而vector底层头删需要移动大量数据，效率极低。