Niuke topic -- Realizing queues with two stacks, stacks containing min functions, and valid bracket sequences

---

subject 1—— Queues are implemented with two stacks

Implement a queue with two stacks , Use n Elements to complete n Insert an integer at the end of the queue... Times (push) and n Delete the integer at the head of the queue once (pop) The function of . The elements in the queue are int type , Ensure that the operation is legal , Guarantee pop There are already elements in the queue during operation .

Their thinking

Because the stack is first in and last out , The queue is first in, first out , To realize the queue with stack , You need to put the elements in the stack one by one pop come out , Again push To another stack .
The specific methods are as follows ：

• When an element is inserted , Insert directly into the stack 1 among ;
• When an element pops up , Ruozhan 2 The element of is empty , You need to set the stack 1 All elements of pop-up one by one , Then insert it into the stack 2 among , Back to the stack 2 Top element of ; Ruozhan 2 The element of is not empty , Indicates that the elements in the previous queue form are still on the stack , At this point, you can pop up the top element directly .

Code implementation

import java.util.Stack;
public class Solution {
    
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
    
    public void push(int node) {
    
        stack1.push(node);
    }
    public int pop() {
    
        if(stack1.empty() && stack2.empty()){
    
            throw new RuntimeException("Queue is empty!");
        }
        if(stack2.size()<=0){
    
            while(stack1.size()!=0){
    
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }
}

subject 2—— contain min Function of the stack

Defines the data structure of the stack , Please implement a that can get the smallest element in the stack in this type min function , Input operation is guaranteed pop、top and min Function operation , There must be elements in the stack .

Example
Input ：[“PSH-1”,“PSH2”,“MIN”,“TOP”,“POP”,“PSH1”,“TOP”,“MIN”] （PSH-1 It means that you will -1 Push ,MIN Means to get the smallest element in the stack at this time ）
Output ：-1,2,1,-1

Their thinking

Set an additional auxiliary stack , Used to store every time after stack , The smallest element in the stack ; When it comes out of the stack at the same time , The smallest element at the top of the stack should also pop up accordingly .

Code implementation

import java.util.Stack;
import java.util.ArrayList;
import java.util.List;
public class Solution {
    
    // It can also be used directly Stack
    private List<Integer> stack = new ArrayList<Integer>();
    private List<Integer> min_stack = new ArrayList<Integer>();
    public void push(int node) {
    
        if(stack.isEmpty()) min_stack.add(node);
        else{
    
            // Compare the size of the top node of the stack and the node into the stack , Put the smallest element in the stack at this time into min_stack
            int temp = min_stack.get(min_stack.size()-1);
           if(node <= temp){
    
            min_stack.add(node);
        } else{
    
             min_stack.add(temp);  
           }
        }
        stack.add(node);  
    }
    
    public void pop() {
    
        if(this.stack.isEmpty()){
    
            throw new RuntimeException("Stack is empty!");
        }
        int peek = this.stack.size()-1;
        this.stack.remove(peek);
        // At this time, the smallest element of the corresponding stack should also pop up 
        this.min_stack.remove(peek);
    }
    
    public int top() {
    
        int peek = this.stack.size()-1;
        return this.stack.get(peek);
    }
    
    public int min() {
    
       // Directly return the top element of the smallest element stack 
        return this.min_stack.get(this.min_stack.size()-1);
    }
}

subject 3—— Valid parenthesis sequence

Give an example that contains only characters ’(‘,’)‘,’{‘,’}‘,’[‘ and ’]', String , Determine whether the given string is a legal sequence of parentheses
Parentheses must be closed in the correct order ,"()“ and ”()[]{}“ Are legal sequences of parentheses , but ”(]“ and ”([)]" illegal .

Their thinking

With the help of auxiliary stack , Every time I encounter the left parenthesis , Put characters on the stack , And every time I encounter the right parenthesis , Stack characters , Check whether there are matching parentheses , If it is not , The sequence of parentheses is illegal ; If the match , Then continue to cycle the string , Until it's done ; Finally, check whether the stack is empty , Empty words indicate that the character sequence is legal , Otherwise it's illegal .

Code implementation

import java.util.*;
public class Solution {
    
    public boolean isValid (String s) {
    
        Stack<Character> st = new Stack<Character>();
        for(int i=0;i<s.length();i++){
    
            char c = s.charAt(i);
            switch(c){
    
                case '(':
                case '[':
                case '{': st.push(c);break;
                case ')':
                    if(!st.empty() && st.pop()=='(') break;
                    else return false;
                case ']':
                  if(!st.empty() && st.pop()=='[') break;
                    else return false;  
                case '}':
                    if(!st.empty() && st.pop()=='{') break;
                    else return false;
            }
        }
        if(st.empty()) return true;
        else return false;
    }
}