C++_course.cpp

# -*- coding: utf-8 -*-
"""C++_course.ipynb

Automatically generated by Colab.

Original file is located at
    https://colab.research.google.com/drive/1rBj1UVXLSGdK1Jhb3N24NbBPcgbT7cnN
"""

#include <iostream>
using namespace std;
int main() {
    std::cout << "Hello World!" << endl;
    //comment
    int age =10;
    char grade = 'A';
    float PI = 3.14f;
    double price = 100.99;
    bool issafe = true;
    cout<<age<<endl;
    int value = grade;
    cout<<grade<<endl;
    cout<<value<<endl;
    int newprice=(int)price;
    cout<<newprice<<endl;
    int x;
    cout<<"input:"<<endl;
    //cin>>x;
    //cout<<x;
    int a=10,b=5;
    cout<<(a+b) <<endl<< (a-b)<<endl<< (a*b)<<endl<< (a/b)<<endl<< (a%b)<<endl;
    //==,!=,<,>,<=,>=
    //||(or),&&(and),!(not)
    int a1=10;
    int b1=a1++;
    cout<<a1<<endl<<b1<<endl;
    int c1=++a1;
    cout<<a1<<endl<<c1<<endl;
    int a2=10;
    int b2=a2--;
    cout<<a2<<endl<<b2<<endl;
    int c2=--a2;
    cout<<a2<<endl<<c2<<endl;
    return 0;
}

int main(){
    int n1=4
    long int n2=8
    short int n3=2
    long long int n4=8
    signed int n5=4
    unsigned int n5=-4
}

int main() {
    int a=0;
    int n=0;
    if (a>100){
        cout<<"100"<<endl;
    }else if(a==50){
        cout<<"50"<<endl;
    }else{
        cout<<"0"<<endl;
    }
    cout<<(n>=0 ? "p":"n")<<endl;
    return 0;
}

int main() {
    int c= 1;
    while(c<5){
        cout<<c;
        c++;
    }
    cout<<endl;
    for (int i=1;i<=7;i++){
        cout<<i;
        if (i==5){
            break;
        }
    }
    cout<<endl;
    do{
       cout<<c;
       c++;
    }while(c<10);
    cout<<endl;
    return 0;
}

int main() {
    int n = 4;
    for ( int i=0; i<n; i++) {
        char ch = 'A';
        for ( int j=0; j<n; j++) {
            cout << ch;
            ch = ch + 1;
        }
        cout<< endl;
    }
    return 0;
}
int main() {
    int n = 6;
    for( int i=0; i<n; i++) {
        for(int j=0; j<i+1; j++) {
            cout<<"*" ;
        }
        cout<< endl;
    }
    return 0;
}

int v3(){
    cout<<"hello\n";
    return 3;
}
double dd(double a, double b){
    double s=a+b;
    return s;
}
void t(){
    cout<<"hello\n";
}
int main()
{
    int v=v3();
    cout<<v<<endl;
    cout<<dd(4,5)<<endl;
    t();

    return 0;
}

//pass by value
int sum_v(int a, int b){
    a += 10;//15
    b += 10;//14
    return a+b;//29
}
//pass by reference
int sum_r(int &a, int &b){
    a+=10;//15
    b+=10;//14
    return a+b;//29
}
int main(){
    int a=5 , b=4;
    cout << sum_v(a, b) << endl;
    cout << a << endl;
    cout << b << endl;
    cout << sum_r(a, b) << endl;
    cout << a << endl;
    cout << b << endl;
    return 0;
}

//bitwise operator:-
//&(and) |(or) ^(xor) <<(left shift) >>(right shift)
//operator precendenc:-
//(! ++ --) (* / %) (+ -) (< <= > >=) (== !=) (&&) (||) (=)

int main(){
    int n1=4
    long int n2=8
    short int n3=2
    long long int n4=8
    signed int n5=4
    unsigned int n5=-4
}

int main(){
    int arr[5]={1,2,3,4,5};
    string ar1[5]={"a","b","c"};
    ar1[3]="d"
    return 0;
}

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    vector<int> vec={1,2,3};
    vector<int> v1(5,0);
    vector<int> v2(vec);
    //vec.size().capacity().front().back().at()
    //vec.push_front()push_back().pop_back().pop_front().emplace_back().emplace_front()
    //vec.erase(vec.begin()+pos).erase(start,end)
    //vec.insert(vec.begin()+pos).insert(pos,val)
    //vec.clear().empty().resize().swap()
    //sort(vec.begin(),vec.end()) reverce(vec.begin(),vec.end())
    for (int i :v1){
        cout<<i<<endl;}
    vector<int>::iterator it;
    for(it=vec.begin();it!=vec.end();it++){
        cout<<*(it)<<endl;}
    vector<int>::reverse_iterator itr;
    for(itr=vec.rbegin();itr!=vec.rend();itr++){
        cout<<*(itr)<<' ';}
    for(auto ita=vec.begin();ita!=vec.end();ita++){
        cout<<*(ita)<<' ';}
}

