Chapter 3 | Stacks and Queues

stack 、queue、priority_queue(stl)

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
using namespace std;
stack<int>s;

void _stack(){
    for(int i = 0 ; i <= 4; i++)
        s.push(i);
    cout <<s.top()<<endl;
    s.emplace(233);//对于在容器中添加类的对象时, 相比于push_back,emplace_back可以避免额外类的复制和移动操作.
    cout <<s.top()<<endl;

}
void _queue(){
    queue<int>q;
    q.push(1);
    if(!q.empty()){
        cout << q.front() <<endl;
        q.pop();
    }
}
void p_q(){
    priority_queue<int> bigtosmall;
    priority_queue<int,vector<int>,greater<int> >smalltobig;
    for(int i = 1; i <= 10 ; i++){
        bigtosmall.push(i);
        smalltobig.push(i);
    }
    while(!bigtosmall.empty()){
        cout << bigtosmall.top() <<"   ";

        bigtosmall.pop();
    }
    cout <<endl;
    while(!smalltobig.empty()){
        cout << smalltobig.top() <<"   ";
        smalltobig.pop();
    }
    cout <<endl;
}
int main(){
    _stack();
    _queue();
    p_q();
}

单调栈

实现一个栈，除了push和pop操作，还要实现min函数以返回栈中的最小值。 push，pop和min函数的时间复杂度都为O(1)。

维护一个单调递减的栈，所栈首就是当前的最小值，pop的时候如果单调栈首的序号是这个，那也要pop这个单调栈，数值可能重复，所以单调栈维护的是同一个值的最小序号。

转载于:https://www.jianshu.com/p/8dfa3b0457bd