2019-07-11—栈

栈：Java数据结构和算法（四）——栈

string和char一般这么转化：

    String str = "12<a[b{c}]>";
    char[] cha = str.toCharArray();
    for(char c : cha){}
    char ch = stack.pop().toString().toCharArray()[0];

21、定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。

import java.util.Stack;

public class Solution {
    
    Stack<Integer> stack1 = new Stack<>();
    Stack<Integer> stack2 = new Stack<>();
    
    public void push(int node) {
        stack1.push(node);
        if(stack2.isEmpty()){
            stack2.push(node);
        }else{
            if(stack2.peek() > node){
                stack2.push(node);
            }
        }
    }
    
    public void pop() {
        int i = stack1.pop();
        if(i == stack2.peek()){
            stack2.pop();
        }
    }
    
    public int top() {
        return stack1.peek();
    }
    
    public int min() {
        return stack2.peek();
    }
}

思路：用两个栈，第二个栈存min。栈的函数：

Stack<Integr> stack1 = new Stack<>();
stack1.pop();
stack1.push();
stack1.isEmpty();
stack1.peek();

22.输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4，5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
做法一：（不用stack。。用数组）

import java.util.ArrayList;

public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        int len = pushA.length;
        int index = -1;
        int num1 = popA[0];
        if(len == 1){
            if(pushA[0] == popA[0]){
                return true;
            }else{
                return false;
            }
        }
        for(int i : pushA){
            index ++;
            if(i == num1){
                break;
            }
        }
        for(int j=1; j<len; j++){
            for(int k=index-1; k>=0; k--){
                if(popA[j] == pushA[k]){
                    while(j < len && k >= 0){
                        if(j == len-1 && k == 0){
                            return true;
                        }else if(k == 0 || j >= len-1){
                            return false;
                        }else{
                            j++;
                            k--;
                            while(j<len){
                                if(popA[j] != pushA[k]){
                                    j++;
                                }else{
                                    break;
                                }
                             }
                        }
                    }
                }
            }
        }
        return false;
    }
}

做法二：（用栈）

import java.util.ArrayList;
import java.util.Stack;

public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        int len = pushA.length;
        if(len == 1){
            if(pushA[0]==popA[0]){
                return true;
            }else{
                return false;
            }
        }
        Stack<Integer> stack = new Stack<>();
        int index = 0;
        for(int i : pushA){
            stack.push(i);
            while(!stack.isEmpty() && stack.peek() == popA[index]){
                stack.pop();
                index++;
            }
        }
        return stack.isEmpty();
    }
}