Bo2SS

"Containers" Why are there quotes? Please read on.

Course Content#

template name; // Custom types are also allowed, such as struct

Queue and Stack#

queue#

• 

• queue que;

• name.method()

  • que.push(5); // Enqueue
  • que.pop(); // Dequeue
  • que.front(); // Front element
  • que.size(); // Number of elements
  • que.empty(); // Is it empty?

stack#

• stack sta;
• name.method()
  • sta.push(5);
  • sta.pop();
  • sta.top(); // Top element, the only difference from queue
  • sta.size();
  • sta.empty();

Essence#

• Their underlying implementation is based on deque
  • double-ended queue
  • Reference deque-cppreference
• They are wrappers around deque, essentially adapters
  • deque is the real container

Vector and Priority Queue#

vector#

【Note: In C language, variable-length arrays cannot be defined, ❌ cannot define like this: int n; scanf("%d", &n); int num[n];】

• vector v;
• name.method()
  • v.push_back(5); // Add an element at the end O(1)
  • v.size(); // Number of elements
  • v.insert(1, 6); // Insert element O(N), using push_back is more efficient
• vector<vector > v2; // Dynamic 2D array
  • Before C++11 standard, there must be a space between ">" and ">", otherwise it may be misinterpreted as right shift operation
  • 
• Initialization, refer to Various Initialization and Assignment Methods of vector-CSDN
• cin to vector requires first initializing the vector with the size of space

priority_queue#

• priority_queue que;
  • int can be followed by objects to sort
  • Reference C++ priority_queue (STL priority_queue) Usage Detailed Explanation-C Language Chinese Network
• name.method()
  • que.push(5);
  • que.pop();
  • que.top(); // Top element, by default largest number is on top
  • que.size();
  • que.empty();
• Custom structure priority queue needs to overload the less than operator
  • bool operator <(const struct name &variable) {}
  • Note: Overloading the less than operator, for this container, if implemented as
    • a) <, then sorted from largest to smallest, corresponding to max heap
    • b) >, then sorted from smallest to largest, corresponding to min heap
    • A bit convoluted, see code demonstration for details-priority_queue
  • Note: All containers that need sorting are overloaded with the less than operator

Essence#

• The underlying implementation of vector is based on arrays
• The underlying implementation of priority_queue is based on heaps

String string#

Class

• string str;
• name.method()
  • str.size() // Equivalent to str.length()
  • str.find(s2, pos = 0); // Find s2 in str, starting from the beginning (pos = 0) by default, returns index if found
    • The underlying method implementation depends on the compiler
    • Check if found (no position)

if (str.find(s2) != string::npos) {
  // static const size_t npos = -1;
  // Found
} else {
  // Not found
}

• • str.insert(x, s2); // Insert s2 at index x
  • str.substr(2); // Substring from index 2 to the end
  • str.substr(2, len); // Note the second parameter is length
  • str.replace(index, len, s2); // Also note the second parameter is length
• Overloaded many operators
  • +
    • string a = string("123") + string("a");
    • += Use with caution
      • a += string("123") + string("456"); // "+=" has a priority just higher than ","
      • ❓ Imagine how many temporary variables are defined, how many times values are copied
  • ==, >=, <=, >, <
    • Judged by dictionary order
  • =
    • str = "123a"
    • Can be directly assigned, unlike C language which requires using strcpy

Key-Value Pair map#

Mapping

• map<string, int> m; // "123" → 456
• Methods
  • []
    • Assignment, access
    • If the accessed key does not exist, it will automatically create one, assigning the default value of the type
    • There is an implicit overhead because the underlying is a red-black tree, search efficiency is O(logN)
  • insert, find, erase
  • count
    • Returns how many of a certain key
    • But there are no duplicates in map, so it only returns 0 or 1
    • Can be used to check if a key exists
• The underlying implementation is a red-black tree【RBTree】
  • Ordered structure, map defaults to ascending order
  • If the key corresponds to a custom structure, the < operator needs to be overloaded
• Extensions
  • multimap
    • Can have multiple duplicate keys
  • unordered_map ❗introduced in C++11
    • Unordered
    • The underlying implementation is a hash table, both search and insert efficiency are O(1)
    • Custom structures need to manually implement hash functions
      • Reference C++ STL Unordered Container Custom Hash Function and Comparison Rules-C Language Chinese Network

Set set#

