北京建设执业网站,网站设计师的工作环境,绍兴seo淄博公司,青岛seo网站排名1. 栈的概述#xff1a;
1.1 生活中的栈
存储货物或供旅客住宿的地方#xff0c;可引申为仓库、中转站。例如酒店#xff0c;在古时候叫客栈#xff0c;是供旅客休息的地方#xff0c;旅客可以进客栈休息#xff0c;休息完毕后就离开客栈
1.2计算机中的栈
将生活中的…1. 栈的概述
1.1 生活中的栈
存储货物或供旅客住宿的地方可引申为仓库、中转站。例如酒店在古时候叫客栈是供旅客休息的地方旅客可以进客栈休息休息完毕后就离开客栈
1.2计算机中的栈
将生活中的栈的概念引入到计算机汇总就是供数据休息的地方它是一种数据结构数据既可以进入到栈中又可以从栈中出去。栈是一种基于先进后出FILO的数据结构是一种只能在一端进行插入和删除操作的特殊线性表。 它按照先进后出的原则存储数据先进入的数据被压入栈底最后的数据在栈顶需要读数据的时候从栈顶开始弹出数据最后一个数据被第一个读出来 我们称数据进入到栈的动作为压栈数据从栈中出去的动作为弹栈 2. 栈的实现
2.1 栈API设计
类名Stack构造方法Stack()创建Stack对象成员方法1. public boolean isEmpty()判断栈是否为空是返回true否返回false2. public int size()获取栈中元素的个数3. public T pop()弹出栈元素4. public void push(T t)向栈中压入元素t成员变量1. private Node head记录首节点2. private int N当前栈的元素个数成员内部类private class Node节点类
2.2 代码实现
package com.renexdemo.linear;import java.util.Iterator;public class StackT implements IterableT {private Node head;private int N;// 节点类private static class NodeT{public T item;// 存储元素public Node next;// 指向下一个节点public Node(T item, Node next) {this.item item;this.next next;}}// 初始化栈public Stack() {this.head new Node(null,null);this.N 0;}// 判断栈是否为空public boolean isEmpty(){return N 0;}// 获得栈中的数量public int size(){return N;}// 压栈public void push(T t){// 找到首节点指向的第一个节点Node oldNode head.next;// 创建新节点NodeT newNode new Node(t, null);// 让首节点指向新节点head.next newNode;// 让新节点指向原来的第一个节点newNode.next oldNode;// 元素个数1N;}// 弹栈public T pop(){// 找到首节点指向的第一个节点Node oldFirst head.next;if (oldFirst null){return null;}// 让首节点指向原来第一个节点的下一个节点head.nextoldFirst.next;// 元素个数-1N--;return (T) oldFirst.item;}Overridepublic IteratorT iterator() {return new SIterator();}private class SIterator implements Iterator{private Node n;public SIterator() {this.n head;}Overridepublic boolean hasNext() {return n.next ! null;}Overridepublic Object next() {n n.next;return n.item;}}
}3. 案例
3.1 括号匹配问题
问题描述
给定一个字符串里边可能包含()小括号和其他字符请编写程序检查该字符串中的小括号是否成对出现
例如
(上海)(长安)正确匹配;
上海((长安))正确匹配;
上海(长安(北京)(深圳)南京)正确匹配;
上海(长安))错误匹配;
(上海(长安)错误匹配;代码实现
// 判断str中的括号是否匹配
public static boolean isMatch(String str){// 1. 创建栈对象用来存储左括号StackString chars new Stack();// 2. 从左往右遍历字符串for (int i 0; i str.length(); i) {String currChar str.charAt(i) ;// 3. 判断当前字符是否为左括号如果是则把字符放入到栈中if (currChar.equals(()){chars.push(currChar);}else if (currChar.equals())){// 4. 继续判断当前字符是否是有括号// 如果是则从栈中弹出一个左括号并判断弹出的结果是否为null// 如果为null证明没有匹配的左括号如果不为null则存在匹配的左括号String pop chars.pop();if (pop null){return false;}}}// 5. 判断栈中还有没有剩余的左括号如果有则证明括号不匹配if (chars.size() 0){return true;}else {return false;}
}3.2 逆波兰表达式求值问题
3.2.1 中缀表达式
中缀表达式就是我们平常生活中使用的表达式例如13*2,2,2-(13)等等中缀表达式的特点是二元运算符总是置于两个操作数中间。
中缀表达式是人们最喜欢的表达式方式因为简单、易懂。但是对于计算机来说就不是这样了因为中缀表达式的运算顺序不具有规律性不同的运算符具有不同的优先级如果计算机执行中缀表达式需要解析表达式语义做大量的优先级相关操作
3.2.2 逆波兰表达式后缀表达式
逆波兰表达式是 波兰逻辑学家j · 卢卡西维兹J · Lukasewicz 于1929年首先提出的一种表达式的表示方法后缀表达式的特点运算符总是放在跟它相关的操作数之后
中缀表达式逆波兰表达式ababa(b-c)abc-a(b-c)*dabc-d*a*(b-c)dabc-*d
3.2.3 需求
给定一个只包含加减乘除四种运算的逆波兰表达式的数组表示方式求出该逆波兰表达式的结果 3.2.4 实现代码
// 执行逆波兰表达式
public static int caculote(String[] notaion){// 1. 定义一个栈用来存储操作数StackInteger oprands new Stack();// 2. 从左往右遍历逆波兰表达式得到每一个元素for (int i 0; i notaion.length; i) {String curr notaion[i];Integer o1,o2,result;// 3. 判断当前元素是运算符还是操作数switch (curr){// 4. 运算符从栈中弹出两个操作数完成运算运算玩的结果压入到栈中case :o1 oprands.pop();o2 oprands.pop();result o2 o1;oprands.push(result);break;case -:o1 oprands.pop();o2 oprands.pop();result o2 - o1;oprands.push(result);break;case *:o1 oprands.pop();o2 oprands.pop();result o2 * o1;oprands.push(result);break;case /:o1 oprands.pop();o2 oprands.pop();result o2 / o1;oprands.push(result);break;default:// 5. 操作数把该操作数放入到栈中oprands.push(Integer.parseInt(curr));break;}}// 6. 得到栈中最后一个元素就是逆波兰表达式的结果int reulst oprands.pop();return reulst;
}3.2.4.1 逻辑问题
当做进行运算符计算时由于栈是先进后出类型。
所以弹出两个元素不能是第一个弹出的元素对第二个元素进行运算。
例如{17,16} 17先压栈然后16 那么在弹栈后16为第一个元素17为第二个元素当作 / 或 - 运算时就不符合本身的运算逻辑了 意思是原来操作逻辑是17-16那么经过弹栈后两者互调了位置变成了16-17。这两个结果是截然不同的
4. 总结
常见常用的数据结构同样也比较好实现可以在许多的业务场景中见到类似的模式分析这种结构后可以提高一定的见解。
