栈和队列没有迭代器，他们只是容器适配器，不是容器。容器才有迭代器

文章目录

栈Stack

➡️有关 栈的实现/二叉树的实现 的知识，可以点击这里进行学习⬅️

头文件：stack

本质

template <class T, class Container = deque<T> > class stack;
  • 后进先出
  • 栈是一种“容器适配器” ——>栈可能是由list，vector或deque容器（称为底层容器）变化而来
  • 底层容器，如果不传，默认是deque

成员函数

    • empty

      Test whether container is empty (public member function )

    • size

      Return size (public member function )

    • top

      Access next element (public member function )

    • push

      Insert element (public member function )

    • emplace

      Construct and insert element (public member function )

    • pop

      Remove top element (public member function )

    • swap

      Swap contents (public member function )

实现

stack.h

#pragma once

namespace lcj
{
	template<class T, class Container = vector<T>>
	class stack
	{
	public:
	/// <summary>
	/// 不用写构造函数，因为container是自定义类型，会调用对应的构造函数
	/// </summary>
	/// 
		void push(const T& x)
		{
			_con.push_back(x);
		}

		void pop()
		{
			_con.pop_back();
		}

		const T& top() const
		{
			return _con.back();///不能通过‘[ ]’访问，当container是list时，没有这个功能
		}

		size_t size() const 
		{
			return _con.size();
		}

		bool empty()const
		{
			return _con.size() == 0;
		}



	private:
		Container _con;
	};
}

按需实例化：

在.h中写的类中的成员函数，并不会全都被实例化，编译器只实例化使用的接口——>编译器不检查细节语法，有时候不会报错，但是使用的时候还是会发生错误——>写函数的时候还是要写一个检查一个

队列queue

本质

template <class T, class Container = deque<T> > class queue;
  • 先进先出
  • 也是一种“容器适配器” ——>栈可能是由list，vector或deque容器（称为底层容器）变化而来
  • 底层容器，如果不传，默认是deque

成员函数

    • empty

      Test whether container is empty (public member function )

    • size

      Return size (public member function )

    • front

      Access next element (public member function )

    • back

      Access last element (public member function )

    • push

      Insert element (public member function )

    • emplace

      Construct and insert element (public member function )

    • pop

      Remove next element (public member function )

    • swap

      Swap contents (public member function )

实现

queue.h

#pragma once 

namespace lcj
{
	template<class T, class Container = list<T>>
	class queue
	{
	public:
		/// <summary>
		/// 不用写构造函数，因为container是自定义类型，会调用对应的构造函数
		/// </summary>
		/// 
		void push(const T& x)
		{
			_con.push_back(x);
		}

		void pop()
		{
			_con.pop_front();
		}

		const T& back() const
		{
			return _con.back();///不能通过‘[ ]’访问，当container是list时，没有这个功能
		}

		const T& front() const
		{
			return _con.front();///不能通过‘[ ]’访问，当container是list时，没有这个功能
		}

		size_t size() const
		{
			return _con.size();
		}

		bool empty()const
		{
			return _con.size() == 0;
		}



	private:
		Container _con;
	};
}

deque双端队列

stack和queue的缝合

成员函数

函数分类函数名功能说明
构造 / 析构 / 赋值(constructor)构造 deque 容器（公有成员函数）
(destructor)销毁 deque 容器（公有成员函数）
operator=给 deque 容器赋值（公有成员函数）
迭代器（Iterators）begin返回指向容器起始位置的迭代器（公有成员函数）
end返回指向容器末尾位置的迭代器（公有成员函数）
rbegin返回指向容器反向起始位置的反向迭代器（公有成员函数）
rend返回指向容器反向末尾位置的反向迭代器（公有成员函数）
cbegin返回指向容器起始位置的 const 迭代器（公有成员函数）
cend返回指向容器末尾位置的 const 迭代器（公有成员函数）
crbegin返回指向容器反向起始位置的 const 反向迭代器（公有成员函数）
crend返回指向容器反向末尾位置的 const 反向迭代器（公有成员函数）
容量管理（Capacity）size返回容器当前存储的元素数量（公有成员函数）
max_size返回容器可容纳的最大元素数量（公有成员函数）
resize改变容器的大小（公有成员函数）
empty检测容器是否为空（公有成员函数）
shrink_to_fit释放容器未使用的内存，收缩到适配当前元素大小（公有成员函数）
元素访问（Element access）operator[]访问容器中指定下标位置的元素（公有成员函数）
at访问容器中指定下标位置的元素，带越界检查（公有成员函数）
front访问容器的第一个元素（公有成员函数）
back访问容器的最后一个元素（公有成员函数）
内容修改（Modifiers）assign给容器重新赋值，覆盖原有内容（公有成员函数）
push_back在容器末尾添加一个元素（公有成员函数）
push_front在容器开头插入一个元素（公有成员函数）
pop_back删除容器末尾的最后一个元素（公有成员函数）
pop_front删除容器开头的第一个元素（公有成员函数）
insert在容器指定位置插入元素（公有成员函数）
erase删除容器指定位置的元素（公有成员函数）
swap交换两个 deque 容器的内容（公有成员函数）
clear清空容器内的所有元素（公有成员函数）
emplace_front在容器开头直接构造并插入一个元素（公有成员函数）
emplace_back在容器末尾直接构造并插入一个元素（公有成员函数）
分配器（Allocator）get_allocator获取容器使用的内存分配器（公有成员函数）
非成员函数重载relational operatorsdeque 容器的关系比较运算符（函数模板）
swap交换两个 deque 容器的内容（函数模板）