#include <iostream>
#include <vector>
using namespace std;
int main(){
    int a =10;
    int* ptr=&a;
    int** parptr=&ptr;
    cout<<&a<<endl;
    cout<<ptr<<endl;
    cout<<&ptr<<endl;
    cout<<parptr<<endl;
    cout<<*(&a)<<endl;
    cout<<*(ptr)<<endl;
    cout<<**(parptr)<<endl;

    int** nptr=NULL;
    cout<<nptr<<endl;

    return 0;
}

#include <iostream>
#include <vector>
using namespace std;
void unchange(int a) // pass by value
{a=20;}
void change(int* ptr) // pass by reference
{*ptr=20;}
int main(){
    int a=10, b=15;
    int arr[]={1,2,3,4,5};
    unchange(a);
    cout<<a<<endl;
    change(&a);
    cout<<a<<endl;

    int* ptr1=&b;
    ptr1=&a;
    //arr=&a(doesnt work)
    //arrays are constent pointter

    cout<<ptr1<<endl;
    ptr1++; // 4 bits for int dtype
    cout<<ptr1<<endl;

    cout<<arr<<endl;
    cout<<*arr<<endl;
    cout<<*arr+1<<endl;

    int* ptr2=ptr1+1;
    cout<<ptr2-ptr1<<endl;
    cout<<(ptr2!=ptr1)<<endl;
    // & used for address
    // * used for dereference
    return 0;

}

#include <iostream>
#include <vector>
#include <list>
using namespace std;
int main(){
    list<int>l{1,2,3,4,5};
    //list=doubly linked list
    //l.push_front().push_back().pop_back().pop_front().emplace_front().emplace_back()
    //l.size().insert().erase().clean().front().back().begin().end().rbegin().rend()
    for (int i :l){
        cout<<i<<endl;}
    return 0;
}

#include <iostream>
#include <vector>
#include <deque>
using namespace std;
int main()
{
    deque<int>d{1,2,3,4,5};
    //deque=dynamic array
    //d.push_front().push_back().pop_back().pop_front().emplace_front().emplace_back()
    //d.size().insert().erase().clean().front().back().begin().end().rbegin().rend()
    for (int i :d){
        cout<<i<<endl;}
    return 0;
}

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    pair<char,int>p={'a',1};
    cout<<p.first<<p.second<<endl;
    pair<int,pair<int,int>>pp={1,{2,3}};
    cout<<pp.first<<pp.second.first<<endl;
    vector<pair<int,int>> v={{1,2},{2,3},{3,4}};
    v.push_back({4,5});//insert
    v.emplace_back(5,6);//inplace object create (faster)
    for (auto vp:v){
        cout<<vp.first<<vp.second<<endl;}
    return 0;
}

#include <iostream>
#include <vector>
#include <list>
#include <deque>
#include <stack>
using namespace std;
int main()
{
    stack<int>s;
    //s.push().emplace().top().pop().size().empty().swap()
    s.push(1);
    s.push(2);
    s.push(3);
    s.push(4);
    s.push(5);
    while(!s.empty()){
        cout<<s.top()<<endl;
        s.pop();}
    return 0;
}

#include <iostream>
#include <vector>
#include <list>
#include <deque>
#include <queue>
using namespace std;
int main()
{
    queue<int>q;
    //q.push().emplace().front().pop().size().empty().swap()
    q.push(1);
    q.push(2);
    q.push(3);
    q.push(4);
    q.push(5);
    while(!s.empty()){
        cout<<s.front()<<endl;
        s.pop();}
    priority_queue<int,vector<int>,greater<int>>pq;
    pq.push(2);
    pq.push(1);
    pq.push(3);
    while(!pq.empty()){
        cout<<pq.top()<<endl;
        pq.pop();}
    return 0;
}

#include <iostream>
#include <vector>
#include <list>
#include <deque>
#include <stack>
#include <queue>
#include <map>
#include <unorder_map>
using namespace std;
int main()
{
    map<string,int>m;
    m["a"]=1;
    m.insert({"b",2});
    m.emplace("c",3);
    //m.count().find().size().empty().erase()
    //O(log(n))
    multimap<string,int>mm;
    //multimap can store samething
    //mm.erase()->erase all samething
    //mm.erase(mm.find())->erase onething
    mm.insert({"a",1});
    mm.emplace("a",1);
    for(auto i:mm){
        cout<<i.first<<i.second<<endl;}
    unordered_map<string,int>um;
    //not stored in order of key
    //fast O(1)
    um["c"]=3;
    um.insert({"a",1});
    um.emplace("b",2);
    for(auto i:um){
        cout<<i.first<<i.second<<endl;}
    return 0;
}

