Stack&&Queue

时间:2021-11-09 17:55:47
特殊的容器:容器适配器
stack     queue     priority_queue:vector+堆算法---->优先级队列
stack:
    1.栈的概念:特殊的线性结构,只允许在其一端进行插入删除操作---栈顶,另一端称为栈底
    2.栈的特性:后进先出 LIFO 
    3.栈的作用:
    4.栈的应用:
    #include<iostream>
    using namespace std;
    class Date
    {
        public:
        Date(int year=1900,int month=11,int day=10){
            _year=year;
            _month=month;
            _day=day;
        }
        Date(const Date& d){
            _year=d._year;
            _month=d._month;
            _day=d._day;
        }
        private:
        int _year;
        int _month;
        int _day;
    }
    int main(){
    Date d;
    stack<Date> s;
    s.push(d);//参数为类类型对象的引用
    s.empace(2018,11,10);//效率比较高,不会调用拷贝构造
    return 0;
    }
    栈中没有迭代器,不需要,因为栈的操作已经给死了
最小栈:必须满足栈的特性
    push/pop/top--->O(1)
    min--->O(1)
    实现最小栈的方法:使用两个栈A、B(一个放最小值,一个放数据),一个栈也行
struct Elem{
     int data;
    int min;
}
stack<int> _data;
stack<int> _min;
int top(){
  return data.top();
}
int getmin(){
 return _min.top();
}
void Pop(){
    
}
void Push(int x){
 _data.push(x);
 if(_min.empty()||_min.top()>=x){
    _min.push(x);
    }
}
    逆波兰表达式:
class Solution{
public: 
    int evalRPN(vector<string>& tokens){
        stack<int> s;
        for(size_t i=0;i<tokens.size();++i){
            string& str =tokens[i];
            if(!("+"==str||"-"==str||"*"==str||"/"==str)){
                s.push(atoi(str.c_str()));
            else{
                int right=s.top(),s.pop();
                int left=s.top(),s.pop();
                switch(str[0]){
                case '+':
                    s.push(left+right);
                    break;
                case '-':
                    s.push(left-right);
                    break;
                case '*':
                         s.push(left*right);
                    break;
                case '/':
                    s.push(left/right);
                    break;
                }
            }
        }
    return s.top();
}
 
二叉树的公共祖先结点:
bool GetNoePath(TreeNode * root,TreeNode *p,Stack<TreeNode*>& Path){
    if(NULL==root||NULL==p){
        return false;
    }
    path.push(root);
    if(root==p)
        rturn true;
    if(GetNodePath(root->left,p,path)){
        return true;
    if(GetNodePath(root->rigth,p,path)){
        retrn true;
    path.pop();
    return false;
}
 
TreeNode* lowestCommonAncestor(TreeNode* root,TreeNode* p,TreeNode *q){
    if(NULL==root||NULL==p||NULL==q){
        return NULL;
    }
    stack<TreeNode*> s1;
    stack<TreeNode*> s2;
    GetNodePath(root,p,s1);
    GetNodePath(root,q,s2);
    int size1=s1.size();
    int size2=s2.size();
    while(size1&&size2){
        if(size1<size2){
            s1.pop();
            size1--;
        }
        else if(size2<size1){
            s2.pop();
            size2--;
            }
        else{
            if(s1.top()==s2.top()){
                return s1.top();
            else{
                s1.pop();
                s2.pop();
                size1--;
                size2--;
                }
        }
    return NULL;
}
 
bool IsNodeInTree(root,Node){
    if(NULL==root||node==NULL){
        return false;
    }
    if(root==Node){
        return true;
    }
    bool Ret=false;
    if(Ret==IsNodeInTree(root->left,Node){
        return true;
    return IsNodeInTree(root->right,Node);
}
TreeNode* lowestCommonAncestor(TreeNode* root,TreeNode* p,TreeNode *q){
    if(NULL==root||NULL==p||NULL==q){
        return NULL;
    if(p==root||q==root){
        return root;
    bool isleft1=IsNodeInTree(root->left,p);
    bool isright2=false;
    if(isleft1){
        isright2=IsNodeInTree(root->right,q);
        if(isright2){
            return root;
        }
    }
    bool islift2=IsNodeTree(root->left,q)
    if(islift2)
        bool isright2=IsNodeTree(root->right,p);
        if(isright2){
            return root;
        }
    }
    if(isleft1&&isleft2){
        return lowestCommonAncestor(root->left,p,q);
    return lowestCommonAncestor(root->right,p,q);
}
        
 
 
二叉树的层序遍历:
层序遍历:按照从上往下,每一层从左往右依次遍历
   根据队列的数据结构进行操作
   1.将根节点放入到队列中
   循环:循环结束条件(队列不为空(!EMptyQueue(&q)))
      从队列中取队头元素
      访问该元素
      如果该元素的左子树存在,入队列
      如果该元素的右子树存在,入队列
      将对头元素出队列
vector<vector<int>> leve10Order(TreeNode* root){
    vector<vector<int>> vRet;
    if(NULL==root){
        return vRet;
    }
    Queue<TreeNode*> q;
    q.push(root);
    while(!q.empty()){
        size_t leve1count=q.size();
        vector<int> levelData;
        for(size_t i=0;i<levecount;++i){
            TreeNode* pCur=q.front();
            levelData.push_back(pCur->val);
            q.pop();
            if(pCur->left){
                q.push(pCur->left);
            }
            if(pCur->right){
                q.push(pCur->right);
            }
        vRet.push_back(levelData);
    }
    return vRet;
}
 
 
priority_queue:
    template<class T,class Con= vector<T>,class Compare=less<T>>
less   greater
    priority_queue<int ,vector<int>,greater<int>> 
    greater默认按照大于号方式给,创建小堆(此时vector<int(类型)一定要给,否则报错)
    默认:less  小于方式比  ---->  创建了大堆
 
topk问题:
    sort(array,array+6);给数组排序,
    sort(array,array+6,greater<int>)
 
 
 

相关文章