有效的括号

https://leetcode.cn/problems/valid-parentheses/

class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        //遍历字符串,碰到左括号：进栈   碰到右括号：出栈顶元素判断是否和该右括号匹配
        for(auto& ch:s)
        {
            if(ch == '(' || ch == '[' || ch == '{') 
            {
                st.push(ch);
            }
            else 
            {
                //如果栈为空,说明括号是不匹配的
                if(st.empty()) return false;
                //出栈顶元素和当前右括号匹配
                char top = st.top();
                st.pop();
                if( ch ==')' && top != '('  || ch == ']' && top != '[' ||ch == '}' && top != '{')
                    return false; 
            }
        }
        return st.empty(); //如果最后栈为空,说明括号是匹配的
    }
};

用队列实现栈

https://leetcode-cn.com/problems/implement-stack-using-queues/

两个队列实现栈

class MyStack {
public:
    MyStack() {

    }
    
    void push(int x) {
        NonEmptyQueue.push(x);//往不为空的队列插入数据
    }
    
    int pop() {
        //将不空队列的数据放到空队列当中,直到不空队列只有一个元素
        while(NonEmptyQueue.size() > 1)
        {
            EmptyQueue.push(NonEmptyQueue.front());
            NonEmptyQueue.pop();
        }
        int front = NonEmptyQueue.front();
        NonEmptyQueue.pop();
        NonEmptyQueue.swap(EmptyQueue);//交换两个队列,保证EmptyQueue为空队列
        return front;
    }
    
    int top() {
        return NonEmptyQueue.back();
    }
    
    bool empty() {
        return EmptyQueue.empty() && NonEmptyQueue.empty();
    }
private:
    queue<int> NonEmptyQueue;//不为空的队列
    queue<int> EmptyQueue;//空队列
};

一个队列实现栈

class MyStack {
public:
    MyStack() {

    }
    
    void push(int x) {
        q.push(x);
    }
    
    int pop() {
        int size = q.size();
        //将前size-1个元素重新插入到队列当中
        for(int i = 0;i<size-1;i++)
        {
            int front = q.front();
            q.pop();
            q.push(front);
        }
        //此时队头元素就相当于是栈顶元素
        int front = q.front();
        q.pop();
        return front;
    }
    
    int top() {
        return q.back();
    }
    
    bool empty() {
        return q.empty();
    }
private:
    queue<int> q;
};

用栈实现队列

https://leetcode-cn.com/problems/implement-queue-using-stacks/

class MyQueue {
public:
    MyQueue() {

    }
    
    void push(int x) {
        pushStack.push(x);
    }
    void Check() //检查是否要将push栈的内容导入到pop栈
    {
        if(popStack.empty())
        {
            while(!pushStack.empty())
            {
                popStack.push(pushStack.top());
                pushStack.pop();
            }
        }
    }
    int pop() {
        Check();
        int top = popStack.top();
        popStack.pop();
        return top;
    }
    
    int peek() {
        Check();
        return popStack.top();
    }
    
    bool empty() {
        return pushStack.empty() && popStack.empty();
    }
private:
    stack<int> pushStack;//存放数据的栈
    stack<int> popStack;//用于弹出数据的栈
};

设计循环队列

https://leetcode-cn.com/problems/design-circular-queue/

方式1：使用数组实现

class MyCircularQueue {
public:
    MyCircularQueue(int k) {
        arr.resize(k+1);//开辟k+1个空间
        front = tail = 0;
        size = k;
    }
    
    bool enQueue(int value) {  //向循环队列插入一个元素。如果成功插入则返回真
        if(isFull()) return false;
        arr[tail] = value;
        tail ++;
        tail %= size+1; //tail = tail % (size+1)
        return true;
    }
    
    bool deQueue() { //从循环队列中删除一个元素。如果成功删除则返回真。
        if(isEmpty()) return false;
        front++;
        front %= size+1;
        return true;
    }
    
    int Front() {
        if(isEmpty()) return -1;
        return arr[front];
    }
    
    int Rear() {
        if(isEmpty()) return -1;
        //由于插入元素之后,tail往后走,所以tail的前一个元素才是队尾元素
        if(tail == 0) return arr[size];
        else return arr[tail-1];
    }
    
    bool isEmpty() {
        return front == tail;
    }
    
    bool isFull() {
        return (tail + 1) % (size+1) == front;
    }
private:
    vector<int> arr;
    int front;//标志队头
    int tail;//标志队尾
    int size;//实际存储的元素个数
};

方法2：链表实现

class MyCircularQueue {
public:
    MyCircularQueue(int k) {
        //构建k+1个节点的循环链表
        tail = head = new ListNode;
        for(int i = 0;i<k;i++) 
        {
            ListNode* newnode = new ListNode;
            tail->next = newnode;
            tail = tail->next;
        }
        //tail指向尾节点,让首尾相连
        tail->next = head;

        //注意:要让tail回到起始位置！！！！！因为一开始链表没有有效元素
        head = tail;
    }
    
    bool enQueue(int value) { //向循环队列插入一个元素。如果成功插入则返回真。
        if(isFull()) return false;
        tail->val = value;
        tail = tail->next;
        return true;
    }
    
    bool deQueue() {
        if(isEmpty()) return false;
        head = head->next;
        return true;
    }
    
    int Front() {
        if(isEmpty()) return -1;
        return head->val;
    }
    
    int Rear() {
        if(isEmpty()) return -1;
        //从head位置遍历查找,tail的前一个节点放的就算队尾元素
        ListNode* cur = head;
        while(cur->next != tail)
            cur = cur->next;
        return cur->val;
    }
    
    bool isEmpty() {
        return head == tail;
    }
    
    bool isFull() {
        return tail->next == head;
    }
private:
    ListNode* head;
    ListNode* tail;
};s

最小栈

https://leetcode.cn/problems/min-stack/

class MinStack {
public:
    MinStack() {

    }
    
    void push(int val) {
        dataStack.push(val);
        //判断要往辅助栈放重复元素还是更小的元素
        if( minStack.empty() || minStack.top() >= val)
            minStack.push(val);
        else 
            minStack.push(minStack.top());//重复压入当前最小栈栈顶元素
    }
    
    void pop() {
        int top = dataStack.top();
        dataStack.pop();
        minStack.pop(); //坑点！！此时minStack也要同步pop数据
    }
    
    int top() {
        return dataStack.top();
    }
    
    int getMin() {
        return minStack.top();
    }
private:
    stack<int> minStack;//辅助栈->存放当前栈中对应的最小值
    stack<int> dataStack;
};

优化：

class MinStack {
public:
    MinStack() {

    }
    
    void push(int val) {
        dataStack.push(val);
        if( minStack.empty() || minStack.top() >= val)
            minStack.push(val);
    }
    
    void pop() {
        int top = dataStack.top();
        dataStack.pop();
        if(top == minStack.top())
            minStack.pop(); 
    }
    
    int top() {
        return dataStack.top();
    }
    
    int getMin() {
        return minStack.top();
    }
private:
    stack<int> minStack;//辅助栈->存放当前栈中对应的最小值
    stack<int> dataStack;
};

栈的压入&弹出序列

https://www.nowcoder.com/practice/d77d11405cc7470d82554cb392585106?tpId=13&&tqId=11174&rp=1&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking