[C++基础]-stack和queue-阿里云开发者社区

一、stack的基本知识

1、什么是栈

栈（Stack）是一种常见的数据结构，它遵循后进先出（LIFO）的原则。栈是一种STL中的容器，类似于现实生活中的堆叠物体，只能在顶部进行插入和删除操作。

栈具有两个主要操作：

入栈（Push）：将元素添加到栈的顶部，成为新的栈顶。

出栈（Pop）：从栈的顶部移除元素，并返回被移除的元素。

由于栈遵循后进先出的原则，最后一个入栈的元素将是第一个出栈的元素，即最新的元素先被访问或移除。

栈还具有一个特殊的属性——栈顶指针（Top），它指向栈的顶部元素。当执行入栈操作时，栈顶指针上移；而在执行出栈操作时，栈顶指针下移。

栈常常用于解决与层次结构相关的问题，例如函数调用、表达式求值、括号匹配、回溯算法等。在计算机内存管理中，栈也被用于存储函数的局部变量、参数以及程序执行期间的临时数据。

需要注意的是，栈具有一定的容量限制，称为栈的大小。当栈已满时，执行入栈操作将导致栈溢出（Stack Overflow）；而当栈为空时，执行出栈操作将导致栈下溢（Stack Underflow）

2、栈的基本使用

对栈(stack)来说在C++中进行来封装，他的底层我们看做是用一个类来实现的，所以他有自己的成员函数和成员变量。通过前面我们对vector和list的学习相信大家对STL容器的都比较熟悉了，下面我们主要和大家介绍一下stack的重点接口.

栈的重要接口：

函数说明	接口说明
stack()	构造空的栈
empty()	判断栈是否为空
size()	返回栈中有多少的元素
top()	返回栈顶中的元素
push()	将元素val压入栈中
pop()	将stack中尾部弹出

栈代码使用演示：

在演示之前，看一个代码：

  for (auto e : st)
  {
 
  }
//代码不可用

运行之后程序会报错，这是为什么呢？这是因为使用aoto for循环的本质其中也运用到了迭代器，也就是要有begin（），end()的成员函数，但是stack是没有的。

那我们将怎么样去打印出stack中的数据呢？

这里我就用用到top（）获取栈顶元素，和pop（）将栈顶元素出栈就可以了。

#define  _CRT_SECURE_NO_WARNINGS
 
#include<iostream>
#include<stack>
 
using namespace std;
int main()
{
  stack<int> st;
  st.push(1);
  st.push(2);
  st.push(3);
  st.push(4);
  st.push(5);
  while (!st.empty())
  {
    cout << st.top() << " ";
    st.pop();
  }
  cout << endl;
  return 0;
}

3、栈的模拟实现

为了更好的理解栈，下面我将模拟实现栈。模拟实现栈时，我们不妨思考一下我们是用数组实现还是用链表实现栈呢？

我们知道数组有数组的好处，链表也有链表的的好处，那我们可以二个都用可以吗？

其实是可以的，这就不得不提一下适配器模式，那什么是适配器模式呢？

其实就是将以有的东西封装转化成你想要的东西。

  template<class T, class Container>
  class stack
  {
  public:
  private:
    Container _con;
  };

这里我们只要多传一个模板参数，Container就可以了。

我们在用自己定义栈，创建对象时多传一个参数就可以了，这样我们就在底层上既实现用list实现的栈，又实现了vector实现的栈

   stack<int，linst<int>> st;//链表实现
   stack<int，vector<int>> st;//数组实现

下面我们只要完善好成员函数就可以实现自己的栈了

namespace pjb
{
  template<class T, class Container >
  class stack
  {
  public:
    void  push(const T& x)
    {
      _con.push_back(x);
    }
    void pop()
    {
      _con.pop_back();
    }
    const T& top()
    {
      return _con.back();
    }
    bool empty()
    {
      return _con.empty();
    }
    size_t size()
    {
      return _con.size();
    }
  private:
    Container _con;
  };
}

