数据结构与算法--简单栈实现及其应用

港控/mmm° 2022-12-26 09:21 169阅读 0赞

#### 栈 ####

*  栈（Stack）是一种限制插入和删除只能在一个位置上进行的表，改位置是表的末端，叫做栈顶top。栈的基本操作有push （进栈）pop（出栈）
 *  栈又叫做LIFO（后进先出）表，下图展示普通push输入，而pop和top是输出操作。普通的清空栈，判断是否空栈操作都是基本操作指令，但是我们对栈的具体修改操作基本也就是push和pop。下图模型中表示若干操作后，一个抽象的栈只有栈顶元素是可见的，其他不可见。  
    ![在这里插入图片描述][20201204112500313.png]

##### 栈的实现 #####

*  由于栈是一个表，因此任何实现表的方法都能够实现栈，显然，ArrayList， LinkedList都支持这些操作，99%的时间他们都是最合理的选择，偶尔设计一种特殊目的的实现可能会更快。因为栈操作是常数时间操作，所以除非在非常特殊的环境下，一般都是这两种方式，这两种一种是链式结构，一种是数组结构，二者都简化了在ArrayList和LinkedList中的逻辑，

###### 栈的链表实现 ######

*  栈的第一种实现是单链表，通过在表的顶端插入实现push，通过删除表顶端实现pop。top操作只是查询表顶端元素并返回他的值。

###### 栈的数组实现 ######

*  另一种实现方法避免了链而且可能是最流行的解决方法。模拟ArrayList的Add操作，因此现有的实现方法非常简单，与每个栈相关联的参是push，pop，都是对数组末尾的数据进行操作，对空栈他是-1。
    
     *  将元素X推入栈，top 增加1，并且array\[last\]=X
     *  将元素弹出栈，返回array\[top\]，并且top减1
 *  以上测操作都是以常数时间运行，非常快速的只有一个操作，以下我们用数组实现自己的一个栈：

/** * @author liaojiamin * @Date:Created in 18:07 2020/12/2 */
    public class MyStack<E> { 
        private Object[] elementData;
        private Integer top;
        private Integer capacity;
        private Integer position;
    
        /** * 数组，指针，位置信息 初始化 * */
        public MyStack() { 
            elementData = new Object[10];
            top = -1;
            capacity = elementData.length - 1;
            position = 0;
        }
    
        /** * 扩容 * */
        public void reSize() { 
            if (position == capacity) { 
                Integer newCapacity = capacity + (capacity >> 1);
                elementData = Arrays.copyOf(elementData, newCapacity);
                capacity = newCapacity;
            }
        }
    
        /** * 添加推入数据 * */
        public Object push(E e) { 
            reSize();
            top = position;
            elementData[position++] = e;
            return e;
        }
    
        /** * 删除，推出数据 * */
        public E pop(){ 
            if(top == -1){ 
                return null;
            }
            E e = (E)elementData[top--];
            position --;
            return e;
        }
    
        /** * 查看栈顶元素 * */
        public E getTop(){ 
            return (E)elementData[top];
        }
    
        /** * 判断是否为空 * */
        public boolean isEmpty(){ 
            return top == -1;
        }
    
        /** * 当前栈存储数据个数 * */
        public int size(){ 
            return position;
        }
     /** * 打印输出 */
     public void printMyStack(){ 
            Integer temp = top;
            while (top != -1){ 
                System.out.print(pop());
            }
            top = temp;
        }
    
        public static void main(String[] args) { 
            MyStack<Integer> myStack = new MyStack<Integer>();
            for (int i = 0; i < 100; i++) { 
                myStack.push(i);
            }
            Integer result = 0;
            while (result != null){ 
                result = myStack.pop();
                System.out.println(result);
            }
        }
    }

#### 应用 ####

*  我们以上示例中将操作限制在一个表上进行，你们这些操作会执行很快，然而这样操作是非常重要的，维护了栈中的数据关系。在栈的应用中给出了三个例子，实现了其中一个作为参考。

##### 平衡符号 #####

