STL :stack & queue & priority

栈和队列

栈：stack队列：queue优先级队列：priority_queue双端队列：deque

栈：stack

/*************************stack***********************/ stack<int> a; // 默认为双端队列 stack<int, vector<int>> stack1; // 用vector实现的栈 stack<int, list<int>> stack2; // 用list实现的栈 for (int i = 0; i < 5; i++) { a.push(i); } a.empty(); a.top(); a.pop(); a.size();

队列：queue

/*************************queue***********************/ queue<int> b; queue<int,list<int>> queue1; // queue因为pop用底层容器实现所以只能用list实现 for (int i = 0; i < 5; i++) { b.push(i); } b.front(); b.back(); b.size(); b.empty(); b.pop();

优先级队列：priority_queue

Tip:emplace可以直接传入构造对象需要的元素，然后自己调用其构造函数！

优先级队列，根据数据从大到小排列（默认情况，可以修改），特点： 自动排序 priority_queue<int, vector<int>, less<int>> p1; //从大到小的队列（默认） priority_queue<int,vector<int>, greater<int>> p2;//从小到大的队列

对象的优先级队列 需要进行 运算符重载 priority_queue<People,vector<People>,less<People>> pp；//重载< ，从大到小排列 priority_queue<People,vector<People>,greater<People>> pp；//重载> ，从小到大排列 priority_queue<People,vector<People>,greaterage> ppp；//仿函数自定义

#include<iostream> #include<stack> #include <queue> #include <list> using namespace std; class People { public: People(int id, int age) :m_id(id), m_age(age) {} int m_id; int m_age; bool operator< (const People& p) const{ return m_age < p.m_age; } bool operator> (const People& p) const { return m_age > p.m_age; } }; class greaterage { public: bool operator()(const People &p1, const People &p2) const { return p1.m_id < p2.m_id; } }; int main(int argc, char ** argv) { priority_queue<int> c; priority_queue<int, vector<int>, less<int>> p1; //从大到小的队列 priority_queue<int,vector<int>, greater<int>> p2;//从小到大的队列 for (int i = 0; i < 3; i++) { c.push(i); p1.push(i); p2.push(i); } cout << "For c:" << endl; while (!c.empty()){ cout << c.top() << endl; c.pop(); } cout << "For less<int> p1:" << endl; while (!p1.empty()){ cout << p1.top() << endl; p1.pop(); } cout << "For greater<int> p2:" << endl; while (!p2.empty()){ cout << p2.top() << endl; p2.pop(); } /*************************对象的优先级队列***********************/ People r[] = { People(1,20),People(2,28),People(3,24) }; priority_queue<People> p(r,r+3); cout << "priority_queue<People> p:" << endl; while (!p.empty()) { cout << p.top().m_age << endl; p.pop(); } priority_queue<People,vector<People>,greater<People>> pp; // 按从小到大排列，需要重载操作符> pp.emplace(1, 20); //Tip:emplace可以直接传入构造对象需要的元素，然后自己调用其构造函数！ pp.emplace(2, 28); pp.emplace(3, 24); cout << "priority_queue<People,vector<People>,greater<People>> pp:" << endl; while (!pp.empty()){ cout << pp.top().m_age << endl; pp.pop(); } /*************************用仿函数做比较优先级队列***********************/ priority_queue <People,vector<People>,greaterage> ppp(r, r + 3); cout << "use self-designe func-class to compare:" << endl; while (!ppp.empty()) { cout << ppp.top().m_id << endl; ppp.pop(); } system("pause"); return 0; }

双端队列：deque

链表和向量的结合体，可以随机访问任意位置的功能（向量），快速插入和删除元素（链表）。 包含向量的at()，[]，链表的pop_front()和push_front() 不包含链表的splice()、merge()、remove()、sort()、unique() 不包含向量的capacity()和reserve()

deque<int> a(10, 1); deque<int> b(a); deque<int> c{ 5,10,15,20,25 }; /**********************查找属性********************/ a.empty(); // 空，返回true deque<int>::size_type sz = a.size(); // 元素个数 a.resize(3, 2); // 调整大小，多删少补，值可指定否则随机 int first = a.front(); // 返回顶部元素 int last = a.back(); // 返回尾部元素 int val1 = c.at(2); int val2 = c[2]; cout << val2 << endl; /***********************增加元素*******************/ a.push_front(3); // 头插 a.push_back(4); // 尾插 deque<int>::iterator it1 = a.begin(); deque<int>::iterator it2 = a.end(); advance(it1, 3); // 迭代器指针前移3次 a.insert(it1, 5); //在迭代器位置插入5 a.insert(a.begin(), 3, 5); //在迭代器位置插入3个5 /***********************删除元素*******************/ a.pop_back(); a.pop_front(); a.erase(a.begin()); // 删除单个元素 a.erase(it1, it2); // 删除之间的所有元素 a.clear(); // size为0，存储空间不变 ///***********************修改元素*******************/ b.assign(a.begin(), a.end()); // 拷贝a b.assign(6, 7); // 删除所有结点并对b重新赋值 a.swap(b); // 交换两链表 ///***********************打印链表*******************/ for (deque<int>::iterator it1 = a.begin(), it2 = a.end(); it1 != it2; ++it1) { cout << *it1 << " "; }