【C++进阶】深入STL之 栈与队列:数据结构探索之旅

简介: 【C++进阶】深入STL之 栈与队列:数据结构探索之旅

前言: 在编程的世界里,数据结构是构建高效、可靠程序的基础。它们就像是我们编程工具箱中的精密工具,帮助我们解决各种复杂的问题。而在C++的STL中,栈(Stack)和队列(Queue)是两种非常重要的数据结构它们以不同的方式管理和操作数据,为我们的程序提供了极大的灵活性


📕1. stack和queue的基本概念

🎩stack的基本概念

栈(Stack)是一种后进先出(LIFO)的数据结构

  • 它的操作特性使其在处理递归调用、函数调用栈以及撤销操作等问题时表现出色。通过栈,我们可以轻松地实现如括号匹配、表达式求值等算法。


🎈queue的基本概念

队列(Queue)则是一种先进先出(FIFO)的数据结构

  • 它在处理需要按顺序处理的任务时非常有用。无论是操作系统中的任务调度,还是网络中的数据包传输,队列都扮演着不可或缺的角色。


📙2. stack与queue的常用操作

⛰️stack的常用操作

函数说明 接口说明
stack() 构造空的栈
empty() 检测stack是否为空
size() 返回stack中元素的个数
top() 返回栈顶元素
push() 将元素val压入stack中
pop() 将stack中尾部的元素弹出
void test_stack()
{
  stack<int, vector<int>> st; // 构造栈
  st.push(1); // 将元素val压入stack中
  st.push(2);
  st.push(3);
  st.push(4);
  printf("栈中有效元素个数为:%d", st.size()); // 返回stack中元素的个数
  while (!st.empty()) // 检测stack是否为空
  {
    printf("%d ", st.top()); // 返回栈顶元素的引用
    st.pop(); // 将stack中尾部的元素弹出
  }
}

相较于之前的栈的常用函数学习还是很简单的,在了解完基本用法后,这里推荐几个相关题目


🌄queue的常用操作

函数声明 接口说明
queue() 构造空的队列
empty() 检测队列是否为空,是返回true,否则返回false
size() 返回队列中有效元素的个数
front() 返回队头元素
back() 返回队尾元素
push() 在队尾将元素val入队列
pop() 将队头元素出队列
void test_queue()
{
  queue<int, list<int>> q; // 构造队列
  q.push(1); // 在队尾将元素val入队列
  q.push(2);
  q.push(3);
  q.push(4);
  printf("队列中有效元素个数为:%d", q.size()); // 返回stack中元素的个数
  while (!q.empty()) // 检测queue是否为空
  {
    printf("%d ", q.front()); // 返回队头元素
    q.pop(); // 将队头元素出队列
  }
}

相较于之前的栈的常用函数学习还是很简单的,在了解完基本用法后,这里推荐几个相关题目,不多说直接上题目巩固

最小栈

栈的压入、弹出序列

逆波兰表达式求值

用栈实现队列

用队列实现栈


📚3. 容器适配器

容器适配器是一种机制,它接受一种已有的容器类型,通过封装和改造,使其行为看起来像另一种类型。这允许我们使用特定的数据访问和操作模式(如栈、队列或优先队列)来管理容器中的数据,而无需修改原始容器的实现。

C++标准库定义了三种序列容器适配器:

容器适配器 概念
stack(栈) 栈是一种后进先出(LIFO)的数据结构,具有push(压栈)、pop(弹栈)、top(查看栈顶元素)等基本操作。在STL中,stack可以建立在vector、list、deque等容器之上。
queue(队列) 队列是一种先进先出(FIFO)的数据结构,具有push(入队)、pop(出队)、front(查看队首元素)、back(查看队尾元素)等基本操作。queue在STL中也是一个容器适配器。
priority_queue(优先队列) 优先队列是一种特殊的队列,其中元素的出队顺序不是按照它们进入队列的顺序,而是根据它们的优先级。priority_queue提供了push(插入元素)、pop(删除最高优先级元素)、top(查看最高优先级元素)等操作。

虽然stack和queue中也可以存放元素,但在STL中并没有将其划分在容器的行列,而是将其称为容器适配器, 这是因为stack和队列只是对其他容器的接口进行了包装,STL中stack和queue默认使用deque,这个在stack和queue的基本概念中可以看到。