*  编译器检查程序的语法错误，经常会因为缺少一个符号，比如花括号，引起编译器上百行的错误提示，而真正的错误并没有找出来。
 *  这种情况，有一个有用的工具就是检验是否每一件事情都成对出现。
 *  每一个右括号，右方括号，右花括号都比如对应左边括号。序列\{()\} 是合法的，但是\{(\]\}是非法的。
 *  事实上检测这些事情是很容易的，为简单起见，我们直接利用栈就可以做一个简单实现，流程如下：
    
     *  做一个空栈，读入字符，直到文件结尾。
     *  如果字符是一个开放括号，推入栈
     *  如果字符是一个封闭括号，则当栈空时候，报错，否则将栈元素弹出。
     *  如果弹出的符合不是对应的开放符号的括号，报错
     *  文件结尾，如果栈非空，报错

##### 后缀表达式 #####

*  假设我们有一个便携计算器用于计算，为此，将一系列数据进行±\*/之后得到结果，如果购物单价是4.99,5.99,6.99,数量是1,1，2，那么输入这些数据的如下：

4.99 + 5.99 + 6.99 * 2

*  普通计算器并不能识别先加减后乘除，得到的结果是：35.94，但是我们期望得到的结果是 24.96
 *  只有科学计算器才支持复杂计算，科学计算器，实现中，将6.99\*2 结果存储A1，将5.99与A1 相加得到A2，再将4.99与A2 相加得到组中的结果，我们将这种操作顺序书写如下

4.99 5.99 + 6.99 2 * +

*  以上操作符记录方式叫做后缀（postfix）或者逆波兰（reverse polish）表达式，求值过程恰好就是上面描述的过程，计算这个问题最容易的方法就是使用栈。当看到一个数时候，将他推入栈，遇到运算符就将栈中头两个数据弹出，计算，接入推入栈中。例如如下后缀表达式计算过程动图如下：
 *  表达式：1 2+3-4 5\*+  
    ![在这里插入图片描述][20201204141837785.gif_pic_center]
 *  如上动图展示全流程，计算一个后缀表达式花费的世界是O(N)，因为对于输入中的每个元素的处理都是有一些栈操作组成从而花费常数的时间。算法简单。注意：当一个表达式以后缀的方式给出的时候，没有必要知道任何的优先规则，因为在中序，转后缀表达式的时候已经考虑过，这个是一个明显的优点。

###### 中缀表达式转后缀表达式 ######

*  上面讲到后缀表达式的计算，那我们如何将中缀表达式转后缀，也是可以用栈来完成这个操作，我们用简单的±\*/（，这几个操作符，我们用如下案例来说明:

a+b*c+(d*e+f)*g

*  转后缀表达式得到如下：

1 2 3 * 4 5 * 6 + 7 * + +

###### 算法分析 ######

