数据结构与算法-栈

共计7622字,阅读大约26分钟。

栈的介绍

栈是限制插入和删除只能在一个位置上进行的线性表。其中,允许插入和删除的一端位于表的末端,叫做栈顶(top),不允许插入和删除的另一端叫做栈底(bottom)。对栈的基本操作有 PUSH(压栈)和 POP (出栈),前者相当于表的插入操作(向栈顶插入一个元素),后者则是删除操作(删除一个栈顶元素)。栈是一种后进先出(LIFO)的数据结构,最先被删除的是最近压栈的元素。

图片[1] | Web Stack | 数据结构与算法-栈 | 一个栈
压栈:
图片[2] | Web Stack | 数据结构与算法-栈 | 一个栈

弹栈:

图片[3] | Web Stack | 数据结构与算法-栈 | 一个栈
栈实现
由于栈是一个表,因此任何实现表的方法都可以用来实现栈。主要有两种方式,链表实现和数组实现。

链表实现栈

可以使用单链表来实现栈。通过在表顶端插入一个元素来实现 PUSH,通过删除表顶端元素来实现 POP。使用链表方式实现的栈又叫动态栈。动态栈有链表的部分特性,即元素与元素之间在物理存储上可以不连续,但是功能有些受限制,动态栈只能在栈顶处进行插入和删除操作,不能在栈尾或栈中间进行插入和删除操作

数组实现栈

栈也可以用数组来实现。使用数组方式实现的栈叫静态栈

栈的应用场景

图片[4] | Web Stack | 数据结构与算法-栈 | 一个栈
栈的快速入门

习题1:使用数组来模拟栈的使用

图片[5] | Web Stack | 数据结构与算法-栈 | 一个栈
public class ArrayStack {
    /**
        栈的大小
     */
    private int maxStack;

    /**
        数组用来模拟栈
     */
    private int[] stack;

    /**
     * 表示栈顶,默认值为-1
     */
    private int top = -1;

    /**
     *
     * @param maxStack 初始化栈的大小
     */
    public ArrayStack(int maxStack){
        this.maxStack = maxStack;
        this.stack = new int[this.maxStack];
    }

    /**
     *  判断是否已经栈满
     * @return
     */
    public boolean isFull(){
        return this.top==maxStack-1;
    }

    /**
     * 是否空栈
     */
    public boolean isEmpty(){
        return this.top==-1;
    }

    /**
     * 入栈
     */
    public void push(int value){
        if (isFull()){
            throw new RuntimeException("栈已满...");
        }

        top++;
        stack[top] = value;
    }

    /**
     *出栈
     */
    public int pop(){
        if (isEmpty()){
            throw new RuntimeException("空栈,没有数据");
        }
        int value = stack[top];
        top--;
        return value;
    }

    /**
     * 查看栈中数据
     */
    public void list(){
        if (isEmpty()){
            throw new RuntimeException("空栈,没有数据");
        }
        for (int i=0;i<stack.length;i++){
            System.out.printf("stack[%d]=%d\n",i,stack[i]);
        }
    }

}

习题2:回文数

回文: 一个单词、短语或数字,从前往后写和从后往前写都是一样的。比如,单词“dad”、“racecar”就是回文;如果忽略空格和标点符号,下面这个句子也是回文,“A man, a plan, a canal: Panama”, 数字1001 也是回文。

思路:使用栈,可以轻松判断一个字符串是否是回文。我们将拿到的字符串的每个字符按从左至右的顺序压入栈。当字符串中的字符都入栈后,栈内就保存了一个反转后的字符串,最后的字符在栈顶,第一个字符在栈底

public static boolean detection(String words){
        ArrayStack arrayStack = new ArrayStack(10);
        int length = words.length();
        for (int i=0;i<length;i++){
            arrayStack.push(words.charAt(i));
        }
        String newValue = "";
        for (int i=0;i<arrayStack.length();i++){
            if (!arrayStack.isEmpty()){
                Object value = arrayStack.pop();
                newValue = newValue+value;
            }
        }
        if (words.equals(newValue)){
            return true;
        }
        return false;
    }

栈实现计算器

思维分析结果图:

图片[6] | Web Stack | 数据结构与算法-栈 | 一个栈
ArrayStack
public class ArrayStack {
    /**
        栈的大小
     */
    private int maxStack;

    /**
        数组用来模拟栈
     */
    private int[] stack;

    /**
     * 表示栈顶,默认值为-1
     */
    private int top = -1;

    /**
     *
     * @param maxStack 初始化栈的大小
     */
    public ArrayStack(int maxStack){
        this.maxStack = maxStack;
        this.stack = new int[this.maxStack];
    }

    /**
     *  判断是否已经栈满
     * @return
     */
    public boolean isFull(){
        return this.top==maxStack-1;
    }