测试：

二、queue的基本知识

1、什么是队列

队列（Queue）是一种数据结构，它遵循先进先出（First-In-First-Out，FIFO）的原则。队列中的数据项按照插入的顺序排列，最先插入的数据项首先被移除。

队列可以比喻成现实生活中的排队等候的场景。新来的人必须排在队尾，而排在队头的人最先离开队列。

队列有两个基本操作：

入队（Enqueue）：将数据项添加到队列的末尾。

出队（Dequeue）：将队列的第一个数据项移除，并返回该数据项。

队列常常用于模拟系统中的排队行为，如任务调度、消息传递等。在编程中，队列可以使用数组或链表等数据结构来实现。

但是要注意并非所有队列都是先进先出的，有一个叫优先级的队列就不是这样的，后面在为大家介绍，我们先了解基本队列的用法。

2、队列的基本用法

队列我们在使用这个容器的时候，重点关注几个接口就好了

队列的重要接口：

函数声明	接口说明
queue()	构造空的队列
empty()	检测队列是否为空，是返回true，否则返回false
size()	回队列中有效元素的个数
front()	返回队头元素的引用
back()	返回队尾元素的引用
push()	在队尾将元素val入队列
pop()	将队头元素出队列

队列代码演示：

int main()
{
  queue<int> qe;
  qe.push(1);
  qe.push(2);
  qe.push(3);
  qe.push(5);
  qe.push(6);
  while (!qe.empty())
  {
    cout << qe.front() << " ";
    qe.pop();
  }
}

3、队列的模拟实现

这里我们常常说，vector和list都有各自的优缺点：

vector:

缺点：头部中部插入删除效率低，扩容有消耗

list：

缺点：不支持随机访问，CPU高速缓命中低。

其实vector和list的缺点和优点是互补的，那有没有一个容器兼容二者的优点呢？

C++中有一个容器 deque（双端队列）（Double Ended Queue，简称为Deque）是一种允许从两端进行插入和删除操作的队列。它可以在队列的前端和后端同时进行插入和删除操作。

双端队列支持以下几种基本操作：

在队头插入元素（Insert at Front）：将一个元素插入到双端队列的前端。

在队尾插入元素（Insert at Rear）：将一个元素插入到双端队列的后端。

从队头删除元素（Delete from Front）：从双端队列的前端删除并返回一个元素。

从队尾删除元素（Delete from Rear）：从双端队列的后端删除并返回一个元素。

获取队头元素（Get Front）：返回双端队列的前端元素。

获取队尾元素（Get Rear）：返回双端队列的后端元素。

双端队列优缺点：

优点：

与vector比较，deque的优势是：头部插入和删除时，不需要搬移元素，效率特别高，而且在扩容时，也不需要搬移大量的元素，因此其效率是必vector高的。

与list比较，其底层是连续空间，空间利用率比较高，不需要存储额外字段

缺点：

不适合遍历，因为在遍历时，deque的迭代器要频繁的去检测其是否移动到某段小空间的边界，导致效率低下

所以当我们传模板的第二个参数时可以直接传deque。

namespace pjb
{
  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& fornt()
    {
      return _con.front();
    }
 
    const T& back()
    {
      return _con.back();
    }
 
    bool empty()
    {
      return _con.empty();
    }
 
    size_t size()
    {
      return _con.size();
    }
 
  private:
    Container  _con;
  };
}

三、优先队列

1、优先队列的基本知识

优先队列（Priority Queue）是一种特殊的队列(是一种容器适配器)，它根据元素的优先级来确定出队的顺序。与普通队列不同，优先队列中的元素被赋予了优先级，优先级高的元素会先被出队。

优先队列的基本操作包括：

入队（Enqueue）：将元素插入到优先队列中，并根据其优先级进行适当的排序。

