栈和队列

Posted on

栈和队列是两种常见的数据结构，STL容器里也为我们提供了，可以直接使用

queue

queue翻译为队列，是一种先进先出的数据结构

1
2
3
4
5
6
7
8
queue<int> q;

q.push(1); // 压入一个元素
int f = q.front(); // 获得队首元素
int b = q.back(); // 获得队尾元素
q.pop(); // 令队首元素出队
q.empty() // 判断队列是否为空
q.size()  // 返回queue中元素的个数

注意：在使用front/back时，要先进行empty的判断，避免因队空而产生错误

常见用途

  • 在实现广度优先搜索时，不需要自己手动实现一个队列

优先队列

priority_queu底层是通过堆来实现的。在优先队列中，队首的一定是当前队列中优先级最高的那一个

1
2
3
4
5
6
7
priority_queue< typename > name;

name.push();
name.top(); // 使用前，判断是否为empty
name.pop();
name.empty();
name.size();

priority_queue中元素优先级的设置

  • 对于int，double，char，遵照的优先级规则就是“数字大”的优先级高

    1
    2
    priority_queue<int> q;
    priority_queue<int, vector<int>, less<int>> q;

    上述两种方法表示的含义相同，第二种明显多了两个参数，参数的意义如下：

    • 第二个参数指承载底层数据结构（heap）的容器，如果是char/double，就改为vector<char/double>
    • 第三个参数是一个比较类，less表示数字大的优先级大；greater表示数字小的优先级大

  • 数据结构的优先级设置
    对相应数据结构的运算符进行重载即可

    1
    2
    3
    4
    5
    6
    7
    8
    struct fruit {
      string name;
      int price;
      friend bool operator < (const fruit &a, const fruit &a) {
        return a.price < b.price;
      }
    };
    priority_queue<fruit> q; // 这样就可以

常见用途

  • 可以解决一些贪心问题，也可以对Dijkstra算法进行优化

stack

stack翻译为栈，是一种后进先出的容器

1
2
3
4
5
6
7
stack< typename > name;

s.push();
s.top();
s.pop();
s.empty();
s.size();

常见用途

  • 模拟实现一些递归
    如果通过普通函数来进行递归，当嵌套深度过大时，可能会导致程序崩溃，而通过stack来模拟会好一些
    如常见的一类单调栈