#include <iostream>
#include <vector>
#include <list>
#include <deque>
#include <stack>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
using namespace std;
int main()
{
    set<int>s={3,2,1};
    //unique value,order,O(logn)
    //s.insert().emplace().merge().size().count().find()
    //s.erase().empty().begin().end()
    s.insert(1);
    s.emplace(1);
    cout<<*(s.lower_bound(2))<<endl;
    //gives that one if not there then upper to that,no upper then last one
    cout<<*(s.upper_bound(10))<<endl;
    //gives upper one if not there then last one
    for(auto i:s){
        cout<<i<<endl;}
    multiset<int>ms={3,2,1};
    //not unique,order,O(logn)
    unordered_set<int>us={3,2,1};
    //unique,not order,no lb or ub,O(1)
    return 0;
}

#include <iostream>
#include <vector>
#include <list>
#include <deque>
#include <stack>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <algorithm>
using namespace std;
bool comparator(pair<int,int>a,pair<int,int>b){
    if (a.second<b.second) return true;
    else return false;}
int main(){
    vector<pair<int,int>> v={{2,4},{1,5},{3,3},{5,1},{4,2}};
    sort(v.begin(),v.end());
    for (auto i:v){
        cout<<i.first<<' '<<i.second<<endl;}
    sort(v.begin(),v.end(),greater<pair<int,int>>());
    sort(v.begin(),v.end(),comparator);//same work
    for (auto i:v){
        cout<<i.first<<' '<<i.second<<endl;}
    //reverse(),next_permutation(),prev_permutation()
    //swap(),min(),max(),max_element(),min_element()
    //binary_search(),builtin_popcount()
    return 0;
}

#include <iostream>
using namespace std;
void pn(int n){
    cout<<' '<<n<<' ';
    if(n==1){
        cout<<" #"<<n<<"# ";
        cout<<" *"<<n<<"* ";
        return;
    }
    cout<<" #"<<n<<"# ";
    pn(n-1);
    cout<<" *"<<n<<"* ";
}
int main(){
    pn(5);
    return 0;
}

#include <iostream>
#include <vector>
using namespace std;
void bt(vector<int> &arr, vector<int> &ans,int h){
    if(h==arr.size()){
        for(int i:ans){
            cout<<i<<" ";
        }
        cout<<endl;
        return;
    }
    ans.push_back(arr[h]);
    bt(arr,ans,h+1);
    ans.pop_back();
    bt(arr,ans,h+1);
}
int main(){
    vector<int> arr={1,2,3};
    vector<int> ans;
    bt(arr,ans,0);
    return 0;
}

#include <iostream>
using namespace std;

class cc{
    private:
        string apv;
        string bpv;
    public:
        string apb;
        string bpb;
        string cpb;
        cc(){//non-parameterized constructor
            cout<<"this in is non-parameterized constructor"<<endl;
            this->cpb="np-cb1";
        }
        cc(string c){//parameterized constructor
            cout<<"this in is parameterized constructor"<<endl;
            this->cpb=c;
        }
        cc(cc &orgObj){//copy constructor
            cout<<"this in is copy constructor"<<endl;
            this->cpb=orgObj.cpb;
        }
        void method1(string napb){
            this->apb=napb;
        }
        //sets a private varible
        void setter(string napv){
            this->apv=napv;
        }
        //gets a private varible
        string getter(){
            return this->apv;
        }
};
int main(){
    cc c1;
    c1.apb="ab1";
    c1.bpb="bb1";
    cout<<c1.apb<<endl;
    c1.method1("ab2");
    cout<<c1.apb<<endl;
    c1.setter("av1");
    cout<<c1.getter()<<endl;
    cout<<c1.cpb<<endl;
    cc c2("cb1");
    cout<<c2.cpb<<endl;
    //defult copy constructor
    //custom copy constructor
    cc c3(c2);
    cout<<c3.cpb<<endl;
    return 0;
}

#include <iostream>
using namespace std;

class cc{
    private:
        string apv;
        string bpv;
    public:
        string apb;
        string bpb;
        string cpb;
        string *shpbPtr;//shallow copy
        string *depbPtr;//deep copy
        cc(){//non-parameterized constructor
            cout<<"this in is non-parameterized constructor"<<endl;
            this->cpb="np-cb1";
        }
        cc(string c){//parameterized constructor
            cout<<"this in is parameterized constructor"<<endl;
            this->cpb=c;
            shpbPtr=new string;
            *shpbPtr="sb1";
            depbPtr=new string;
            *depbPtr="db1";
        }
        cc(cc &orgObj){//copy constructor
            cout<<"this in is copy constructor"<<endl;
            this->cpb=orgObj.cpb;
            this->shpbPtr=orgObj.shpbPtr;
            depbPtr=new string;
            *depbPtr=*orgObj.depbPtr;
        }
        ~cc(){//destructor
            cout<<"this delets constructor"<<endl;
            delete shpbPtr;
            delete depbPtr;
        }
        void method1(string napb){
            this->apb=napb;
        }
        //sets a private varible
        void setter(string napv){
            this->apv=napv;
        }
        //gets a private varible
        string getter(){
            return this->apv;
        }
};
int main(){
    cc c1;
    c1.apb="ab1";
    c1.bpb="bb1";
    cout<<c1.apb<<endl;
    c1.method1("ab2");
    cout<<c1.apb<<endl;
    c1.setter("av1");
    cout<<c1.getter()<<endl;
    cout<<c1.cpb<<endl;
    cc c2("cb1");
    cout<<c2.cpb<<endl;
    //defult copy constructor
    //custom copy constructor
    cc c3(c2);
    cout<<c3.cpb<<endl;
    //shallow copy
    cout<<*c3.shpbPtr<<endl;
    *c3.shpbPtr="sb2";
    cout<<*c2.shpbPtr<<endl;//changed
    cout<<*c3.shpbPtr<<endl;
    //deep copy
    cout<<*c3.depbPtr<<endl;
    *c3.depbPtr="db2";
    cout<<*c2.depbPtr<<endl;//unchanged
    cout<<*c3.depbPtr<<endl;
    return 0;
}

