Sword finger offer 𞓜: stack and queue (simple)

List of articles

1. 【 Stack and queue 】

---

---

Preface

This column records leetcode Record of writing questions , With a sword finger Offer The first 2 Version based

---

1. Simulate the queue with two stacks

Original link ： The finger of the sword Offer 09. Queues are implemented with two stacks

subject ：
Use two stacks to implement a queue . The declaration of the queue is as follows , Please implement its two functions appendTail and deleteHead , The functions of inserting integers at the end of the queue and deleting integers at the head of the queue are respectively completed .( If there are no elements in the queue ,deleteHead Operation return -1 )

Example ：

Input ：
[“CQueue”,“appendTail”,“deleteHead”,“deleteHead”]
[[],[3],[],[]]
Output ：[null,null,3,-1]

1 <= values <= 10000
 At most  appendTail、deleteHead  Conduct  10000  Secondary call 

Code

class CQueue {
    
private:
    stack<int> s1;
    stack<int> s2;
    
    void push_In_S2() {
    
        while (!s1.empty()) {
    
            s2.push(s1.top());
            s1.pop();
        }
    }

public:
    CQueue() {
    }
    //  Queue in operation , Push s1
    void appendTail(int value) {
    
        s1.push(value);
    }
    
    //  The stack, 
    int deleteHead() {
    
        if (s2.empty()) {
    
            if (s1.empty()) {
    
                return -1;
            }
            push_In_S2(); //  This function is responsible for s1 Element of is pushed to s2
        }

        int value = s2.top();
        s2.pop();
        return value;
    }
};

/** * Your CQueue object will be instantiated and called as such: * CQueue* obj = new CQueue(); * obj->appendTail(value); * int param_2 = obj->deleteHead(); */

2. contain min Function of the stack

subject ：
Defines the data structure of the stack , Please implement a in this type that can get the minimum elements of the stack min The function is in the stack , call min、push And pop The time complexity of O(1).

Original link ： contain min Function of the stack

Code ：

With the help of auxiliary stack , Record the minimum value every time you stack , Keep the minimum at the top of the auxiliary stack .

class MinStack {
    
private:
    stack<int> stk;
    stack<int> min_stk;
public:
    /** initialize your data structure here. */
    MinStack() {
    
        min_stk.push(INT_MAX);
    }
    
    void push(int x) {
    
        stk.push(x);
        min_stk.push(std::min(min_stk.top(), x));
    }
    
    void pop() {
    
        stk.pop();
        min_stk.pop();
    }
    
    int top() {
    
        return stk.top();
    }
    
    int min() {
    
        return min_stk.top();
    }
};