有了容器适配器后,我们在模拟实现时,就不需要自己再从底层出发,而是可以直接调用已经存在的容器


📒4. deque的简单介绍

💧deque的原理介绍

deque(双端队列):是一种双开口的"连续"空间的数据结构

  • 双开口的含义是:可以在头尾两端进行插入和删除操作,且时间复杂度为O(1),与vector比较,头插效率高,不需要搬移元素;与list比较,空间利用率比较高

注意:deque并不是真正连续的空间,而是由一段段连续的小空间拼接而成的,实际deque类似于一个动态的二维数组

我们查表发现deque基本上包含了vector与list的用法,那我们之前为什么还要费尽心思去学习呢?直接学习deque不好吗?


🌊deque的缺陷

与vector比较

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

与list比较

  • 其底层是连续空间,空间利用率比较高,不需要存储额外字段。但是,deque有一个致命缺陷:不适合遍历,因为在遍历时,deque的迭代器要频繁的去检测其是否移动到某段小空间的边界,导致效率低下,

在序列式场景中,可能需要经常遍历,因此在实际中,需要线性结构时,大多数情况下优先考虑vector和list,deque的应用并不多,而目前能看到的一个应用就是,STL用其作为stack和queue的底层数据结构

因此我们还是要单独学习list和vector的


📜5. stack和queue的模拟实现

在模拟实现这俩个容器的时候,我们只要实现它的常用函数,在模拟实现时,我们只需要复用就可以了

🍂stack的模拟实现

template<class T, class Container = 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();
  }
  bool empty()
  {
    return _con.empty();
  }
  size_t size()
  {
    _con.size();
  }
private:
  Container _con;
};

🍁queue的模拟实现

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

关于stack与queue的模拟实现就是复用之前学过的函数,没什么好说的,让我们进入重头戏


📖6. priority_queue

🌞priority_queue的基本概念

关于优先级队列,我们就可以把它想象成堆那样的结构

优先级队列默认使用vector作为其底层存储数据的容器,在vector上又使用了堆算法将vector中元素构造成

堆的结构,因此priority_queue就是堆,所有需要用到堆的位置,都可以考虑使用priority_queue

注意:默认情况下priority_queue是大堆


🌙priority_queue的常用操作

函数声明 接口说明
priority_queue()/priority_queue(first,last) 构造一个空的优先级队列
empty( ) 检测优先级队列是否为空,是返回true,否则返回false
top( ) 返回优先级队列中最大(最小元素),即堆顶元素
push(x) 在优先级队列中插入元素x
pop() 删除优先级队列中最大(最小)元素,即堆顶元素
void test_priority_queue()
{
  std::priority_queue<int> q; // 构造优先级队列
  q.push(1); // 在优先级队列中插入元素x
  q.push(43);
  q.push(233);
  q.push(43);
  q.push(4);
  q.push(73);
  q.push(2);
  while (!q.empty()) // 检测优先级队列是否为空
  {
    printf("%d ", q.top()); // 返回堆顶元素
    q.pop(); // 删除堆顶元素
  }
}

⭐priority_queue的模拟实现

// 仿函数,数据的比较方法
template<class T>
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 = 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() - 2) / 2; i >= 0; i--)
    {
      AdjustDown(i);
    }
  }
  void AdjustUp(int child) // 向上调整
  {
    int parent = (child - 1) / 2;
    Compare com;
    while (child > 0)
    {
      if (com(_con[child], _con[parent]))
      {
        swap(_con[child], _con[parent]);
        child = parent;
        parent = (child - 1) / 2;
      }
      else
      {
        break;
      }
    }
  }
  void AdjustDown(int parent) // 向下调整
  {
    int child = parent * 2 + 1;
    Compare com;
    while (com(child , _con.size()))
    {
      if ((child + 1 < _con.size()) &&
        com(_con[child + 1], _con[child]))
      {
        child++;
      }
      if (com(_con[child] , _con[parent]))
      {
        swap(_con[child], _con[parent]);
        parent = child;
        child = parent * 2 + 1;
      }
      else
      {
        break;
      }
    }
  }
  void push(const T& x)
  {
    _con.push_back(x);
    AdjustUp(_con.size() - 1); // 在插入新元素时,我们要调整容器里面的元素
  }
  size_t size()
  {
    return _con.size();
  }
  const T& top()
  {
    return _con[0];
  }
  void pop()
  {
    swap(_con[0], _con[_con.size() - 1]);
    _con.pop_back(); 
    AdjustDown(0); // 删除时,依旧要调整元素
  }
  bool empty()
  {
    return _con.empty();
  }