//hybride inheritance
//multilavel inheritance
//multipath inheritance
class gpa{//grand parent class
    public:
    string gpa1in;
};
//hierarchical inheritance
class pa1:virtual public gpa{//parent class
    public:
    string pa1in;
};
class pa2:virtual public gpa{//parent class
    public:
    string pa2in;
};
//multiple inheritance
class chi:public pa1,public pa2{//child class
    public:
    string ch1in;
};
//inheriting constructor
class con_pa{
    public:
    string con;
    con_pa(string c){
        this->con=c;
    }
};
class con_ch:public con_pa{
    public:
    con_ch(string c):con_pa(c){
        this->con=c;
    }
};
int main(){
    chi kid1;
    kid1.gpa1in="gpa1in_ch_1";
    cout<<kid1.gpa1in<<endl;
    //polymorphism constructor
    con_ch conc1("con1");
    cout<<conc1.con<<endl;
    return 0;
}

class con_pa{
    public:
    string con;
    con_pa(string c){
        this->con=c;
    }
    void same_method(){
        cout<<"parent's met"<<endl;
    }
    virtual void vir_fun(){
        cout<<"parent's vf"<<endl;
    }
};
class con_ch:public con_pa{
    public:
    con_ch(string c):con_pa(c){
        this->con=c;
    }
    void same_method(){
        cout<<"child's met"<<endl;
    }
    void same_method(string x){
        cout<<"string"<<endl;
    }
    void same_method(int x){
        cout<<"integer"<<endl;
    }
    virtual void vir_fun(){
        cout<<"child's vf"<<endl;
    }

};
int main(){
    //polymorphism constructor
    con_ch conc1("con1");
    cout<<conc1.con<<endl;
    //polymorphism method
    conc1.same_method("10");
    conc1.same_method(10);
    //overriding
    conc1.same_method();
    //virtual function
    conc1.vir_fun();
    return 0;
}

class abst{//abstract class
    public:
    //pure virtual function
    virtual void pvf() = 0;
};
class aa:public abst{//derived class
    public:
    //forced implement
    void pvf() override{
        cout<<"override"<<endl;
    }
};
int main(){
    //abstraction
    abst* a1= new aa();
    a1->pvf();
    return 0;
}

class sta{
    public:
    //shared by all objects
    //static Variables
    static int count;
    string s;
    sta(string s){
        cout<<"construct"<<endl;
        this->s=s;
        count++;
    }
    ~sta(){
        cout<<s<<endl;
    }
};
//initialize static variable outside class
int sta::count=0;
int main(){
    //static keyword
    sta st1("destruct-st1");
    //static object
    static sta st2("destructor-st2");
    cout<<sta::count<<endl;
    cout<<"end main"<<endl;
    return 0;
}

