【数据结构与算法之线性结构】栈

﹏ヽ暗。殇╰゛Y 2024-03-25 12:36 129阅读 0赞

#### 【数据结构与算法之线性结构】栈 ####

#### 文章目录 ####

*   *   *  【数据结构与算法之线性结构】栈
         *   *   *  1 栈的基本概念
                 *  2 栈的定义
                 *  3 栈的基本操作
                 *   *  入栈
                     *  出栈
                 *  4 案例
                 *   *  二/十进制转换器
                     *  括号匹配问题

###### 1 栈的基本概念 ######

栈Stack 是一个后进先出 LIFO的线性表，它要求只能在表尾执行删除和插入等操作。其实栈就是一个线性表(可以是数组，也可以是链表)，就是操作受到限制。

栈的操作只能在线性表尾进行，表尾 → 栈顶top，表头 → 栈底bottom。

![在这里插入图片描述][9c60084045d344f89d4dd1ad58eabc47.png_pic_center]

###### 2 栈的定义 ######

使用数组实现栈。

这里我们并没有定义栈顶位置的值，因为用数组实现栈的话，bottom恒为0就行了，如果使用链表实现栈，则需要定义bottom，它应该是指向栈顶节点的指针变量。

初始化后，top = bottom = 0，说明此时空栈。

###### 3 栈的基本操作 ######

###### 入栈 ######

入栈就是向栈中存入数据。入栈操作在栈顶执行，每当向栈中压入一个数据，栈顶指针top + 1，直到栈满。

public void push(int elem) {
        
        // 元素入栈
        if (top == capacity) {
        
            // 扩容
            increaseCapacity();
        }
        stack[top] = elem;
        top++;
    }
    
    public void increaseCapacity() {
        
        // 增加栈的容量
        // 初始化一个新栈，容量是原栈容量的2倍
        int[] stackTmp = new int[stack.length * 2];
        System.arraycopy(stack, 0, stackTmp, 0, stack.length);
        stack = stackTmp;
    }

top 始终指向栈顶元素的上一个位置，所以当top 数值上 = capacity时，说明栈满。

###### 出栈 ######

出栈与入栈相反，从栈顶取出元素，top -1 。

public int pop() {
        
        // 出栈
        if (top == 0) {
        
            System.out.println("栈中没有数据");
            return -1; // 返回一个无效值
        }
        top--;
        return stack[top];
    }

测试

/**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: MyStack
     * @Author: Ding Jiaxiong
     * @Data:2023/3/13 9:27
     */
    
    public class MyStack {
        
    
        int[] stack; // 数组实现栈
        int top; // 栈顶索引
        int capacity; // 栈的容量
    
        public MyStack(int capacity) {
        
            stack = new int[capacity]; // 动态初始化栈，长度为capacity
            top = 0; // 栈顶索引为0，说明此时栈空
            this.capacity = capacity; // 初始化栈的容量
        }
    
        public void push(int elem) {
        
            // 元素入栈
            if (top == capacity) {
        
                // 扩容
                increaseCapacity();
            }
            stack[top] = elem;
            top++;
        }
    
        public void increaseCapacity() {
        
            // 增加栈的容量
            // 初始化一个新栈，容量是原栈容量的2倍
            int[] stackTmp = new int[stack.length * 2];
            System.arraycopy(stack, 0, stackTmp, 0, stack.length);
            stack = stackTmp;
        }
    
        public int pop() {
        
            // 出栈
            if (top == 0) {
        
                System.out.println("栈中没有数据");
                return -1; // 返回一个无效值
            }
            top--;
            return stack[top];
        }
    
        public static void main(String[] args) {
        
    
            MyStack stack = new MyStack(3);
            stack.push(1);
            stack.push(2);
            stack.push(3);
            stack.push(4);
            stack.push(5);
    
            System.out.println(stack.pop());
            System.out.println(stack.pop());
            System.out.println(stack.pop());
            System.out.println(stack.pop());
            System.out.println(stack.pop());
        }
    }

运行结果

![在这里插入图片描述][34878f7786974e9b9acef51fbdc9cd5b.png_pic_center]

如果再弹

![在这里插入图片描述][0c2bed29038a42f88ba5561eaa86233f.png_pic_center]

没问题。

###### 4 案例 ######

###### 二/十进制转换器 ######

利用栈结构将二进制数转为十进制数。

举个栗子：将二进制数 11001转换为十进制数, → 1x2^0 + 0x2^1 + 0x2^2 + 1x2^3 + 1x2^4 = 25.

由于栈后进先出的特性，首先将二进制数从高位到地位顺序入栈，从栈顶依次取出，第i个元素，就对应的乘上  2 i − 1 2^\{i - 1\} 2i−1 。

Java代码实现：