• Can be used for deduplication and sorting
• The underlying implementation is the same as map, red-black tree, and may also need to overload "<" when necessary
• Extensions
  • multiset
  • unordered_set ❗C++11

Pair pair#

• Pair
• pair<int, int>
  • pair.first First element
  • pair.second Second element
• make_pair can quickly create a temporary pair

Code Demonstration#

queue#

• 

• Two types of data queues

• que.empty() and que.size() are both O(1), with an underlying data field storing

• Default generated constructor

Output

stack#

• 

• Difference from queue: name, header file, top() method

Output

vector#

• 

• More advanced than arrays, commonly used in leetcode

• 3 types of insertion methods

Output

priority_queue#

• 

• Remember to overload the less than operator for custom structure queues

• ❗The overloaded operator is less than, but it outputs from largest to smallest!

Output

• 

• In the second part, it implements sorting from largest to smallest, but the overloaded operator is less than, and it also implements the less than operator

map#

• 

• For custom structures, map needs to overload <, unordered_map needs to define a hash function

• For non-existent keys, accessing them will automatically create them and assign the default value of the type

Output

Exercise Questions#

HZOJ-383: Weekend Dance Party#

Sample Input

3 5 6

Sample Output

1 1
2 2
3 3
1 4
2 5
3 1

• Idea
  • Queue
  • Dequeue, enqueue to the back
• Code
  • 
  • Basic operations of the queue

HZOJ-378: String Parenthesis Matching 2#

Sample Input

a(cc[])bbb()@

Sample Output

YES