出队（Dequeue）：移除具有最高优先级的元素，并返回该元素。

获取队头元素（Get Front）：获取具有最高优先级的元素，但不从队列中移除。

优先队列可以使用不同的数据结构来实现，其中一个常见的实现方式是使用堆（Heap）。堆是一种完全二叉树，具有一些特殊的性质使得它适用于实现优先队列。在堆中，树的每个节点都比它的子节点具有更高的优先级。

优先队列的特点：

优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中元素构造成堆的结构，因此priority_queue就是堆，所有需要用到堆的位置，都可以考虑使用priority_queue。注意：默认情况下priority_queue是大堆。

优先队列的操作函数：

函数声明	接口说明
priority_queue()/priority_queue(first,last)	构造一个空的优先级队列
empty( )	检测优先级队列是否为空，是返回true，否则返回 false
top( )	返回优先级队列中最大(最小元素)，即堆顶元素
push()	在优先队列中插入元素
pop()	删除优先级队列中最大(最小)元素，即堆顶元素

注意：

默认情况下，priority_queue是大堆。

如果在priority_queue中放自定义类型的数据，用户需要在自定义类型中提供> 或者< 的重载

2、仿函数

仿函数（Functor）是一种具有函数行为的对象，实际上是将函数行为封装在一个类或结构体中。它可以像函数一样被调用，可以作为函数参数传递，也可以作为返回值返回。

在C++中，仿函数可以通过重载operator()运算符来实现函数调用操作。通过这种方式，仿函数可以像普通函数一样被调用，而且可以带有自己的状态和行为。

class AddFunctor {
public:
    int operator()(int a, int b) const {
        return a + b;
    }
};
 
int main() {
    AddFunctor add;
    int result = add(3, 4);  // 调用仿函数
    // 结果为7
    return 0;
}

那我们不由的想到函数和仿函数有什么区别吗？

仿函数（Functor）实际上是一个类对象，它的对象可以像函数一样被调用。

函数是一段可执行的代码块，可以通过函数名直接调用。

区别：

类对象：仿函数是一个类对象，而函数是一个独立的代码块。仿函数的行为可以通过重载函数调用运算符 operator() 来定义，使得它可以被像函数一样调用。

状态保持：仿函数可以在自己的内部保留状态信息，这些信息可以在不同的函数调用之间保持，并影响后续的函数调用。而函数通常不具备状态保持的能力，每次调用都是独立的，无法直接记住之前的状态。

可定制性：由于仿函数是一个类对象，我们可以根据需要定制它的行为，通过它的成员变量和函数实现更复杂的逻辑。函数则相对简单，无法直接修改其内部的逻辑。

应用场景：仿函数常用于STL的算法中，比如排序、查找、遍历等操作，因其灵活的行为定义和可定制性。函数则广泛应用于各种编程场景，无论是简单的数学运算还是复杂的业务逻辑

3、priority_queue的模拟实现

在模拟实现优先队列，我们重点关注向上调整和向下调整的方法，来进行建堆。

这里我们也用到我们上面讲的仿函数：

  template<class T>
  class less
  {
  public:
    bool operator()(const T& x, const T& y)const
    {
      return x < y;
    }
  };
  
  template<class T>
  class greator
  {
    bool operator()(const T& x, const T& y)const
    {
      return x > y;
    }
  };

大家可能不由的会想，这个就不是一个简单的大小比较吗？有必要写的这么复杂吗？，这种仿函数有必要被定义出来吗？

其实不然，虽然我们在写简单大小比较时候，是会增加了代码的复杂性，但是在实际的开发中，我们经常遇到需要对数据进行复杂排序或计算等操作，此时使用仿函数就可以极大地提高程序的灵活性和可扩展性。

以排序为例，STL提供了多种排序算法，如sort、stable_sort等，这些算法均可通过传入一个比较函数来定义排序规则。使用仿函数定义排序规则时，我们可以根据自己的需要灵活地定制排序规则，从而实现更加复杂的排序操作