/**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: BiToDecTest
     * @Author: Ding Jiaxiong
     * @Data:2023/3/13 10:15
     */
    
    public class BiToDecTest {
        
    
        public static String BiToDec(String binary) {
        
            MyStack stack = new MyStack(10);
            int i;
    
            // 将二进制串binary 从高位到地位入栈
            for (i = 0; i < binary.length(); i++) {
        
                if (binary.charAt(i) == '0') {
        
                    stack.push(0); // 将0整数形式入栈
                } else {
        
                    stack.push(1); // 1同理
                }
            }
    
            i = 0;
            int e;
            long sum = 0;
    
            // 将栈中元素顺序出栈，并将其转换为十进制数
            while ((e = stack.pop()) != -1) {
         // 没到栈底
                sum += (int) (e * Math.pow(2, i));
                i++;
            }
    
            return String.valueOf(sum);
        }
    
        public static void main(String[] args) {
        
    
            System.out.println(BiToDec("11001"));
        }
    
    }

运行结果

![在这里插入图片描述][1c22238550564092a59722690474db01.png_pic_center]

###### 括号匹配问题 ######

判断表达式中有两种括号， () 和 \[\]，括号必须成对出现，编写一个程序，判断一个括号表达式是否合法。

【经典问题】利用栈来保存输入的括号，并判断输入的括号表达式是否合法。

每输入一个括号都与栈顶的括号进行比较，如果输入括号与栈顶保存的括号匹配，则栈顶出栈，如果不匹配，则输入符号入栈。输入完毕时，栈为空则表示合法，如果栈中还有剩余元素，则表明输入不完全匹配。

Java实现：

稍微进行了修改的自定义栈类：

/**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: MyStack
     * @Author: Ding Jiaxiong
     * @Data:2023/3/13 9:27
     */
    
    public class MyStack {
        
    
        char[] stack; // 数组实现栈
        int top; // 栈顶索引
        int capacity; // 栈的容量
    
        public MyStack(int capacity) {
        
            stack = new char[capacity]; // 动态初始化栈，长度为capacity
            top = 0; // 栈顶索引为0，说明此时栈空
            this.capacity = capacity; // 初始化栈的容量
        }
    
        public void push(char elem) {
        
            // 元素入栈
            if (top == capacity) {
        
                // 扩容
                increaseCapacity();
            }
            stack[top] = elem;
            top++;
        }
    
        public void increaseCapacity() {
        
            // 增加栈的容量
            // 初始化一个新栈，容量是原栈容量的2倍
            char[] stackTmp = new char[stack.length * 2];
            System.arraycopy(stack, 0, stackTmp, 0, stack.length);
            stack = stackTmp;
        }
    
        public char pop() {
        
            // 出栈
            if (top == 0) {
        
    //            System.out.println("栈中没有数据");
                return ' '; // 返回一个无效值
            }
            top--;
            return stack[top];
        }
    
        public static void main(String[] args) {
        
    
            MyStack stack = new MyStack(3);
            stack.push('a');
            stack.push('b');
            stack.push('c');
            stack.push('d');
            stack.push('e');
    
            System.out.println(stack.pop());
            System.out.println(stack.pop());
            System.out.println(stack.pop());
            System.out.println(stack.pop());
            System.out.println(stack.pop());
        }
    }

测试

import java.util.Stack;
    
    /**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: MatchBracketTest
     * @Author: Ding Jiaxiong
     * @Data:2023/3/13 10:28
     */
    
    public class MatchBracketTest {
        
    
        private static boolean match(char a, char b) {
        
            if ((a == '(' && b == ')') || (a == '[' && b == ']')) {
        
                return true;
            }
            return false;
        }
    
        public static boolean MatchBracket(String expression) {
        
    
            // 判断括号表达式expression是否合法
    
            MyStack stack = new MyStack(10);
            char c;
            for (int i = 0; i < expression.length(); i++) {
        
                if ((c = stack.pop()) != ' ') {
        
                    if (!match(c, expression.charAt(i))) {
        
                        stack.push(c);
                        stack.push(expression.charAt(i));
                    }
                } else {
        
                    stack.push(expression.charAt(i));
                }
            }
    
            if (stack.pop() != ' ') {
        
                return false;
            } else {
        
                return true;
            }
        }
    
        public static void main(String[] args) {
        
    
            String expression = "[([])]";
            System.out.println(MatchBracket(expression));
    
        }
    
    }

运行结果【匹配情况】

![在这里插入图片描述][20dfe1ea787f490d91c79515b41b3a74.png_pic_center]

不匹配情况

![在这里插入图片描述][a126c1a6357b4cdfb2c1cf1a49274b4a.png_pic_center]

[9c60084045d344f89d4dd1ad58eabc47.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/691a073dcc8e471cb640ac2c9dcc4ac7.png
[34878f7786974e9b9acef51fbdc9cd5b.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/966f2cf5990a4322babb6c725885cc33.png
[0c2bed29038a42f88ba5561eaa86233f.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/33ff207b3b8b4771ada43e684095de38.png
[1c22238550564092a59722690474db01.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/157230e4b8d24badb1a6c7769038bf18.png
[20dfe1ea787f490d91c79515b41b3a74.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/1eb283dc507042d3a7709f2f1d1da10e.png
[a126c1a6357b4cdfb2c1cf1a49274b4a.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/0a9eb2725f0243219a3cd81595e1ce2b.png