    /**
     * 是否空栈
     */
    public boolean isEmpty(){
        return this.top==-1;
    }

    /**
     * 入栈
     */
    public void push(int value){
        if (isFull()){
            throw new RuntimeException("栈已满...");
        }

        top++;
        stack[top] = value;
    }

    /**
     *出栈
     */
    public int pop(){
        if (isEmpty()){
            throw new RuntimeException("空栈,没有数据");
        }
        int value = stack[top];
        top--;
        return value;
    }

    /**
     * 查看栈中数据
     */
    public void list(){
        if (isEmpty()){
            throw new RuntimeException("空栈,没有数据");
        }
        for (int i=0;i<stack.length;i++){
            System.out.printf("stack[%d]=%d\n",i,stack[i]);
        }
    }

    /**
     * 查看栈大小
     * @return
     */
    public int length(){
        return stack.length;
    }

    /**
     * 查看栈顶
     * @return
     */
    public int peek(){
        return stack[top];
    }

    /**
     * 运算符优先级
     * 数字越大优先级越高
     */
    public int priority(int oper){
        if (oper=='*' || oper=='/'){
            return 1;
        }else if (oper=='+' || oper=='-'){
            return 0;
        }else {
            return -1;
        }

    }
    /**
     * 判断是否是一个运算符
     */
    public boolean isOper(char v){
        return v=='+' || v=='-'||v=='*'||v=='/';
    }

    /**
     * 计算
     */
    public int calculate(int num1,int num2,int oper){
        int res = 0;
        switch (oper){
            case '+':
                res=num1+num2;
                break;
            case '-':
                res=num2-num1;
                break;
            case '*':
                res=num1*num2;
                break;
            case '/':
                res=num2/num1;
                break;

                default:
                    break;

        }
        return res;
    }

main

public static void main(String[] args) {


        String str = "3+2*3-1-1";

        ArrayStack numStack = new ArrayStack(10);
        ArrayStack symbolStack = new ArrayStack(10);
        int length = str.length();
        int temp1 = 0;
        int temp2 = 0;
        int symbolChar = 0;
        int result = 0;
        String values = "";
        for (int i=0;i<length;i++) {
            //获取每一个字符
            char c = str.charAt(i);
            //判断是否是一个字符
            if (symbolStack.isOper(c)){
                //如果字符栈中不是空栈
                if (!symbolStack.isEmpty()){
                    //如果当前字符优先级小于等于字符栈中存在的
                    if (symbolStack.priority(c)<=symbolStack.priority(symbolStack.peek())){
                        /**
                         * 即从数字栈中pop出来两个数字,再从符号栈中pop出来一个符号进行计算,然后把结果
                         * 然后把结果再次存入栈中
                         */
                        temp1 = numStack.pop();
                        temp2 = numStack.pop();
                        symbolChar = symbolStack.pop();
                        result = numStack.calculate(temp1,temp2,symbolChar);
                        //把计算结果再次放入栈中
                        numStack.push(result);
                        //把当前符号放入栈中
                        symbolStack.push(c);
                    }else {
                        //如果当前符号优先级大于符号栈中的符号,直接放入符号栈中
                        symbolStack.push(c);
                    }
                }else {
                    //如果符号栈中是空,则也直接如符号栈
                    symbolStack.push(c);
                }
            }else {
                //如果扫描的是数字。数字很能存在多位,比如33,22,100,如何能保证这多位数字
                //判断当前字符后一位是否是一个字符,如果是字符表示当前数字结束直接存入数字栈,如果不是字符,表示
                //这是一个多位数字
                values+=c;
                if (i==length-1){//表示是最后一个数字,可以直接存放在数字栈中
                    numStack.push(Integer.parseInt(values));
                }else {
                    char data = str.substring(i+1, i + 2).charAt(0);
                    if (symbolStack.isOper(data)){//如果是符号,则把数字存入数字栈中,并清空values。
                        numStack.push(Integer.parseInt(values));
                        values="";
                    }
                }

            }
        }

        while (true){
            if (symbolStack.isEmpty()){
                break;
            }
            temp1 = numStack.pop();
            temp2 = numStack.pop();
            symbolChar = symbolStack.pop();
            result = numStack.calculate(temp1,temp2,symbolChar);
            numStack.push(result);
        }
        int res = numStack.pop();
        System.out.println("结果是:"+res);
    }

温馨提示:本文最后更新于2022-09-01 20:37:28,某些文章具有时效性,若有错误或已失效,请在下方留言或联系雅舍站长
© 版权声明
THE END
有所帮助就支持一下吧
点赞11 分享
箴言区 抢沙发
头像
达瓦里希请发言...
提交
头像

昵称

取消
昵称表情代码图片