#pragma once
#include<algorithm>
 
namespace pjb
{
  template<class T>
  class less
  {
  public:
    bool operator()(const T& x, const T& y)const
    {
      return x < y;
    }
  };
  
  template<class T>
  class greator
  {
    bool operator()(const T& x, const T& y)const
    {
      return x > y;
    }
  };
  template<class T, class Container = vector<T>, class Compare = less<T>>
  class priority_queue
  {
  public:
    priority_queue()
    {}
    //建堆
    template <class InputIterator>
    priority_queue(InputIterator first, InputIterator last)
      :_con(first, last)
    {
      for (int i = (_con.size() - 1 - 1) / 2;i >= 0;--i)
      {
        for (int i = (_con.size() - 1 - 1) / 2; i >= 0; --i)
        {
          adjust_down(i);
        }
      }
    }
    //向上调整法
    void adjust_up(size_t child)
    {
      Compare com;
      size_t parent = (child - 1) / 2;
      while (child > 0)
      {
        //if(com(_con[parent]<_con[child])
        if (com(_con[parent], _con[child]))
        {
          std::swap(_con[child], _con[parent]);
          child = parent;
          parent = (child - 1) / 2;
        }
        else
        {
          break;
        }
      }
    }
    void push(const T& x)
    {
      _con.push_back(x);
      adjust_up(_con.size() - 1);
    }
 
    void adjust_down(size_t parent)
    {
      Compare com;
      size_t child = parent * 2 + 1;
      while (child < _con.size())
      {
        //找最大的孩子
        if (child + 1 < _con.size() && com(_con[child], _con[child + 1]))
        {
          child++;
        }
        //父亲节点<孩子节点交换
        if (com(_con[parent], _con[child]))
        {
          std::swap(_con[child], _con[parent]);
          parent = child;
          child = parent * 2 + 1;
 
        }
        else
        {
          break;
        }
      }
    }
 
    void pop()
    {
      //交换堆头和堆尾
      std::swap(_con[0], _con[_con.size() - 1]);
      //删除堆尾
      _con.pop_back();
      //向下调整堆
      adjust_down(0);
    }
 
    const T& top()const
    {
      return _con[0];
    }
 
    bool empty()const
    {
      return _con.empty();
    }
 
    size_t size()const
    {
      return _con.size();
    }
  private:
    Container _con;
  };
}

4、反向迭代器的模拟实现

template<class Iterator,class Ref,class Ptr>
class ReverseIterator
{
  typedef ReverseIterator<Iterator, Ref, Ptr>Self;
 
public:
  ReverseIterator(Iterator it)
    :_it(it)
  {}
  Ref operator*()
  {
    Iterator tmp = _it;
    return *(--tmp);
  }
  Ptr operator->()
  {
    return &(operator*());
  }
  Self& operator--()
  {
    ++_it;
    return *this;
  }
  bool operator!=(const Self& s)const
  {
    return _it != s._it;
  }
 
private:
  Iterator _it;
};

[C++基础]-stack和queue

一、stack的基本知识

1、什么是栈

2、栈的基本使用

3、栈的模拟实现

二、queue的基本知识

1、什么是队列

2、队列的基本用法

3、队列的模拟实现

三、优先队列

1、优先队列的基本知识

2、仿函数

3、priority_queue的模拟实现

4、反向迭代器的模拟实现

热门文章

最新文章

相关课程

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

[C++基础]-stack和queue

一、stack的基本知识

1、什么是栈

2、栈的基本使用

3、栈的模拟实现

二、queue的基本知识

1、什么是队列

2、队列的基本用法

3、队列的模拟实现

三、优先队列

1、优先队列的基本知识

2、仿函数

3、priority_queue的模拟实现

4、反向迭代器的模拟实现

热门文章

最新文章

相关课程

相关电子书