数据结构之栈的实现

绝地灬酷狼 2022-09-14 14:26 222阅读 0赞

**目录**

目标

栈结构示意图

代码实现

附加题

判断括号串是否规范

总结

--------------------

# 目标 #

*  熟悉栈结构，包括入栈，出栈的具体操作；
 *  能独立实现栈结构（可以用数组实现，也可以用链表实现，本文使用数组实现。）。

--------------------

# 栈结构示意图 #

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bGx5YmN55WZ5ZCN_size_20_color_FFFFFF_t_70_g_se_x_16][]

--------------------

# 代码实现 #

package com.ctx;
    
    import java.lang.reflect.Array;
    
    /**
     * @describe 用数组实现栈
     */
    public class MyArrayStack<T> {
        private T[] array;
        //数组大小
        private int size;
        //数组中元素的个数
        private int num = 0;
        Class<T> componentType;
    
        public MyArrayStack(Class<T> componentType, int size) {
            this.size = size;
            this.array = (T[]) Array.newInstance(componentType, size);
            this.componentType = componentType;
        }
    
        /**
         * 获取元素个数
         *
         * @return
         */
        public int num() {
            return num;
        }
    
        /**
         * 获取数组大小
         *
         * @return
         */
        public int size() {
            return size;
        }
    
        /**
         * 扩容数组
         *
         * @param t       数组
         * @param newSize 数组扩容后的大小
         * @return
         */
        private boolean expandSize(T[] t, int newSize) {
            //创建一个新数组
            T[] newT = (T[]) Array.newInstance(componentType, newSize);
            //遍历新数组
            for (int i = 0; i < size; i++) {
                newT[i] = t[i];
            }
            array = newT;
            size = newSize;
            return true;
        }
    
        /**
         * 数组是否满了
         *
         * @return
         */
        private boolean isFull() {
            return num == size ? true : false;
        }
    
        /**
         * 入栈
         *
         * @param t
         */
        public void add(T t) {
    
            //元素个数=数组容量，需要扩容。
            if (isFull()) {
                //这里扩容为原来的2倍
                expandSize(array, size * 2);
            }
            //元素个数加1
            num++;
            //元素下标=元素个数-1
            array[num - 1] = t;
        }
    
        /**
         * 出栈
         *
         * @return
         */
        public T delete() {
            if (num == 0) {
                throw new IndexOutOfBoundsException();
            }
            num = num - 1;
            //后入栈的先出栈
            T t = array[num];
            array[num] = null;
    
            return t;
        }
    
        public T get(int index) {
            if (index + 1 > num) {
                throw new IndexOutOfBoundsException();
            }
            return array[index];
        }
    
        public static void main(String[] args) {
            MyArrayStack<String> list = new MyArrayStack<>(String.class, 10);
            list.add("A");
            list.add("B");
            list.add("C");
            list.add("D");
            list.add("E");
            list.add("F");
            list.add("G");
            list.add("H");
            list.add("I");
            list.add("J");
            System.out.println("==================" + list.size);
            list.add("K");
            list.add("L");
            System.out.println("==================" + list.size);
            list.delete();
            list.delete();
            list.delete();
            for (int i = 0; i < list.num(); i++) {
                System.out.println(list.get(i));
            }
        }
    }

--------------------

# 附加题 #

## 判断括号串是否规范 ##

package com.ctx;
    
    /**
     * @describe 给定一串括号，如何判断括号符合正常的使用规则。正常：[[({})]()]；错误：(()){
       {}
     */
    public class Brackets {
        public static void main(String[] args) {
            System.out.println(fun("[[({})]()]"));
            System.out.println(fun("(()){
       {}"));
        }
    
        public static boolean fun(String bra) {
            MyArrayStack<String> stack = new MyArrayStack<String>(String.class, 20);
            String[] split = bra.split("");
            for (String s : split) {
                switch (s) {
                    case "(":
                    case "[":
                    case "{":
                        stack.add(s);
                        break;
                    case ")":
                        //出栈
                        if (!stack.delete().equals("(")) {
                            return false;
                        }
                        break;
                    case "]":
                        //出栈
                        if (!stack.delete().equals("[")) {
                            return false;
                        }
                        break;
                    case "}":
                        //出栈
                        if (!stack.delete().equals("{")) {
                            return false;
                        }
                }
            }
            return stack.num() > 0 ? false : true;
        }
    }

--------------------

# 总结 #

1.  出栈和入栈的时间复杂度为O(1)，用数组实现的栈，扩容的时间复杂度是O(n)；
2.  数组和链表都可以实现栈，但是数组可以更好地控制元素数量，而链表对元素数量没有限制，容易耗尽内存，但是数组比链表扩容麻烦。

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bGx5YmN55WZ5ZCN_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/cd64462051474900bc2643a584f75ff5.png