priority_queue优先级队列

➡️有关 堆和二叉树 的知识，可以点击这里进行学习【数据结构精讲】堆与二叉树从底层原理到代码落地：堆的构建 / 调整 / 排序 + 二叉树遍历 / 操作（附完整 C++ 源码 + LeetCode 题解）⬅️

本质

template <class T, class Container = vector<T>,
  class Compare = less<typename Container::value_type> > class priority_queue;
  • 就是个堆，默认是大根堆
  • 也是容器适配器，默认是vector（因为下标访问用的多）

头文件：queue‼️

不是单独的‼️

成员函数

    • (constructor)

      Construct priority queue (public member function )

    • empty

      Test whether container is empty (public member function )

    • size

      Return size (public member function )

    • top

      Access top element (public member function )

    • push

      Insert element (public member function )

    • emplace

      Construct and insert element (public member function )

    • pop

      Remove top element (public member function )

    • swap

      Swap contents (public member function )

应用

大根堆

  • priority_queue<int, vector<int>, less<int>> pq;中的： less<int>也可以不写，是默认的，这时候是大根堆——>打印出来是从大到小的
#include<queue>

using namespace std;///必须在#include"stack.h"的前面，这样，如果stack.h里面有std::cout这种函数也没问题
 

int main()
{
	priority_queue<int, vector<int>, less<int>> pq;
	pq.push(3);
	pq.push(777);
	pq.push(66);
	pq.push(88);
	pq.push(22);
	pq.push(9);

	while (!pq.empty())
	{
		cout << pq.top() << endl;
		pq.pop();
	} 
	return 0;
}

小根堆

——>从小到大打印

只需要改 less<int>为greater<int>即可

实现

位置：

  • 在namespace lcj 中

基础：

  1. 通过类模板实现： template <class T, class Container = std::vector<T>, class Compare = Less<T> >
    1. class T：priority_queue中存的类型
    2. class Container = std::vector<T>：priority_queue 也是一种“容器适配器” ——>可能是由list，vector或deque容器（称为底层容器）变化而来
    3. class Compare = Less<T>：仿函数， （ 重载了 () 运算符的类，长得像函数，实际是对象。）。需要你在前面专门写两个仿函数（只有operator() 的类模板）：Greater和Less
  2. push：堆插入，需要提前写向上调整算法void Adjustup(size_t child)
  3. pop：删除堆顶元素，需要提前写向下调整算法：void Adjustdown(int parent)

完整代码


    template <class T>///类模板——>得到的类中只有operator（）——>仿函数
    class Less///——>用来判断小于的仿函数
    {
    public:
        bool operator() (const T& x, const T& y)
        {
            return x < y;
        }
    };


    template <class T>
    class Greater///——>用来判断大于的仿函数
    {
    public:
        bool operator() (const T& x, const T& y)
        {
            return x > y;
        }
    };



    template <class T, class Container = std::vector<T>, class Compare = Less<T> >///传参传的是仿函数（一种类）
    /// <summary>
    /// 在创建priorityqueue的时候，直接传仿函数就能判断是大根堆还是小根堆 

    class priority_queue

    {

    public:

        priority_queue()
        {

        } 

        void Adjustup(size_t child)
        { 

            int parent = (child - 1) / 2;

            while (child > 0)
            {
                if (comp(c[parent], c[child]))
                {
                    std::swap(c[child], c[parent]);
                    child = parent;
                    parent = (child - 1) / 2;

                }

                else
                    break;
            } 
        }

        void push(const T& x)
        {
            c.push_back(x);
            
            Adjustup(c.size() - 1);
        }

        void Adjustdown(int parent)
        {
            int child = parent * 2 + 1;
            while (child < c.size())
            {
                if (child + 1 < c.size() && comp(c[child], c[child + 1]))
                    ++child;

                if (comp(c[parent], c[child]))
                {
                    std:: swap(c[parent], c[child]);
                    parent = child;
                    child = parent * 2 + 1;
                }

                else
                {
                    break;
                }
            }
        }

        void pop()
        {
            std::swap(c[0], c[c.size() - 1]);
            c.pop_back();

            Adjustdown(0); 

        }

        bool empty() const
        {
            return c.size() == 0;
        }

        size_t size() const
        {
            return c.size() ;
        }

        const  T& top() const
        {
            return c.front();
        }

    private:

        Container c;

        Compare comp;

    };

};