#include <iostream>
using namespace std;
class cc{
    private:
        string apv;
        string bpv;
    public:
        string apb;
        string bpb;
        string cpb;
        string *shpbPtr;//shallow copy
        string *depbPtr;//deep copy
        cc(){//non-parameterized constructor
            cout<<"this is default constructor"<<endl;
            this->cpb="np-cb1";
        }
        cc(string c){//parameterized constructor
            cout<<"this is parameterized constructor"<<endl;
            this->cpb=c;
            shpbPtr=new string;
            *shpbPtr="sb1";
            depbPtr=new string;
            *depbPtr="db1";
        }
        cc(cc &orgObj){//copy constructor
            cout<<"this is copy constructor"<<endl;
            this->cpb=orgObj.cpb;
            this->shpbPtr=orgObj.shpbPtr;
            depbPtr=new string;
            *depbPtr=*orgObj.depbPtr;
        }
        ~cc(){//destructor
            cout<<"this delets constructor"<<endl;
            delete shpbPtr;
            delete depbPtr;
        }
        void method1(string napb){
            this->apb=napb;
        }
        //sets a private varible
        void setter(string napv){
            this->apv=napv;
        }
        //gets a private varible
        string getter(){
            return this->apv;
        }
};
//hybride inheritance
//multilavel inheritance
//multipath inheritance
class gpa{//grand parent class
    public:
    string gpa1in;
};
//hierarchical inheritance
class pa1:virtual public gpa{//parent class
    public:
    string pa1in;
};
class pa2:virtual public gpa{//parent class
    public:
    string pa2in;
};
//multiple inheritance
class ch1:public pa1,public pa2{//child class
    public:
    string ch1in;
};
//inheriting constructor
class con_pa{
    public:
    string con;
    con_pa(string c){
        this->con=c;
    }
    void same_method(){
        cout<<"parent's met"<<endl;
    }
    virtual void vir_fun(){
        cout<<"parent's vf"<<endl;
    }
};
class con_ch:public con_pa{
    public:
    con_ch(string c):con_pa(c){
        this->con=c;
    }
    void same_method(){
        cout<<"child's met"<<endl;
    }
    void same_method(string x){
        cout<<"string"<<endl;
    }
    void same_method(int x){
        cout<<"integer"<<endl;
    }
    virtual void vir_fun(){
        cout<<"child's vf"<<endl;
    }

};
class abst{//abstract class
    public:
    //pure virtual function
    virtual void pvf() = 0;
};
class aa:public abst{//derived class
    public:
    //forced implement
    void pvf() override{
        cout<<"override"<<endl;
    }
};
class sta{
    public:
    //shared by all objects
    //static Variables
    static int count;
    string s;
    sta(string s){
        cout<<"construct"<<endl;
        this->s=s;
        count++;
    }
    ~sta(){
        cout<<s<<endl;
    }
};
//initialize static variable outside class
int sta::count=0;
int main(){
    cc c1;
    c1.apb="ab1";
    c1.bpb="bb1";
    cout<<c1.apb<<endl;
    c1.method1("ab2");
    cout<<c1.apb<<endl;
    c1.setter("av1");
    cout<<c1.getter()<<endl;
    cout<<c1.cpb<<endl;
    cc c2("cb1");
    cout<<c2.cpb<<endl;
    //defult copy constructor
    //custom copy constructor
    cc c3(c2);
    cout<<c3.cpb<<endl;
    //shallow copy
    cout<<*c3.shpbPtr<<endl;
    *c3.shpbPtr="sb2";
    cout<<*c2.shpbPtr<<endl;//changed
    cout<<*c3.shpbPtr<<endl;
    //deep copy
    cout<<*c3.depbPtr<<endl;
    *c3.depbPtr="db2";
    cout<<*c2.depbPtr<<endl;//unchanged
    cout<<*c3.depbPtr<<endl;
    ch1 kid1;
    kid1.gpa1in="gpa1in_ch_1";
    cout<<kid1.gpa1in<<endl;
    //polymorphism constructor
    con_ch conc1("con1");
    cout<<conc1.con<<endl;
    //polymorphism method
    conc1.same_method("10");
    conc1.same_method(10);
    //overriding
    conc1.same_method();
    //virtual function
    conc1.vir_fun();
    //abstraction
    abst* a1= new aa();
    a1->pvf();
    //static keyword
    sta st1("destruct-st1");
    //static object
    static sta st2("destructor-st2");
    cout<<sta::count<<endl;
    cout<<"end main"<<endl;
    return 0;
}

#include <iostream>
using namespace std;
class Node{
    public:
        int data;
        Node* next;
        Node(int val){
            data=val;
            next=nullptr;
        }
};
class List{
    Node* head;
    Node* tail;
    public:
    List(){
            head=tail=nullptr;
    }
    void printLL(){
        Node* temp=head;
        while(temp!=nullptr){
            cout<<temp->data<<"->";
            temp=temp->next;
        }
        cout<<"null"<<endl;
    }
    void push_front(int val){
        Node* newNode= new Node(val);
        if(head==nullptr){
            head=tail=newNode;
            return;
        }else{
            newNode->next=head;
            head=newNode;
        }
    }
    void push_back(int val){
        Node* newNode= new Node(val);
        if(tail==nullptr){
            head=tail=newNode;
            return;
        }else{
            tail->next=newNode;
            tail=newNode;
        }
    }
    void insert(int val, int pos){
        if(pos<0){
            cout<<"invalid pos\n";
            return;
        }
        if(pos==0){
            push_front(val);
            return;
        }
        Node* temp=head;
        for(int i=0;i<pos-1;i++){
            temp=temp->next;
        }
        Node* newNode= new Node(val);
        newNode->next=temp->next;
        temp->next=newNode;
    }
    void pop_front(){
        if(head==nullptr){
            cout<<"LL is empty"<<endl;
            return;
        }
        Node* temp=head;
        head=head->next;
        temp->next=nullptr;
        delete temp;
    }
    void pop_back(){
        if(tail==nullptr){
            cout<<"LL is empty"<<endl;
            return;
        }
        Node* temp=head;
        while(temp->next!=tail){
            temp=temp->next;
        }
        temp->next=nullptr;
        delete tail;
        tail=temp;
    }
    int search(int key){
        Node* temp=head;
        int idx=0;
        while(temp!=nullptr){
            if(temp->data==key){
                return idx;
            }
            idx++;
            temp=temp->next;
        }
        return -1;
    }
    void reverseList(){
        Node* perv=nullptr;
        Node* curr=head;
        Node* next=nullptr;
        while(curr!=nullptr){
            next=curr->next;
            curr->next=perv;
            perv=curr;
            curr=next;
        }
        head=perv;
    }
};
int main(){
    List ll;
    ll.push_front(1);
    ll.push_front(2);
    ll.push_front(3);
    ll.push_back(0);
    ll.printLL();
    ll.pop_front();
    ll.pop_back();
    ll.printLL();
    ll.insert(4,0);
    ll.insert(3,1);
    ll.printLL();
    cout<<ll.search(1)<<endl;
    cout<<ll.search(0)<<endl;
    ll.reverseList();
    ll.printLL();
    return 0;
};

