数据结构-栈和队列

栈的概念

栈的使用

编辑模拟实现栈

中缀表达式转后缀表达式

括号匹配

出栈入栈次序匹配

队列概念

队列的使用

栈的概念

栈是一种特殊的线性表,其只允许在固定的一端进行插入和删除元素的操作.进行数据插入和删除操作的一端称为栈顶,;另一端称为栈底.栈中的数据元素遵守先进后出的原则.

压栈:栈的插入操作叫做压栈/进栈/入栈,入数据在栈顶.

出栈:栈的删除操作叫做出栈.出数据在栈顶.

栈的底层是一个动态的数组.因此其中的元素在物理和逻辑上都是连续的.

栈的使用

模拟实现栈

import java.util.Arrays;

public class MyStack {
    public int[] elem;
    public int usedSize;
    public static final int DEFAULT_SIZE = 10;

    public MyStack(){
        this.elem = new int[DEFAULT_SIZE];
    }

    /**
     * 压栈
     */
    public int push(int val){
        if (isFull()){
            elem = Arrays.copyOf(elem,2*elem.length);
        }
        this.elem[usedSize] = val;
        usedSize++;
        return val;
    }

    public boolean isFull(){
        return usedSize == elem.length;
    }

    //出栈
    public int pop(){
        if (empty()){
            throw new MyEmptyStackException("栈为空!");
        }
        int ret = elem[usedSize-1];
        usedSize--;
        return ret;
    }

    public boolean empty(){
        return usedSize == 0;
    }

    public int peek(){
        if (empty()){
            throw new MyEmptyStackException("栈为空!");
        }
        return elem[usedSize-1];
    }
}

中缀表达式转后缀表达式

后缀表达式又叫做逆波兰式.

快捷的转换方式:

写代码:将后缀表达式123*+45*6+7*+进行计算,求结果.

这类问题就是利用栈.

思路就是遍历这个表达式,遇到数字就入栈,遇到运算符出栈顶两个元素,第一个元素作为右操作数,第二个元素作为左操作数.

class Solution {

    public int evalRPN(String[] tokens) {

        Stack<Integer> stack = new Stack<>();

        //遍历字符串数组,不是运算符就入栈

        for(String s:tokens){

            if(!isOperations(s)){

                stack.push(Integer.parseInt(s));

            }else{

                //是运算符就出栈顶两个元素

                //第一个元素作为右操作数

                int num2 =stack.pop();

                //第二个元素作为左操作数

                int num1 = 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(num1/num2);

                    break;

                }

            }

        }

        //最后栈里剩的元素就是结果

        return stack.pop();

    }

    //判断是不是运算符

    public boolean isOperations(String s){

        if(s.equals("+")||s.equals("-")||s.equals("*")||s.equals("/")){

            return true;

        }

        return false;

    }

}

括号匹配

思路:遍历字符串,是左括号就压栈,右括号就出栈,看是否匹配.如果字符串遍历完成,此时栈也是空的,就是匹配的.

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 ch2 = stack.peek();

                if(ch2=='['&&ch==']' ||ch2=='{'&&ch=='}' ||ch2=='('&&ch==')'){

                    stack.pop();

                }else{

                    return false;

                }

            }

        }

        if(!stack.empty()){

            return false;

        }

        return true;

    }

}

出栈入栈次序匹配

思路: 用i下标遍历PushV数组,直接入栈;

入栈之后判断j下标元素是不是当前入栈的元素,如果是则出栈,j++,并且弹出栈顶元素,弹出之后判断栈顶元素是不是和j下标元素一样,一样则继续弹出,不一样则i++.

如果不是就继续i++.

循环遍历完之后,栈里还有元素就说明是不匹配的.

public class Solution {

/**

* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可

*

*

* @param pushV int整型一维数组

* @param popV int整型一维数组

* @return bool布尔型

*/

public boolean IsPopOrder (int[] pushV, int[] popV) {

Stack<Integer> stack = new Stack<>();

int j = 0;//遍历popV数组

for(int i=0;i<pushV.length;i++){

stack.push(pushV[i]);

while(!stack.empty()&&stack.peek()==popV[j]){

stack.pop();

j++;

}

}

return stack.empty();

}

}