程序员,你应该知道的数据结构之栈
数据结构中的栈不要与 Java 中的栈混淆,他们俩不是一回事,数据结构中的栈是一种受限制的线性表,栈具有先进后出、后进先出的特点,因为栈只允许访问最后一个数据项,即最后插入的数据项。也许你会有疑问,栈既然有这么多限制,为什么不用数组或者链表而使用栈?在开发中,我们有特定的场景,根据特定的场景去选用数据结构,栈的适用场景非常多,比如浏览器的前进与后退、字符串括号的合法性等,我们使用栈来实现就比较好,因为栈相对数组、链表来说对外提供的接口要少很多,接口少了,出错的概率就减少了,对风险的可控性就提高了。
实现一个栈
从栈的定义中可以看出,栈主要有两个操作,一个是新增一条数据,我们叫做入栈,另一个是获取一条数据,称为出栈,下面两张图是入栈出栈示意图。
栈的实现有两种方式,一种是基于数组实现的,我们叫作顺序栈,另一种是基于链表实现的,我们叫作链式栈。下面是两种栈的实现代码
基于数组的顺序栈
/** * 基于数组的顺序栈 */ public class ArrayStack { // 栈最大容量 private int maxSzie; // 存放内容 private String[] array; // 栈顶元素 private int top; public ArrayStack(int size){ this.maxSzie = size; this.array = new String[this.maxSzie]; this.top = 0; } /** * 入栈操作 * * @param data 数据 * @return 0:入栈失败 1:入栈成功 */ public int push(String data) { if (top == maxSzie) return 0; array[top] = data; top++; return 1; } /** * 出栈操作 * * @return */ public String pop() { if (top == 0) return null; return array[--top]; } /** * 获取栈顶元素 * * @return */ public String peek() { return array[top - 1]; } /** * 判断栈是否为空 * @return */ public boolean isEmpty() { return top == 0; } }
基于链表的链式栈
/** * 基于链表的链式栈 */ public class LinkStack { // 始终指向栈的第一个元素 private Node top = null; /** * 压栈 * * @param data * @return */ public int push(String data) { Node node = new Node(data); if (top == null) { top = node; } else { node.next = top; top = node; } return 1; } /** * 出栈 * * @return */ public String pop() { if (top == null) return null; String data = top.getData(); top = top.next; return data; } /** * 节点信息 */ private static class Node { private String data; private Node next; public Node(String data) { this.data = data; this.next = null; } public String getData() { return this.data; } } }
栈的实现比较简单,因为栈涉及的操作不多,主要就入栈和出栈两个操作。
栈的应用
检测字符串括号的合法性
我们有时候需要检测字符串括号的合法性,即一个左括号需要匹配一个右括号,这个我们可以使用栈来实现。我们可以从一个合法的括号来理解为什么使用栈?如果括号使用合法,最后一个左括号跟第一个右括号是匹配的,倒数第二个左括号和第二个右括号匹配的,以此类推,这符合我们栈的特性先进后出。
假设我们有三种括号:圆括号 ()、方括号 [] 和花括号{},我们使用栈来检测括号的合法性。我们将左括号全部压栈,当出现右括号时,我们就进行匹配,这时候有如下三种情况:
- 栈为空,说明没有左括号,括号使用不合法
- 栈中取出来的左括号跟右括号不匹配,括号使用不合法
- 栈中取出的左括号跟右括号匹配,括号使用暂时合法
当整个字符串都扫描完成后,检测栈中是否还有值,如果栈为空,则说明括号使用合法,反正,则括号使用不合法。
实现代码
public static boolean BracketChecker(String data) { char[] chars = data.toCharArray(); ArrayStack stack = new ArrayStack(chars.length); for (char ch : chars) { switch (ch){ case '{': case '[': case '(': stack.push(ch); break; case '}': case ']': case ')': if (!stack.isEmpty()){ char ch1 = stack.pop(); if ((ch=='}' && ch1 !='{') ||(ch==']' && ch1 !='[') ||(ch==')' && ch1 !='(') ){ return false; } }else { return false; } break; default: break; } } return stack.isEmpty(); }
浏览器前进、后退功能
我们使用浏览器都知道,浏览器可以前进、后退功能,浏览器的前进后退也符合栈的特点,我们最先访问的网页肯定要最后才能倒回去。我们一起来看看栈怎么实现这个功能?
我们需要定义两个栈,我们将首次访问的页面压栈到第一个栈中,当点击后退时,从第一个栈中取出数据放入到第二个栈,当点击前进按钮时,从第二个栈取出数据放入第一个栈。当第一个栈没有数据时,说明没有页面可以点击后退了,当第二个栈没有数据时,说明没有页面可以点击前进了。这样我们就通过栈实现了浏览器前进、后退功能。
最后
打个小广告,平头哥给大家整理了一份较全面的 Java 学习资料,欢迎扫码关注微信公众号:「平头哥的技术博文」领取,一起学习进步吧。