데이터 구조 구현 시리즈

하나, 두 개의 창고 가 하나의 대열 을 실현 하 다

class CQueue {
public:
    CQueue() {
    }
    stack s1, s2;
    
    void appendTail(int value) {
        s1.push(value);
    }
    
    int deleteHead() {
        if(!s2.empty()) {
            int tmp = s2.top();
            s2.pop();
            return tmp;
        }
        if(s1.empty()) return -1;
        while(!s1.empty()) {
            s2.push(s1.top());
            s1.pop();
        }
        int tmp = s2.top();
        s2.pop();
        return tmp;
    }
};

2. LC 225. 대기 열 로 스 택 실현

class MyStack {
private:
    queue q;
public:
    /** Initialize your data structure here. */
    MyStack() {}
    
    /** Push element x onto stack. */
    void push(int x) {
        q.push(x);
    }
    
    /** Removes the element on top of the stack and returns that element. */
    int pop() {
        int ans = q.back();
        queue tmp;
        for(int i = q.size()-1; i > 0; i--) {
            tmp.push(q.front());
            q.pop();
        }
        q = tmp;
        return ans;
    }
    
    /** Get the top element. */
    int top() {
        return q.back();
    }
    
    /** Returns whether the stack is empty. */
    bool empty() {
        return q.empty();
    }
};

3. LC 146. LRU 캐 시 메커니즘

class LRUCache {
private:
    int capacity_; //  
    list> l; //    list
    unordered_map>::iterator> m; //key->  (key, val)  list    
public:
    LRUCache(int capacity) {
        capacity_ = capacity;
    }
    
    int get(int key) {
        auto it = m.find(key);
        if(it == m.end()) return -1;

        auto lit = it->second; //     ,       
        l.splice(l.begin(), l, lit);  // l  lit          ，    l.begin()  
        return lit->second;
    }
    
    void put(int key, int value) {
        auto it = m.find(key);
        if(it != m.end()) {  //      key,     key val,          
            it->second->second = value;
            l.splice(l.begin(), l, it->second);
            return;
        }

        //    key      
        if(l.size() == capacity_) {
            auto& node = l.back(); //        ,          
            m.erase(node.first); //     key   map    key-value 
            l.pop_back(); //list l         ,      map  key   !!!
        }

        l.push_front({key, value});
        m[key] = l.begin();
    }
};

4. 면접 문제 30. min 함 수 를 포함 하 는 스 택

class MinStack {
public:
    /** initialize your data structure here. */
    MinStack() {
        //A = new stack();
        //B = new stack();
    }
    
    void push(int x) {
        A.push(x);
        if(B.empty() || x <= B.top()) {
            B.push(x);
        }
    }
    
    void pop() {
        if(!A.empty()) {
            //int top = A.top();
            if(A.top() == B.top()) { // ==     = ...
                B.pop();
            }
            A.pop();
        }
    }
    
    int top() {
        return A.top();
    }
    
    int min() {
        return B.top();
    }
private:
    stack A;
    stack B;
};