*  操作符优先级，‘）’右括号 > \*/ 乘除 > ±加减 > ‘(’ 左括号
 *  依次读取操作数，将数字推入number 栈，将操作符推入action栈
 *  右括号‘）’，依次将action中操作符弹出，直到遇见左括号‘（’
 *  如果见到任何其他符号（+，-,\*,/,(）,如果当前栈顶元素X优先级高于当前元素Y，那么弹出栈顶元素X，将X加入number栈，并将当前元素Y加入到action栈
 *  如果读到末尾，我们需要将action栈元素依次弹出加入到number栈

###### 动图展示 ######

![在这里插入图片描述][20201204153330231.gif]

*  与前面的计算相同，这种转换同样也只要O(N)时间，并经过一次输入后就完成工作。以下代码通过自己实现的栈，实现中缀表达式转后缀表达式，并且计算后缀表达式得到对应结果

/** * @author liaojiamin * @Date:Created in 15:13 2020/12/3 */
    public class Evaluate { 
    
        public static MyStack<String> middlePreTOAfterPre(String mathStr) { 
            MyStack<String> number = new MyStack<>();
            MyStack<String> action = new MyStack<>();
            String[] chars = mathStr.split(" ");
            for (int i = 0; i < chars.length; i++) { 
                String s = String.valueOf(chars[i]);
                switch (flag(s, action)) { 
                    case 1:
                        number.push(s);
                        break;
                    case 2:
                        action.push(s);
                        break;
                    case 3:
                        action.push(s);
                        break;
                    case 4:
                        number.push(action.pop());
                        action.push(s);
                        break;
                    case 5:
                        action.push(s);
                        break;
                    case 6:
                        while (!action.isEmpty()) { 
                            String temp = action.pop();
                            if (temp.matches("\\(")) { 
                                break;
                            } else { 
                                number.push(temp);
                            }
                        }
                        break;
                    default:
                        break;
                }
            }
            while (!action.isEmpty()) { 
                number.push(action.pop());
            }
            MyStack<String> temp = new MyStack<>();
            while (!number.isEmpty()) { 
                temp.push(number.pop());
            }
            return temp;
        }
    
    
        /** * 中序转后序表达式的各种逻辑判断 */
        public static int flag(String s, MyStack<String> action) { 
            if (s.matches("([1-9]\\d*\\.?\\d*)|(0\\.\\d*[1-9])")) { 
                //数字
                return 1;
            }
            if (s.matches("(\\*)|(\\/)|(\\+)|(\\-)")) { 
                if (action.isEmpty()) { 
                    //栈为空
                    return 2;
                } else if (prior(s, action.getTop())) { 
                    //不为空，优先级高于栈顶元素
                    return 3;
                } else { 
                    //不为空，优先级不高于于栈顶元素
                    return 4;
                }
            }
            if (s.matches("\\(")) { 
                //左括号
                return 5;
            }
            if (s.matches("\\)")) { 
                //右括号
                return 6;
            }
            return 0;
        }
    
        /** * @return 优先级 * @author: liaojiamin * @description:s 操作符， top 栈顶操作符 */
        public static boolean prior(String s, String top) { 
            if (top.matches("\\(")) { 
                return true;
            }
            if (s.matches("(\\*)|(\\/)") && top.matches("(\\+)|(\\-)")) { 
                return true;
            }
            return false;
        }
    
        public static Double evalutePostfix(MyStack<String> myStack){ 
            MyStack<String> newStack = new MyStack<>();
            while (!myStack.isEmpty()){ 
                String temp = myStack.pop();
                if(temp.matches("\\d+")){ 
                    newStack.push(temp);
                }else if(temp.matches("(\\*)|(\\/)|(\\+)|(\\-)")){ 
                    if(newStack.size() < 2){ 
                       break;
                    }
                    double a = Double.valueOf(newStack.pop());
                    double b = Double.valueOf(newStack.pop());
                    switch (temp){ 
                        case "+":
                            newStack.push(String.valueOf(b+a));
                            break;
                        case "-":
                            newStack.push(String.valueOf(b-a));
                            break;
                        case "*":
                            newStack.push(String.valueOf(b*a));
                            break;
                        case "/":
                            newStack.push(String.valueOf(b/a));
                            break;
                        default:
                            break;
                    }
    
                }
            }
            return Double.valueOf(newStack.pop());
        }
    
         public static void main(String[] args) { 
            MyStack<String> middlerStack = middlePreTOAfterPre("67 - 8 + 9 * ( 1 + 4 - 5 / 3 ) + ( 8 - 4 * 2 ) + 8 - 21");
            middlerStack.printMyStack();
            System.out.println();
            System.out.println(evalutePostfix(middlerStack));
        }
    }

*  注意：以上带有减法，除法， 在具体计算时候，应该是 （第二个弹出值- 第一个弹出值），除法也是类似，只有这个顺序区别，其他的和以上描述一致。
 *  其实中缀转后缀唯一的一个重要规则就是：高优先级操作符入栈，需要保证低下的操作符优先级比我更低或相等，否则就弹出顶部操作符，也就是算法分析中的第四点：
    
     *  **如果见到任何其他符号（+，-,\*,/,(）,如果当前栈顶元素X优先级高于当前元素Y，那么弹出栈顶元素X，将X加入number栈，并将当前元素Y加入到action栈**

##### 应用三 #####

*  方法调用，略

[上一篇：数据结构与算法–排序算法总结（动图演示）][Link 1]  
[下一篇：数据结构与算法–利用栈实现队列][Link 2]

[20201204112500313.png]: /images/20221120/7f539a99b27c44e2a9656eee1953201b.png
[20201204141837785.gif_pic_center]: /images/20221120/d1ae6142b57d405d88583e8938096252.png
[20201204153330231.gif]: /images/20221120/7398bfd4ea524bb7bd05398b34360662.png
[Link 1]: https://blog.csdn.net/liaojiamin0102/article/details/109512635
[Link 2]: https://blog.csdn.net/liaojiamin0102/article/details/114579897