• Idea
  • Character stack
  • Match: YES, such as ( [ ] )
  • Not matched: NO
    • Parentheses are mismatched, such as ( [ ) ]
    • Encountering a right parenthesis when the stack is empty, such as ( ) )
    • The string ends, but the stack is still not empty, such as ( ( { } )
  • Note: Cannot use three variables to simply record the count, because parentheses have order issues, such as ([)]
• Code
  • 
  • Note the three mismatched situations
  • When matched, pop the left parenthesis from the stack

HZOJ-376: Machine Translation#

Sample Input

3 7
1 2 1 5 4 4 1

Sample Output

5

• Idea
  • Queue
  • Use mark array to record words
    • mark[x] = 1, 0
    • Data is not large (article length does not exceed 1000), no need to use map, set, etc.
• Code
  • 
  • The key is the queue that stores words and the array that marks words
  • Note the case when memory is full

HZOJ-379: Warehouse Log#

Sample Input

13 0 1 0 2 2 0 4 0 2 2 1 2 1 1 2 1 2

Sample Output

2
4
4
1
0

• Idea
  • 0, 1, 2: Inbound, Outbound, Query
  • Last in first out: Needs a goods stack
  • Query function (output maximum): Also needs a stack to record the maximum value [Key]
  • Note: Each piece of goods is different, so the problem is simplified
• Code
  • 
  • There are two stacks!
    • For this problem, the goods stack can be omitted, just to aid understanding
    • Because this problem does not need to care about what the goods are when they are popped, and the max stack records the maximum value each time it is stored, it will be recorded repeatedly!

HZOJ-382: Counting#

Sample Input

7 3

Sample Output

4

• Idea
  • Josephus problem
  • 【Essence】 Queue: Safe people throw to the back, unsafe people are eliminated
  • Termination condition: When the size of the queue is 1
• Code
  • 
  • The push i is the number
  • Does pop have no return value?
    • Here, in the containers mentioned, pop and push have no return value
    • See pop-cppreference

HZOJ-384: Counting to Seven#

Sample Input

4 3 6

Sample Output

3

• Idea
  • Similar to the previous question, pay attention to details
  • The difference is
    • Input: The x-th person starts counting from t
    • Judgment condition: Contains 7 or multiples of 7
    • Counting does not reset, continues to +1
• Code

HZOJ-385: Harbor#

Sample Input

4
1 4 1 2 2 3
3 2 2 3
86401 2 3 4
86402 1 5

Sample Output

3
3
3
4

• Idea
  • Input: Arrival time, number of people, nationality of each person
  • Queue +【mark array/map】+ variable for the number of countries
    • The queue can store either ships or people
      • Because the people in the ship are not fixed, storing people is more convenient
    • First reduce the number of people based on time, then add people
    • Country count: If a new one arrives, +1; if the last one leaves, -1
• Code
  • 
  • The key is the queue used, the mark array, and the variable counting the number of countries
  • Is it a bit like a sliding window? A bit, but generally the sliding window has fixed data
  • Directly copy data input, output format seems a bit strange? It should be a newline issue
  • Line 33 quickly defines the structure: (struct name){..., ...}
    • Not adding parentheses () is also fine, but adding parentheses may be clearer

HZOJ-569: Solution Simulator#

Sample Input

100 100
2
P 100 0
Z

Sample Output

200 50.00000
100 100.00000

• Idea
  • Undo operation: Use stack! Store the quality and concentration after each operation [or] the quality of salt and total quality
  • Review of chemistry knowledge
    • Solution composition: Salt + Water
    • Concentration: Salt / (Salt + Water)
    • Quality: Salt + Water
• Code
  • 
  • Storing the quality of salt and total quality is helpful for understanding calculations
    • Both stored as double type, pay attention to conversion during output
  • Undo operation: first reduce then pop

LC-232: Implement Queue Using Stacks#

• Idea
  • Two stacks to implement a queue
  • Have this process in mind👇
  • 
• Code

class MyQueue {
public:
    // Declare stacks here, otherwise they are not easy to call
    stack<int> s1, s2;
    /** Initialize your data structure here. */
    MyQueue() {
        // No need to care
    }
    
    /** Push element x to the back of queue. */
    void push(int x) {
        s1.push(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        // First transfer all elements from s1 stack to s2 stack
        while (!s1.empty()) {
            // Push first then pop, order cannot be reversed
            s2.push(s1.top());
            s1.pop();
        }
        int t = s2.top();  // At this point, get the value to pop
        s2.pop();          // Pop from stack
        // Transfer back
        while (!s2.empty()) {
            s1.push(s2.top());
            s2.pop();
        }
        return t;
    }
    
    /** Get the front element. */
    int peek() {
        // Transfer to s2
        while (!s1.empty()) {
            s2.push(s1.top());
            s1.pop();
        }
        int t = s2.top();  // Temporary variable t stores the value, must transfer back before returning
        // Transfer back
        while (!s2.empty()) {
            s1.push(s2.top());
            s2.pop();
        }
        return t;
    }
    
    /** Returns whether the queue is empty. */
    bool empty() {
        return s1.empty();  // Just check s1
    }
};

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue* obj = new MyQueue();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->peek();
 * bool param_4 = obj->empty();
 */

• • After each operation, the value is always stored in s1
  • The position of stack declaration: It should be placed globally in the class to be accessed by other functions
    • Can it be used with this if placed in the initialization function MyQueue()?
    • ❌ No, this refers to the entire class, pay attention when learning classes later
  • 【Advanced】 Can you implement a queue with an amortized time complexity of O(1) for each operation? In other words, the total time complexity for executing n operations is O(n), even if one of the operations may take longer.
    • Key: When pop transfers elements from s1 to s2, do not transfer back
    • This way, the order of s2 is the order of the queue's dequeue
    • Each pop only transfers elements from s1 to s2 when s2 is empty; otherwise, just pop from s2
    • Reference Implement Queue Using Stacks - Official Solution-Method Two

LC-225: Implement Stack Using Queues#

• Idea
  • Actually, only one queue is needed
    • When transferring elements, just place them at the back
      • ① Can adjust the order during push
      • ② Can also operate during pop
    • Control the transfer boundary using queue.size()
• Code

class MyStack {
public:
    queue<int> que;
    /** Initialize your data structure here. */
    MyStack() {
    }
    
    /** Push element x onto stack. */
    void push(int x) {
        que.push(x);
        // Move all previous elements to the back
        for (int i = 1; i < que.size(); i++) {
            que.push(que.front());
            que.pop();
        }
    }
    
    /** Removes the element on top of the stack and returns that element. */
    int pop() {
        int t = que.front();
        que.pop();
        return t;
    }
    
    /** Get the top element. */
    int top() {
        return que.front();
    }
    
    /** Returns whether the stack is empty. */
    bool empty() {
        return que.empty();
    }
};
/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack* obj = new MyStack();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->top();
 * bool param_4 = obj->empty();
 */

• • After pushing complex operations, other operations can be used like a stack

Additional Knowledge Points#

• Quickly define a structure: (struct name){..., ...}

Points to Consider#

Tips#

Course Summary#