#include <iostream>
using namespace std;
class Node{
    public:
        int data;
        Node* next;
        Node* prev;
        Node(int val){
            data=val;
            next=prev=nullptr;
        }
};
class DoublyList{
    Node* head;
    Node* tail;
    public:
    DoublyList(){
            head=tail=nullptr;
    }
    void printDLL(){
        Node* temp=head;
        while(temp!=nullptr){
            cout<<temp->data<<"<=>";
            temp=temp->next;
        }
        cout<<"null"<<endl;
    }
    void push_front(int val){
        Node* newNode= new Node(val);
        if(head==nullptr){
            head=tail=newNode;
            return;
        }else{
            newNode->next=head;
            head->prev=newNode;
            head=newNode;
        }
    }
    void push_back(int val){
        Node* newNode= new Node(val);
        if(tail==nullptr){
            head=tail=newNode;
            return;
        }else{
            newNode->prev=tail;
            tail->next=newNode;
            tail=newNode;
        }
    }
    void insert(int val, int pos){
        if(pos<0){
            cout<<"invalid pos\n";
            return;
        }
        if(pos==0){
            push_front(val);
            return;
        }
        Node* temp=head;
        for(int i=0;i<pos-1;i++){
            temp=temp->next;
        }
        Node* newNode= new Node(val);
        newNode->next=temp->next;
        newNode->prev=temp;
        temp->next->prev=newNode;
        temp->next=newNode;
    }
    void pop_front(){
        if(head==nullptr){
            cout<<"DLL is empty"<<endl;
            return;
        }
        Node* temp=head;
        head=head->next;
        if(head!=nullptr){
            head->prev=nullptr;
        }
        temp->next=nullptr;
        delete temp;
    }
    void pop_back(){
        if(tail==nullptr){
            cout<<"DLL is empty"<<endl;
            return;
        }
        Node* temp=tail;
        tail=tail->prev;
        if(tail!=nullptr){
            tail->next=nullptr;
        }
        temp->prev=nullptr;
        delete temp;
    }
    int search(int key){
        Node* temp=head;
        int idx=0;
        while(temp!=nullptr){
            if(temp->data==key){
                return idx;
            }
            idx++;
            temp=temp->next;
        }
        return -1;
    }
    void reverseList(){
        Node* current=head;
        while(current!=nullptr){
            Node* temp=current->prev;
            current->prev=current->next;
            current->next=temp;
            current=current->prev;
        }
        Node* temp=head;
        head=tail;
        tail=temp;
    }
};
int main(){
    DoublyList dll;
    dll.push_front(1);
    dll.push_front(2);
    dll.push_front(3);
    dll.push_back(0);
    dll.printDLL();
    dll.pop_front();
    dll.pop_back();
    dll.printDLL();
    dll.insert(4,0);
    dll.insert(3,1);
    dll.printDLL();
    cout<<dll.search(1)<<endl;
    cout<<dll.search(0)<<endl;
    dll.reverseList();
    dll.printDLL();
    return 0;
};

