Java-数构栈与队列

1.栈（Stack）

1.1概念

栈是一种特殊的线性表，其只允许在固定的一段进行插入和删除元素操作。进行数据插入和删除的操作的一段称为栈顶，请一段称为栈底。栈中元素遵循后进先出的原则。

压栈：栈的插入操作叫做进栈/入栈/压栈，输入的数据在栈顶。

出栈：栈的删除操作叫做出栈。

1.2栈的初始化

    public static void main(String[] args) {
        Stack<Integer>s=new Stack<>();
        s.push(1);
        s.push(2);
        s.push(3);
        s.push(4);
    }

1.3栈的模拟实现：

import java.util.Arrays;

public class Mystack {
    private int[] elem;
    private int usedSize;

    private static final int DEFUALT_CAPACITY=10;

    public Mystack(int[] elem) {
        this.elem = new int[DEFUALT_CAPACITY];
    }
    public void push(int val){
        if(isFull()){
            elem= Arrays.copyOf(elem,2*elem.length);
        }
        elem[usedSize]=val;
        usedSize++;
    }
    private boolean isFull(){
        return usedSize==elem.length;
    }
    public int  pop(){
        if(isEmpty()){
            throw new EmptyException("栈内为空");
        }
        int oldVal=elem[usedSize-1];
        usedSize--;
        return oldVal;
    }
    private boolean isEmpty(){
        return usedSize==0;
    }
    public int peek(){
        if (isEmpty()){
            throw new EmptyException("栈内为空");
        }
        return elem[usedSize-1];
    }
}

20. 有效的括号 - 力扣（LeetCode）

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack=new Stack <>();
        for(int i =0;i<s.length();i++){
           char ch=s.charAt(i);//获取每个字符
           if(ch=='('||ch=='['||ch=='{'){
            stack.push(ch);//满足条件的再压入栈
           }else{
            if(stack.empty()){
                return false;//代表第一个元素是右括号无法匹配
            }
            char top=stack.peek();
            if((ch==')'&&top=='(')||(ch==']'&&top=='[')||(ch=='}'&&top=='{')){
                stack.pop();
            }else{return false;}//不匹配的返回
           }
        }
        if(!stack.empty()){
            return false;//最后栈中还有左括号没有被匹配
        }
        return true;
        
    }
}

150. 逆波兰表达式求值

class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack=new Stack<>();
        for(String s:tokens){
            if(isInteger(s)){
            stack.push(Integer.parseInt(s));
            }else{
                int num1=stack.pop();//右边
                int num2=stack.pop();//左边
                switch(s){
                case"+":
                    stack.push(num1+num2);
                    break;
                case"-":
                    stack.push(-num1+num2);
                    break;
                case"*":
                    stack.push(num1*num2);
                    break;
                case"/":
                    stack.push(num2/num1);
                    break;
                    }
            }
        }
        return stack.pop();
    }
    private boolean isInteger(String s){
        if(s.equals("+")||s.equals("-")||s.equals("*")||s.equals("/")){return false;}
        return true;
    }
}

import java.util.Stack;

public class MinStack {
    private Stack<Integer> stack;
    private Stack<Integer> minStack;
    public MinStack() {
        stack=new Stack<>();
        minStack=new Stack<>();
    }

    public void push(int val) {
        stack.push(val);
        if(minStack.empty()){
            minStack.push(val);
        }else {
            if(val<=minStack.peek()){
                minStack.push(val);
            }
        }
    }

    public void pop() {
        if(!stack.empty()){
            int ret=stack.pop();
            if(minStack.peek()==ret){
                minStack.pop();
            }
        }
    }
//获取正常栈顶元素
    public int top() {
        if(stack.empty()){
            return -1;
        }
        return stack.peek();
    }

    public int getMin() {
        if(minStack.empty()){
            return -1;
        }
        return minStack.peek();
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param pushV int整型一维数组
     * @param popV int整型一维数组
     * @return bool布尔型
     */
   public boolean IsPopOrder(int[] pushA,int[] popA){
        Stack<Integer> stack=new Stack<>();
        int j=0;
        for (int i = 0; i < pushA.length; i++) {
            stack.push(pushA[i]);
            while(!stack.empty()&&j< popA.length&&stack.peek()==popA[j]){
                stack.pop();
                j++;
            }
        }
        return stack.empty();
    }
}