private:
  Container _con;
};

关于priority_queue的模拟实现,依然是以复用为主,只不过多了一些堆要使用的调整函数,而且我们在查priority_queue这个容器时,不难发现其实它是有三个模板参数的,它的第三个模板参数就是,数据的排列方式,也就是决定大小堆的,这就涉及到了仿函数,关于仿函数,下节我们在讲!


🔥7. 总结

在深入探讨了STL(Standard Template Library)中的栈(stack)与队列(queue)之后,我们不难发现这两大数据结构在程序设计中扮演着至关重要的角色。栈与队列的引入,不仅极大地丰富了C++程序员的工具箱,也为解决各种实际问题提供了更为高效、优雅的方法

学习栈与队列并不仅仅是为了掌握它们的基本操作和应用场景。更重要的是,我们要学会如何根据问题的特点选择合适的数据结构,以及如何有效地利用数据结构来解决实际问题。在这个过程中,我们需要不断思考、探索和实践,才能不断提升自己的编程能力和问题解决能力。让我们继续前行,不断探索编程的奥秘,享受编程的乐趣!

谢谢大家支持本篇到这里就结束了,端午安康,祝大家天天开心!


目录
相关文章
|
8天前
|
设计模式 算法 Java
【c++】STL之stack和queue详解
【c++】STL之stack和queue详解
10 1
|
15天前
|
存储 算法 C++
【C++高阶】探索STL的瑰宝 map与set:高效数据结构的奥秘与技巧
【C++高阶】探索STL的瑰宝 map与set:高效数据结构的奥秘与技巧
24 0
|
16天前
|
存储 算法 数据处理
【C++】STL简介
**STL是C++标准库的关键部分,源于Alexander Stepanov的泛型编程研究。它提供了数据结构(如vector、list)和算法,是高效、通用的软件框架。STL始于惠普,后由SGI发展,现已成为C++1998标准的一部分并不断进化。它包括容器、迭代器、算法、仿函数、配接器和分配器六大组件,带来高效性、通用性和可扩展性,但也存在性能开销和学习难度。学习STL涉及理解底层数据结构、用法、实现和实践。推荐[cplusplus.com](https://cplusplus.com)作为学习资源。**
|
16天前
|
存储 算法 程序员
C++基础知识(八:STL标准库(Vectors和list))
C++ STL (Standard Template Library标准模板库) 是通用类模板和算法的集合,它提供给程序员一些标准的数据结构的实现如 queues(队列), lists(链表), 和 stacks(栈)等. STL容器的提供是为了让开发者可以更高效率的去开发,同时我们应该也需要知道他们的底层实现,这样在出现错误的时候我们才知道一些原因,才可以更好的去解决问题。
|
24天前
|
算法 C语言
【数据结构与算法 经典例题】使用栈实现队列(图文详解)
【数据结构与算法 经典例题】使用栈实现队列(图文详解)
|
1天前
【数据结构OJ题】用队列实现栈
力扣题目——用队列实现栈
11 0
【数据结构OJ题】用队列实现栈
|
19天前
|
存储 缓存 算法
堆和栈的区别及应用场景
堆和栈的区别及应用场景
|
25天前
|
存储 测试技术
【数据结构】操作受限的线性表,栈的具体实现
【数据结构】操作受限的线性表,栈的具体实现
28 5
|
24天前
|
算法 C语言
【数据结构与算法 经典例题】使用队列实现栈(图文详解)
【数据结构与算法 经典例题】使用队列实现栈(图文详解)
|
25天前
|
算法
【C/数据结构和算法】:栈和队列
【C/数据结构和算法】:栈和队列
28 1