#include <iostream>
using namespace std;
class Node{
    public:
        int data;
        Node* next;
        Node(int val){
            data=val;
            next=nullptr;
        }
};
class CircularList{
    Node* head;
    Node* tail;
    public:
    CircularList(){
            head=tail=nullptr;
    }
    void printCLL(){
        cout<<head->data<<"->";
        Node* temp=head->next;
        while(temp!=head){
            cout<<temp->data<<"->";
            temp=temp->next;
        }
        cout<<"->"<<endl;
    }
    void push_front(int val){
        Node* newNode= new Node(val);
        if(head==nullptr){
            head=tail=newNode;
            tail->next=head;
        }else{
            newNode->next=head;
            head=newNode;
            tail->next=head;
        }
    }
    void push_back(int val){
        Node* newNode= new Node(val);
        if(tail==nullptr){
            head=tail=newNode;
            tail->next=head;
        }else{
            tail->next=newNode;
            tail=newNode;
            tail->next=head;
        }
    }
    void insert(int val, int pos){
        if(pos<0){
            cout<<"invalid pos\n";
            return;
        }
        if(pos==0){
            push_front(val);
            return;
        }
        Node* temp=head;
        for(int i=0;i<pos-1;i++){
            temp=temp->next;
        }
        Node* newNode= new Node(val);
        newNode->next=temp->next;
        temp->next=newNode;
    }
    void pop_front(){
        if(head==nullptr){
            cout<<"LL is empty"<<endl;
            return;
        }else if(head==tail){
            delete head;
            head=tail=nullptr;
            return;
        }
        Node* temp=head;
        head=head->next;
        tail->next=head;
        temp->next=nullptr;
        delete temp;
    }
    void pop_back(){
        if(tail==nullptr){
            cout<<"LL is empty"<<endl;
            return;
        }else if(head==tail){
            delete head;
            head=tail=nullptr;
            return;
        }
        Node* temp=tail;
        Node* prev=head;
        while(prev->next!=tail){
            prev=prev->next;
        }
        tail=prev;
        tail->next=head;
        temp->next=nullptr;
        delete temp;
    }
    int search(int key){
        Node* temp=head;
        int idx=0;
        while(temp!=tail){
            if(temp->data==key){
                return idx;
            }
            idx++;
            temp=temp->next;
        }
        if(temp->data==key){
                return idx;
            }
        return -1;
    }
    void reverseList(){
        Node* perv=nullptr;
        Node* curr=head;
        Node* next=nullptr;
        do {
            next=curr->next;
            curr->next=perv;
            perv=curr;
            curr=next;
        } while(curr!=head);
        head->next=perv;
        head=perv;
    }
};
int main(){
    CircularList cll;
    cll.push_front(1);
    cll.push_front(2);
    cll.push_front(3);
    cll.push_back(0);
    cll.printCLL();
    cll.pop_front();
    cll.pop_back();
    cll.printCLL();
    cll.insert(4,0);
    cll.insert(3,1);
    cll.printCLL();
    cout<<cll.search(1)<<endl;
    cout<<cll.search(0)<<endl;
    cll.reverseList();
    cll.printCLL();
    return 0;
};

#include <iostream>
#include <vector>
#include <list>
#include <stack>
using namespace std;

class Stack_v{
    vector<int> v;
public:
    void push(int val){
        v.push_back(val);
    }
    void pop(){
        v.pop_back();
    }
    int top(){
        return v[v.size()-1];
    }
    bool empty(){
        return v.size()==0;
    }
};
class Stack_ll{
    list<int> ll;
public:
    void push(int val){
        ll.push_front(val);
    }
    void pop(){
        ll.pop_front();
    }
    int top(){
        return ll.front();
    }
    bool empty(){
        return ll.size()==0;
    }
};
int main(){
    stack<int> s;
    Stack_v s2;
    Stack_ll s3;
    s.push(1);
    s.push(2);
    s.push(3);
    while(!s.empty()){
        cout<<s.top()<<" ";
        s.pop();
    }
    cout<<endl;

    s2.push(1);
    s2.push(2);
    s2.push(3);
    while(!s2.empty()){
        cout<<s2.top()<<" ";
        s2.pop();
    }
    cout<<endl;
    s3.push(1);
    s3.push(2);
    s3.push(3);
    while(!s3.empty()){
        cout<<s3.top()<<" ";
        s3.pop();
    }
    cout<<endl;

    return 0;
}

#include <iostream>
#include <queue>
#include <deque>
using namespace std;
class Node{
public:
    int data;
    Node* next;
    Node(int val){
        data=val;
        next=NULL;
    }
};
class Queue{
    Node* head;
    Node* tail;
public:
    Queue(){
        head=tail=NULL;
    }
    void push(int data){
        Node* newNode=new Node(data);
        if(empty()){
            head=tail=newNode;
        }else{
            tail->next=newNode;
            tail=newNode;
        }
    }
    void pop(){
        if(empty()){
            cout<<"LL is EMPTY";
            return;
        }
        Node* temp=head;
        head=head->next;
        delete temp;
    }
    int front(){
        if(empty()){
            cout<<"LL is EMPTY";
            return -1;
        }
        return head->data;
    }
    bool empty(){
        return head==NULL;
    }
};


int main()
{
    queue<int>q;
    Queue q1;
    q.push(1);
    q.push(2);
    q.push(3);
    while(!q.empty()){
        cout<<q.front()<<" ";
        q.pop();
    }
    cout<<endl;
    q1.push(1);
    q1.push(2);
    q1.push(3);
    while(!q1.empty()){
        cout<<q1.front()<<" ";
        q1.pop();
    }
    cout<<endl;
    deque<int>dq;
    dq.push_back(1):
    dq.push_back(2):
    dq.push_back(3):
    dq.push_front(0):
    dq.pop_back():
    cout<<dq.front()<<" "<<dq.back()<<endl;
    return 0;
}

