[从今天开始修炼数据结构]栈、斐波那契数列、逆波兰四则运算的实现
一、栈的定义
栈是限定仅在表尾进行插入和删除操作的线性表。允许插入和删除的一端称为栈顶(top),另一端称为栈底(bottom)。栈又称后进先出的线性表,简称LIFO结构。
注意:首先它是一个线性表,也就是说栈元素有前驱后继关系。
栈的插入操作,叫做进栈,也称压栈、入栈
栈的删除操作,叫做出栈,也叫弹栈。
注意:最先入栈,不代表就要最后出栈。因为栈没有限制出栈的时间,例如可以先入栈两个元素,再出栈两个元素,后入栈其他元素。
二、栈的抽象数据类型
ADT Stack Data 同线性表。元素具有相同的类型,相邻元素具有前驱和后继。 Operation InitStack(S) : 初始化操作,建立一个空栈 DestroyStack(S):若栈存在,销毁它。 ClearStack(S):将栈清空 StackEmpty:若栈为空,返回true,否则返回false。 GetTop(S,e):若栈存在且非空,用e返回栈顶元素。 Push(S,e):若栈S存在,插入新元素e到栈顶 Pop(S,e):删除S中栈顶元素,并用e返回其值 StackLength(S):返回栈S中的元素个数 endADT
三、栈的顺序结构
1,栈的顺序存储结构是什么样子
栈的顺序存储结构也是用数组来实现的。让下标0的一端作为栈底,另一端作为栈顶。若存储栈的长度为StackSize,则栈顶位置top必须小于StackSize。当栈存在一个元素时,top = 0.因此通常把空栈的判定条件定为top = - 1。
2,顺序结构栈的实现
package Stack; public class ArrayStack<T>{ private Object[] list; private int top; private int size; private static int DEFAULT_SIZE = 10; public ArrayStack(int size){ list = new Object[size]; this.size = size; top = -1; } public ArrayStack(){ this(DEFAULT_SIZE); } public void push(T data){ if (!isFull()){ list[++top] = data; }else { System.out.println("栈满了"); } } public T pop(){ if (!isEmpty()){ T obj = (T)list[top]; list[top] = null; top--; return obj; }else { System.out.println("栈是空的"); } return null; } private boolean isEmpty(){ return top == -1; } private boolean isFull() { return top >= size; } public int size(){ return size; } public int getTop(){ return top; } }
四、共享栈
1,共享栈是指两栈共享一片空间的栈。如下图所示
两个栈共用一块数组,以两头为栈底,中间为栈顶。可以节省空间。判断满的方法是top1 + 1 = top2.
2,共享栈的实现。
package Stack; public class ShareStack<T> { private Object[] list; private int top1; private int top2; private int capacity; private static int DEFAULT_SIZE = 10; //private boolean isFull = false; public ShareStack(int capacity){ list = new Object[capacity]; this.capacity = capacity; top1 = -1; top2 = capacity; } public ShareStack(){ this(DEFAULT_SIZE); } public boolean pushStackOne(T data){ if (!isFull()){ list[++top1] = data; //isFull = isFull(); return true; }else{ System.out.print("栈满了!"); return false; } } public boolean pushStackTwo(T data){ if (!isFull()){ list[--top2] = data; //isFull = isFull(); return true; }else{ System.out.print("栈满了!"); return false; } } public T popStackOne(){ if (!isEmptyOne()){ T data = (T)list[top1--]; return data; }else { System.out.println("栈一是空的!"); return null; } } public T popStackTwo(){ if (!isEmptyTwo()){ T data = (T)list[top2++]; return data; }else { System.out.println("栈二是空的!"); return null; } } private boolean isEmptyTwo() { return top2 == capacity; } private boolean isFull() { return top1 == (top2 - 1); } private boolean isEmptyOne(){ return top1 == -1; } }
五、栈的链式存储及实现
1,栈的链式存储简称链栈,把栈顶放在单链表的头部。如下图
2,链栈的实现
public class LinkedStack<T> { private Node<T> top; public void push(T data){ Node<T> newNode = new Node<>(data, null); Node<T> t = top; top = newNode; top.next = t; } public T pop(){ Node<T> t = top; if (!isEmpty()){ top = top.next; return t.data; }else { System.out.println("栈为空!"); return null; } } private boolean isEmpty() { return top == null; } private class Node<T> { private T data; private Node next; public Node(T data, Node<T> next){ this.data = data; this.next = next; } } }
以表头为栈顶,降低了弹栈操作的时间复杂度。若以表尾为栈顶则弹栈只能遍历找到top-1位置,或者用双向链表牺牲空间。如下
public T pop(){ if (!isEmpty()){ Node<T> newTop = bottom; while (newTop.next != top){ newTop = newTop.next; } T data = top.data; top = newTop; top.next = null; return data; }else { System.out.println("栈是空的!"); return null; } }
五、栈的应用 —— 递归
1,斐波那契数列的递归实现
引例:如果兔子在出生两个月后就有繁殖能力,一对兔子每个月能生出一对小兔子。假设所有兔子都不死,那么一年后有多少对兔子?分析得出兔子数量按天数增加如下表
所经过的月数 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
兔子对数 | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 | 89 | 144 |
表中数列有明显的特点:相邻前两项之和等于后一项。抽象成函数表达如下
迭代实现如下:
public class Fibonacci { public static void main(String[] args) throws Exception { System.out.println(Fibonacci(12)); } public static int Fibonacci(int month) throws Exception { if (month < 0){ throw new Exception(); } if (month < 2){ return month == 0 ? 0 : 1; }else { return (Fibonacci(month - 1) + Fibonacci(month - 2)); } }}
代码执行过程如下:
递归实现法的时间复杂度为O(2n),太高,还可能会引起内存栈溢出,所以应该用别的方法求解。这篇文章主要讲由栈引出递归,所以先挖个坑,在后面的文章中我会单独讨论递归和斐波那契数列的其他解法。
参考:https://blog.csdn.net/sofia_m/article/details/78796084
https://blog.csdn.net/IronWring_Fly/article/details/100050016
https://blog.csdn.net/Bob__yuan/article/details/84956740
2,在前行阶段,对于每一层递归,函数的局部变量、参数值以及返回地址都被压入栈中。在退回阶段,位于栈顶的局部变量、参数值和返回地址被弹出,用于返回调用层次中执行代码的其余部分,也就是恢复了调用的状态。
六、栈的应用 —— 四则运算表达式求值
1,后缀(逆波兰)表示法定义
对于会计计算器,不能表达复杂的带括号和多种运算符号复合的表达式;而对于科学计算器,我们可以一次将一个复杂的带括号的四则运算输入进去,计算器是怎么做到的呢?
这就引入了一种不需要括号的后缀表达法 —— 逆波兰表达法。举个例子来看 对于 “ 9 + ( 3 - 1) * 3 + 10 / 2”这个表达式,转换成后缀表达式应该变为 “ 9 3 1 - 3 * + 10 2 / + ”。 叫做后缀的原因就是所有的符号都在被运算的数字后面出现。
2,我们先来看看后缀表达式是如何计算的
规则: 从左到右遍历表达式的每个数字和符号,遇到数字就进栈,遇到符号,就把数字栈栈顶的两个数字出栈,栈顶元素放在运算符后面,栈顶下面一个元素放在运算符前面。再将运算结果进栈,如此往复,直到获得最终结果。
步骤精解:我们以上面的 “ 9 3 1 - 3 * + 10 2 / + ” 为例
(1)初始化一个空栈,用来对要运算的数字进行进出使用
(2)后缀表达式中前三个都是数字,所以将9 3 1 依次进栈。
(3)接下来是运算符“ - ”,所以将1, 3 出栈,运算3 - 1得到2 ,将2进栈,然后遇到3 ,将3进栈
(4)后面遇到“ * ”,将3, 2出栈,计算2 * 3,得到6,将6进栈
(5)遇到“ + ”,将6 , 9出栈,计算9 + 6,得到15,将15进栈
(6)将10, 2 进栈
(7)遇到符号“ / ” 将2, 10出栈,计算10/2得到5,将5压栈
(8)最后一个符号 “ + ”,将15,5出栈,计算15 + 5,得到20,将20压栈
(9)表达式读取完成,将结果20出栈,栈变为空。
这就是通过后缀表达式计算四则运算的结果。那么下面我们再来讨论如何将中缀表达式(也就是我们平时数学课上计算的形式)转换为方便计算机运算的后缀表达式呢?
3,中缀转后缀
规则:从左到右遍历中缀表达式,如果是数字就存入后缀表达式,如果是符号就判断其与栈顶符号的优先级,如果优先级不高于栈顶符号,则栈顶元素依次出栈并输出,并将当前符号进栈。特殊的,遇到左括号就进栈,左括号的优先级不做判断;当遇到右括号时,将与其匹配的左括号以上的全部符号依次出栈。直到最终输出后缀表达式为止。
具体步骤:我们还是以上面的 “ 9 + ( 3 - 1) * 3 + 10 / 2”这个表达式为例
(1)初始化一个空栈。遇到第一个字符是数字9,输出9,遇到符号“ + ”,进栈。
(2)遇到字符“ ( ”进栈,然后遇到了数字3,输出,又遇到了符号“ - ”,进栈。如下图
(3)遇到符号“ ) ”,根据规则,匹配前面的“ ( ”,并将其上的符号依次出栈并输出,直到“ ( ”出栈。
(4)下面遇到了符号“ * ”,比较其与栈顶元素 “ + ”的优先级。* 的优先级更高,所以压栈。 后面遇到了数字3 ,输出。
(5)之后遇到了符号 “ + ”,与栈顶元素“ * ”比较, + 的优先级低,所以将 * 弹栈,再与现在的栈顶 + 比较,与新来的 + 优先级相同,所以将栈顶+也出栈,将新来的 + 弹栈。如下图
(6)紧接着数字10,输出,后面是符号“ / ”,进栈。 最后一个数字2 输出。原表达式读取完成,将栈内剩余的符号都出栈,得到
4,实现逆波兰四则运算(静态方法调用)
package Stack; import java.util.Stack; import java.util.regex.Pattern; public class RPNmethod { private static Stack<String> charStack = new Stack<>(); private static Stack<Integer> intStack = new Stack<>(); public static int RPN(String exp){ String behindEXP = convert(exp); String[] chars = behindEXP.split(" "); for (int i = 0; i < chars.length; i++){ String thisOne = chars[i]; if (isNum(thisOne)){ intStack.push(Integer.parseInt(thisOne)); }else if (isSymbol(thisOne)){ int a = intStack.pop(); int b = intStack.pop(); int result; switch (thisOne){ case "+": result = b + a; intStack.push(result); break; case "-": result = b - a; intStack.push(result); break; case "*": result = b * a; intStack.push(result); break; case "/": result = b / a; intStack.push(result); break; } } } return intStack.pop(); } /** * 将中缀表达式转为后缀表达式 * @param middle * @return */ private static String convert(String middle){ String rpnEXP = ""; String[] chars = middle.split(" "); for(int i = 0; i < chars.length; i++){ String thisOne = chars[i]; if (isNum(thisOne)){ rpnEXP = rpnEXP + thisOne + " "; }else if (isSymbol(thisOne)) { /* 三个分支 : 是左括号,是右括号,不是括号 */ if (isLeftPar(thisOne)) { charStack.push(thisOne); } else if (isRightPar(thisOne)) {//Here while (!isLeftPar(thisOne)) { thisOne = charStack.pop(); if (!isLeftPar(thisOne)) { rpnEXP = rpnEXP + thisOne + " "; } } } else { if (charStack.isEmpty() || !lowerPriority(thisOne, charStack.peek())) { charStack.push(thisOne); } else { do { rpnEXP = rpnEXP + charStack.pop() + " "; } while (!charStack.isEmpty() && lowerPriority(thisOne, charStack.peek())); charStack.push(thisOne); } } } } while(!charStack.isEmpty()){ rpnEXP = rpnEXP + charStack.pop() + " "; } return rpnEXP; } private static boolean isLeftPar(String aChar) { return aChar.equals("("); } /** * 返回新来的优先级是不是不大于栈顶.aChar > peek 就返回false,peek >= aChar 就返回true * @param aChar * @param peek * @return 返回true就弹栈,返回false就将新来的压栈 */ private static boolean lowerPriority(String aChar, String peek) { if(peek.equals("(")){ return false; } else if (aChar.equals("+") || aChar.equals("-")){ return true; }else { if (peek.equals("*") || peek.equals("/")){ return true; }else { return false; } } } private static boolean isRightPar(String c) { return c.equals(")"); } private static boolean isNum(String c){ Pattern pattern = Pattern.compile("[\\d]*$"); return pattern.matcher(c).matches(); } private static boolean isSymbol(String c){ String pattern = "[-/*+()]"; return Pattern.matches(pattern,c) ; } }