栈_队列_优先级队列 | 无关风月 我题序等你回
Cobb 578 0

知识储备

C++11新特性: nullptr =delete =default 构造函数默认实现 右值引用 智能指针 auto_ptr lambda表达式 <= 函数对象 auto <= 自动推导类型 迭代器 vector::iterator map<int, string>::iterator 迭代器的简化foreach遍历 无序关联容器unorderde_set\unorderde_map

C++的容器适配器 (适配器:容器没有自己实现栈或者队列的功能,是依赖上面的容器实现的功能)

  1. stack 栈 push入栈 pop出栈 top返回栈顶元素 empty判断栈空 size返回栈元素个数
  2. queue 队列 push入队 pop出队 front返回队头元素 back返回队尾元素 empty判断队空 size
  3. priority_queue 优先级队列 (底层默认是一个大根堆)
             push入堆  pop出堆  top返回堆顶元素  empty判断堆空   size

priority_queue的大根堆/小根堆


int main()
{
    priority_queue<int> q1; // 大根堆
    priority_queue<int, vector<int>, greater<int>> p; // 小根堆


    // 定义优先级队列时,传入自定义的lambda表达式
    // _Pr=less<int> operator()(int a, int b)
    //priority_queue<int, vector<int>, function<bool(int,int)>> 
    //    q2([&](int a, int b)->bool {return a > b; }); // 小根堆

    return 0;
}

双队列实现栈

双栈实现队列

双队列实现栈 双栈实现队列

栈的实现依赖于vector


template<typename T>
class stack
{
public:
    void push(T val)
    {
        vec_.push_back(val);
    }
    void pop()
    {
        vec_.pop_back();
    }
    T top()
    {
        return vec_.back();
    }
    bool empty() { return vec_.empty(); }
private:
    vector<T> vec_;
};
// stack<int> s;  s.push(20)  s.pop()    s.top()

评论区

索引目录