#include <iostream>
using namespace std;
class CircularQueue{
    int* arr;
    int currSize, cap;
    int f,r;
public:
    CircularQueue(int size){
        cap=size;
        arr=new int[cap];
        currSize=0;
        f=0;
        r=-1;
    }
    void push(int data){
        if(currSize==cap){
            cout<<"CQ is FULL\n";
            return;
        }
        r=(r+1)%cap;
        arr[r]=data;
        currSize++;
    }
    void pop(){
        if(empty()){
            cout<<"CQ is EMPTY\n";
            return;
        }
        f=(f+1)%cap;
        currSize--;
    }
    int front(){
        if(empty()){
            cout<<"CQ is EMPTY\n";
            return -1;
        }
        return arr[f];
    }
    bool empty(){
        return currSize==0;
    }
    void printArr(){
        for(int i=0; i<cap; i++){
            cout<<arr[i]<<" ";
        }
        cout<<endl;
    }
};



int main()
{
    CircularQueue cq(3);
    cq.push(1);
    cq.push(2);
    cq.push(3);
    cq.push(4);
    cq.pop();
    cq.push(4);
    cq.printArr();
    while(!cq.empty()){
        cout<<cq.front()<<" ";
        cq.pop();
    }
    cout<<endl;
    return 0;
}

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

class Node{
public:
    int data;
    Node* left;
    Node* right;
    Node(int val){
        data=val;
        left=right=NULL;
    }
};
static int idx=-1;
Node* buildTree(vector<int>preorder){
    idx++;
    if(preorder[idx]==-1){
        return NULL;
    }
    Node* root=new Node(preorder[idx]);
    root->left=buildTree(preorder);
    root->right=buildTree(preorder);
    return root;
}
void preorder(Node* root){
    if(root==NULL){
        return;
    }
    cout<<root->data<<" ";
    preorder(root->left);
    preorder(root->right);
}
void inorder(Node* root){
    if(root==NULL){
        return;
    }
    inorder(root->left);
    cout<<root->data<<" ";
    inorder(root->right);
}
void postorder(Node* root){
    if(root==NULL){
        return;
    }
    postorder(root->left);
    postorder(root->right);
    cout<<root->data<<" ";
}
void levelorder(Node* root){
    queue<Node*>q;
    q.push(root);
    q.push(NULL);
    while(q.size()>0){
        Node* curr=q.front();
        q.pop();
        if(curr==NULL){
            if(!q.empty()){
                cout<<endl;
                q.push(NULL);
                continue;
            }else{break;}
        }
        cout<<curr->data<<" ";
        if(curr->left!=NULL){
            q.push(curr->left);
        }
        if(curr->right!=NULL){
            q.push(curr->right);
        }
    }
    cout<<endl;
}

int main(){
    vector<int>preorderData={1,2,-1,-1,3,4,-1,-1,5,-1,-1};
    idx=-1;
    Node* root=buildTree(preorderData);
    cout<<root->data<<endl;
    cout<<root->left->data<<endl;
    cout<<root->right->data<<endl;
    preorder(root);
    cout<<endl;
    inorder(root);
    cout<<endl;
    postorder(root);
    cout<<endl;
    levelorder(root);
    return 0;
}

#include <iostream>
#include <vector>
using namespace std;
class Node{
public:
    int data;
    Node* left;
    Node* right;
    Node(int val){
        data=val;
        left=right=NULL;
    }
};
Node* insert(Node* root,int val){
    if(root==NULL){
        return new Node(val);
    }
    if(val<root->data){
        root->left=insert(root->left,val);
    }else{
         root->right=insert(root->right,val);
    }
    return root;
}
Node* buildBST(vector<int>arr){
    Node* root=NULL;
    for(int val:arr){
        root=insert(root,val);
    }
    return root;
}
void inorder(Node* root){
    if(root==NULL){
        return;
    }
    inorder(root->left);
    cout<<root->data<<" ";
    inorder(root->right);
}
bool search(Node*root, int key){
    if(root==NULL){
        return false;
    }
    if(root->data==key){
        return true;
    }
    if(root->data>key){
        return search(root->left,key);
    }else{
        return search(root->right,key);
    }
}
Node* getInorderSuccessor(Node* root){
    while(root!=NULL && root->left!=NULL){
        root=root->left;
    }
    return root;
}
Node* delNode(Node* root, int key){
    if(root==NULL){
        return NULL;
    }
    if(root->data>key){
        root->left= delNode(root->left,key);
    }else if(root->data<key){
        root->right= delNode(root->right,key);
    }else{
        if(root->left==NULL){
            Node* temp=root->right;
            delete root;
            return temp;
        }else if(root->right==NULL){
            Node* temp=root->left;
            delete root;
            return temp;
        }else{
            Node* IS=getInorderSuccessor(root->right);
            root->data=IS->data;
            root->right=delNode(root->right,IS->data);
        }
    }
    return root;
}
int main(){
    vector<int>arr={3,2,1,5,6,4};
    Node* root=buildBST(arr);
    cout<<search(root,5)<<endl;
    inorder(root);
    cout<<endl;
    delNode(root,6);
    inorder(root);
    cout<<endl;
    return 0;
}