STL note （ Ten ）： Container adapter —— Queues and stacks

function

#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <stack>
#include <queue>

using namespace std;

//  Sequence type    Relevance    Container adapter   bitset
// vector  set     stack
// deque   map     queue
// list            priority_queue

//  Container adapter ： On the basis of sequential containers, it is encapsulated as a stack 、 Queue or priority queue 

// stack -  First in, then out  -  No iterator 
//  Basic container for encapsulation ：deque（ Default ）、vector、list
//  Basic operation of encapsulation ：empty、size、top、push、pop

void test1()
{
    stack<int> s1; // deque
    vector<int> v(2); // 0 0
    stack<int, vector<int> > s2(v); // vector

    cout << s2.empty() << endl;
    cout << s2.size() << endl;
    cout << s2.top() << endl; // 0
    s2.push(3);
    s2.push(4);
    cout << s2.top() << endl; // 4
    s2.pop();
    cout << s2.top() << endl; // 3

    //  Traverse out of stack 
    while (!s2.empty()) {
        cout << s2.top() << ' ';
        s2.pop();
    }
}

// queue -  fifo  -  No iterator 
//  Basic container for encapsulation ：deque（ Default ）、list
//  Basic operation of encapsulation ：empty、size、front、back、push、pop

void test2()
{
    queue<int> q1;
    list<int> l;
    l.push_back(3);
    l.push_back(4);
    queue<int, list<int> > q2(l);

    cout << q2.empty() << endl; // 0
    cout << q2.size() << endl;  // 2
    cout << q2.front() << endl; // 3
    cout << q2.back() << endl;  // 4
    q2.push(5);
    q2.push(6);
    q2.push(7);
    cout << q2.size() << endl;  // 5
    cout << q2.front() << endl; // 3
    cout << q2.back() << endl;  // 7
    q2.pop();
    q2.pop();
    cout << q2.size() << endl;  // 3
    cout << q2.front() << endl; // 5
    cout << q2.back() << endl;  // 7

    //  Traverse the queue 
    while(!q2.empty()) {
        cout << q2.front() << ' ';
        q2.pop();
    }
}

int main()
{
    //  Container adapter 
    test1(); //  Stack 
    test2(); //  queue 

    return 0;
}

Case study

#include <iostream>
#include <string>
#include <stack>
#include <queue>

using namespace std;

//  Parentheses matching 
class Match
{
private:
    string bracket;
public:
    Match(string s): bracket(s) {}
    void matchBracket()
    {
        stack<char> stk;
        int i = 0, flag = 0; //  matching  · 0 |  Mismatch  · 1
        for (; i < bracket.size(); i++) {
            char c = bracket[i];
            switch(c)
            {
            case '[':
                stk.push(c);
                break;
            case '(':
                stk.push(c);
                break;
            case ')':
                if (!stk.empty() && stk.top() == '(') {
                    stk.pop();
                } else {
                    flag = 1;
                }
                break;
            case ']':
                if (!stk.empty() && stk.top() == '[') {
                    stk.pop();
                } else {
                    flag = 1;
                }
                break;
            }
            if (flag == 1) break;
        }
        if (flag == 0 && stk.empty()) { //  In extreme cases ： Only left bracket or only right bracket 
            cout << " The match is successful ！" << endl;
        } else { //  Only the left parenthesis , Only the right parenthesis , Bracket mismatch 
            cout << " Matching failure ！" << endl;
        }
    }
};

class YHTriangle
{
private:
    int rowNum;
public:
    YHTriangle(int n): rowNum(n) {}
    void printYHTriangle()
    {
        int s, t;
        queue<int> q;
        cout << '1' << endl; //  first line 
        q.push(0);
        q.push(1);
        q.push(1); //  The second line 
        for (int i = 0; i < rowNum - 2; i++) { //  Print the second line and generate the third line 
            q.push(0); // 0 Represents the boundary value of each row （ Beginning of each line ）|  Zero is always one , Used to generate a... At the beginning and end of each line 
            do
            {
                s=q.front();
                q.pop();
                t=q.front();
                q.push(s+t);
                if(t) {
                    cout<<t<<"\t";
                } else {
                    cout<<endl;  //  Line break when reading zero 
                }
            }while(t != 0);
        }
        q.pop(); // 0
        while(!q.empty()){ //  Print the last line 
           cout<<q.front()<<"\t";
           q.pop();
        }
    }
};


int main()
{
    Match r("[()]");
    Match s("[(");
    Match t("[(])");

    r.matchBracket();
    s.matchBracket();
    t.matchBracket();

    YHTriangle tmp(6);

    tmp.printYHTriangle();

    return 0;
}

summary

• Both stack and queue are container adapters , That is, functional packaging based on sequential containers , The container and function of the package depend on the characteristics of the container adapter itself
• According to the characteristics of the container adapter itself , There are certain restrictions on the sequential containers encapsulated at the bottom , for example , For queues , Its bottom layer can only be used deque And list, They can't be used vector, Because the queue is a data structure that can be operated at the head and tail of the queue , and vector The operation of can only be carried out at the end of the container

In the next article , We will introduce C++ Container adapter in —— Priority queue

Postscript

Recommend a free open course of zero sound College , Personally, I think the teacher spoke well , Share with you ：[Linux,Nginx,ZeroMQ,MySQL,Redis,fastdfs,MongoDB,ZK, Streaming media ,CDN,P2P,K8S,Docker,TCP/IP, coroutines ,DPDK Etc , Click learn now :

This article is mainly used as a summary of the course learning process , If you have any questions, you can also leave a message in the comment area , I will try my best to help you solve the problem , If it's helpful to you , I hope you like it more 、 forward , thank you ！