拓展函数

make_heap(传begin和end)

  • 可以将一个vector变成堆

sort_heap（创begin和end）

  • 将堆进行堆排序（只能将堆进行堆排序‼️）

push_heap

pop_heap

题目

1.栈的压入、弹出序列

栈的压入、弹出序列

  1. 入栈序列，每次入栈一个值
  2. 如果入后的栈顶数据跟出栈序列匹配，——>出栈——>不断匹配，不断出栈
  3. 入栈序列入完了，就结束了

2.二叉树的层序遍历

原题链接：二叉树的层序遍历

image-20260607113013903

这个题目给的是二叉树，要求是输出一个vector<vector<int>>类型的数组

1.实现二叉树层序遍历：

队列存节点指针，下来一个节点，放一个节点的子节点

  • 创造一个队列，存的是TreeNode*类型的指针： queue<TreeNode*> q;

  • 插入树根：q.push(root);

  • while循环遍历：

    • 条件： 队列中还有元素： while(!q.empty())

    • 循环体：

      • 得到队列头节点：TreeNode* thisnode=q.front();

      • 头删：q.pop();

      • 操作：……

      • 将这个节点的孩子放进队列：

        ​ if(thisnode->left)
        ​ q.push(thisnode->left);

        ​ if(thisnode->right)
        ​ q.push(thisnode->right);

        queue<TreeNode*> q;
        int levelsize=0;

        if(root)
        {
            q.push(root); 
        }

        while(!q.empty())
        {   
                TreeNode* thisnode=q.front(); 
                q.pop();
            
            //对thisnode的操作

                if(thisnode->left)
                    q.push(thisnode->left);

                if(thisnode->right)
                    q.push(thisnode->right); 
        }

2.进一步实现题目要求

在上面的条件下，我们一层一层输入数据

  1. levelsize作为内部的循环条件
    1. 在“插入树根”的时候，levelsize置为1——因为第一层只有一个节点
      1. 然后的循环中，只将levelsize个节点的子节点插入队列中
    2. 插入结束之后的队列的size，就是下一层的节点个数
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) 
    {
        vector<vector<int>> vv;
        queue<TreeNode*> q;
        int levelsize=0;

        if(root)
        {
            q.push(root);
            levelsize=1; 
        }

        while(!q.empty())
        {
            vector<int> v;

            while(levelsize--)////////////////////////////////levelsize作为内部的循环条件
            {
                TreeNode* thisnode=q.front();
                q.pop();
                
                
                v.push_back(thisnode->val);//操作

                if(thisnode->left)
                    q.push(thisnode->left);

                if(thisnode->right)
                    q.push(thisnode->right);

            }
            
            
            vv.push_back(v);  //////////////////////////////////////////操作
            levelsize=q.size();/////////////////////////////插入结束之后的队列的size，就是下一层的节点个数
        }

        return vv;
        
    }
};

# c++ # 面试 # java
Logo
亚马逊云科技技术品牌专区

更多推荐

open-code-review Codex 插件教程：对话式调用评审技能指南

本文是一份面向新手的 **open-code-review Codex 插件教程**，教你在 Codex 中通过对话式方式调用 open-code-review 的 AI 代码评审技能。open-code-review 是阿里巴巴开源的 AI 代码评审工具，采用"确定性流水线 + LLM Agent"混合架构，内置多语言评审规则（NPE、线程安全、XSS、SQL 注入等），可在 Codex 里用一

avatar 亚马逊云科技技术品牌专区

OBS Studio 完整指南：免费开源录屏与直播软件从零上手

想做一场像模像样的直播，或者把屏幕内容录成教程视频，但一想到商用软件的订阅费就有些犹豫？其实你不需要花一分钱。OBS Studio 是一款免费开源的直播与录屏软件，支持 Windows、macOS 和 Linux，采集、混音、编码、推流、录制，一条流水线全包了。## 先搞清楚 OBS Studio 是什么OBS Studio 是一个"场景化"的采集合成工具：你把摄像头、窗口、浏览器、图片、

avatar 亚马逊云科技技术品牌专区

如何用MediaCrawler爬取小红书抖音数据？7大平台爬虫从安装到实战完整指南

MediaCrawler 是一个支持小红书、抖音、快手、B站、微博、百度贴吧、知乎的开源自媒体数据采集工具。它能按关键词、按帖子、按创作者主页三种方式抓取笔记/视频内容、评论甚至二级评论，并把结果存成 JSON、CSV、Excel 或数据库。适合做市场调研、竞品监控、内容选题的运营人员，以及想要现成爬虫框架而不想从零写 JS 逆向的开发者。## 从一次"手动抄数据"说起想象这个场景：你负责

avatar 亚马逊云科技技术品牌专区