栈与队列
我们一般把栈与队列合在一块讨论,因为他们具有相似的性质。
栈:栈是限定仅在表尾进行插入和删除操作的线性表,所以栈又称为后进先出(LastIn First Out)
的线性表,简称LIFO结构。
队列:只允许在一端进行插入操作、而在另一端进行删除操作的线性表,队列又称为先进先出(First In First Out)
的线性表,简称FIFO结构。
栈
生活中的栈
存储货物或供旅客住宿的地方,可引申为仓库、中转站 。例如我们现在生活中的酒店,在古时候叫客栈,是供旅客休息的地方,旅客可以进客栈休息,休息完毕后就离开客栈。
计算机中的栈
我们把生活中的栈的概念引入到计算机中,就是供数据休息的地方,它是一种数据结构,数据既可以进入到栈中,又可以从栈中出去。
栈是一种基于先进后出(FILO
)的数据结构,是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据(最后一个数据被第一个读出来)。
我们称数据进入到栈的动作为压栈,数据从栈中出去的动作为弹栈。
栈的设计
类名 | Stack |
---|---|
构造方法 | Stack() :创建Stack对象 |
成员方法 | public boolean isEmpty() :判断栈是否为空,是返回true,否返回falsepublic int size() :获取栈中元素的个数public T pop() :弹出栈顶元素public void push(E e) :向栈中压入元素e |
成员变量 | private Node head :记录首结点private int n :当前栈的元素个数 |
我们一般用链表来实现栈。
栈的代码实现
public class Stack<E> implements Iterable<E> {/*** 头结点*/private final Node<E> head;/*** 元素个数*/private int count;public Stack() {this.head = new Node<>();this.count = 0;}/*** 插入元素e为新的栈顶元素*/public void push(E e) {// 把当前的栈顶元素赋值给新结点的直接后继var oldNext = head.next;head.next = new Node<>(e, oldNext);this.count++;}/*** 出栈* <p>* 若栈不空,则删除S的栈顶元素,用e返回其值,并返回OK;否则返回ERROR*/public E pop() {var oldNext = head.next;if (oldNext == null) {return null;}// 删除首个元素head.next = head.next.next;count--;return oldNext.item;}/*** 判断栈是否为空,是返回true,否返回false*/public boolean isEmpty() {return count == 0;}/*** 获取栈中元素的个数*/public int size() {return count;}@Overridepublic Iterator<E> iterator() {return new SIterator();}private class SIterator implements Iterator<E> {private Node<E> n = head;@Overridepublic boolean hasNext() {return n.next != null;}@Overridepublic E next() {var node = n.next;n = n.next;return node.item;}}@NoArgsConstructor@AllArgsConstructorprivate static class Node<E> {/*** 存储元素*/private E item;/*** 指向下一个节点*/private Node<E> next;}
}
栈的应用
括号匹配问题
给定一个字符串,里边可能包含"()"小括号和其他字符,请编写程序检查该字符串的中的小括号是否成对出现。
例如:
- “(上海)(长安)”:正确匹配
- “上海((长安))”:正确匹配
- “上海(长安(北京)(深圳)南京)”:正确匹配
- “上海(长安))”:错误匹配
- “((上海)长安”:错误匹配
public class BracketsMatch {public static void main(String[] args) {String str = "(上海(长安)())";boolean match = isMatch(str);System.out.println(str + "中的括号是否匹配:" + match);}/*** 判断str中的括号是否匹配** @param str 括号组成的字符串* @return 如果匹配,返回true,如果不匹配,返回false*/public static boolean isMatch(String str) {return false;}
}
请完善isMatch
方法
我们用栈来分析解决方案:
- 创建一个栈用来存储左括号
- 从左往右遍历字符串,拿到每一个字符
- 判断该字符是不是左括号,如果是,放入栈中存储
- 判断该字符是不是右括号,如果不是,继续下一次循环
- 如果该字符是右括号,则从栈中弹出一个元素t;
- 判断元素t是否为null,如果不是,则证明有对应的左括号,如果不是,则证明没有对应的左括号
- 循环结束后,判断栈中还有没有剩余的左括号,如果有,则不匹配,如果没有,则匹配
代码实现
public class BracketsMatch {private static final char LEFT_PARENTHESIS = '(';private static final char RIGIT_PARENTHESIS = ')';/*** 判断str中的括号是否匹配** @param str 括号组成的字符串* @return 如果匹配,返回true,如果不匹配,返回false*/public static boolean isMatch(String str) {var stack = new Stack<Character>();for (int i = 0; i < str.length(); i++) {var c = str.charAt(i);if (LEFT_PARENTHESIS == c) {stack.push(c);} else if (RIGIT_PARENTHESIS == c) {// 弹出一个元素,如果是NULL,那么证明没有对应的左括号if (stack.pop() == null) {return false;}}}return stack.isEmpty();}}
逆波兰(后缀)表达式求值
逆波兰表达式求值问题是我们计算机中经常遇到的一类问题,要研究明白这个问题,首先我们得搞清楚什么是逆波兰表达式?要搞清楚逆波兰表达式,我们得从中缀表达式说起。
中缀表达式
中缀表达式就是我们平常生活中使用的表达式,例如:1 + 3 * 2
,2 - (1 + 3)
等等,中缀表达式的特点是:二元运算符总是置于两个操作数中间。
中缀表达式是人们最喜欢的表达式方式,因为简单,易懂。但是对于计算机来说就不是这样了,因为中缀表达式的运算顺序不具有规律性。不同的运算符具有不同的优先级,如果计算机执行中缀表达式,需要解析表达式语义,做大量的优先级相关操作。
逆波兰(后缀)表达式
逆波兰表达式是波兰逻辑学家J・卢卡西维兹(J・ Lukasewicz)于1929年首先提出的一种表达式的表示方法,后缀表达式的特点:运算符总是放在跟它相关的操作数之后。
中缀表达式 | 逆波兰表达式 |
---|---|
a+b | ab+ |
a+(b-c) | abc-+ |
a+(b-c)*d | abc-d*+ |
a*(b-c)+d | abc-*d+ |
需求
给定一个只包含加减乘除四种运算的逆波兰表达式的数组表示方式,求出该逆波兰表达式的结果。
public class ReversePolishNotation {public static void main(String[] args) {//中缀表达式3*(17-15)+18/6的逆波兰表达式如下String[] notation = {"3", "17", "15", "-", "*", "18", "6", "/", "+"};int result = caculate(notation);System.out.println("逆波兰表达式的结果为:" + result);}/*** @param notaion 逆波兰表达式的数组表示方式* @return 逆波兰表达式的计算结果*/public static int caculate(String[] notaion) {return -1;}
}
完善caculate
方法,计算出逆波兰表达式的结果。
我们用栈来分析解决方案:
- 创建一个栈对象
oprands
存储操作数 - 从左往右遍历逆波兰表达式,得到每一个字符串
- 判断该字符串是不是运算符,如果不是,把该该操作数压入
oprands
栈中 - 如果是运算符,则从
oprands
栈中弹出两个操作数o1,o2 - 使用该运算符计算o1和o2,得到结果
result
- 把该结果压入
oprands
栈中 - 遍历结束后,拿出栈中最终的结果返回
代码实现
public class ReversePolishNotation {/*** @param notaion 逆波兰表达式的数组表示方式* @return 逆波兰表达式的计算结果*/public static int caculate(String[] notaion) {var oprands = new Stack<Double>();for (var s : notaion) {switch (s) {case "+": {var o1 = oprands.pop();var o2 = oprands.pop();oprands.push(o2 + o1);}break;case "-": {var o1 = oprands.pop();var o2 = oprands.pop();oprands.push(o2 - o1);}break;case "*": {var o1 = oprands.pop();var o2 = oprands.pop();oprands.push(o2 * o1);}break;case "/": {var o1 = oprands.pop();var o2 = oprands.pop();oprands.push(o2 / o1);}break;default:// 非运算符,那么入栈oprands.push(Double.parseDouble(s));}}return oprands.pop().intValue();}
}
队列
你们在用电脑时有没有经历过,机器有时会处于疑似死机的状态,鼠标点什么似乎都没用,双击任何快捷方式都不动弹。就当你失去耐心,打算reset时。突然它像酒醒了一样,把你刚才点击的所有操作全部都按顺序执行了一遍。这其实是因为操作系统中的多个程序因需要通过一个通道输出,而按先后次序排队等待造成的。
再比如像移动、联通、电信等客服电话,客服人员与客户相比总是少数,在所有的客服人员都占线的情况下,客户会被要求等待,直到有某个客服人员空下来,才能让最先等待的客户接通电话。这里也是将所有当前拨打客服电话的客户进行了排队处理。操作系统和客服系统中,都是应用了一种数据结构来实现刚才提到的先进先出的排队功能,这就是队列。
队列是一种先进先出(First In First Out)的线性表,简称FIFO。允许插入的一端称为队尾,允许删除的一端称为队头。
队列的设计
类名 | Queue |
---|---|
构造方法 | Queue() :创建Queue对象 |
成员方法 | public boolean isEmpty() :判断队列是否为空,是返回true,否返回falsepublic int size() :获取队列中元素的个数public E pop() :从队列中拿出一个元素public void push(E e) :往队列中插入一个元素 |
成员变量 | private Node head :记录首结点private int n :当前栈的元素个数private Node last :记录最后一个结点 |
队列的实现
public class Queue<E> {/*** 队头指针*/private final Node<E> head;/*** 队尾指针*/private Node<E> last;private int n;public Queue() {this.head = new Node<>();this.last = null;this.n = 0;}/*** 入队*/public void push(E e) {// 新节点var newNode = new Node<>(e, null);if (last == null) {last = newNode;head.next = last;} else {// 当前尾结点不为NULLvar oldLast = last;last = newNode;oldLast.next = last;}last.next = newNode;last = newNode;this.n++;}/*** 出队*/public E pop() {// 无元素if (head == last) {return null;}// 头结点不存储元素,所以移出的元素是头结点下一个元素var oldFirst = head.next;head.next = oldFirst.next;this.n--;if (isEmpty()) {last = null;}return oldFirst.item;}public boolean isEmpty() {return n == 0;}public int size() {return n;}@NoArgsConstructor@AllArgsConstructorprivate static class Node<E> {/*** 存储元素*/private E item;/*** 指向下一个节点*/private Node<E> next;}}