写在前面
这一篇我们来学习栈,栈也是非常重要的数据结构,需要好好理解和掌握。
栈初识
栈是一种线性结构,相比与数组,栈对应的操作是数组的子集。不过栈只能从一端添加元素,也只能从一端取出元素(这一端称之为栈顶)。你可以把栈理解为我们常见的竖状容器:
记住添加元素和取出元素都只能从栈顶位置开始存取。从图中你也知道栈是一种后进先出的数据结构(先进来的在底部,后面的最先出去)。因此后进先出英文就是Last ln First Out (LIFO)。
栈的应用
你在使用office办公软件的时候,经常会使用撤销操作,Undo操作(撤销)是无处不在的。
假设你需要在word里面打一行字: "沉迷学习无法自拔",然后你一不小心将"无法"打成"不法",然后你就要使用ctrl+Z或者撤销操作,这样"不法"就从栈里面给压出来了,然后你再去写入"无法自拔",这样句子就写完了。如果你想写"沉迷OSC,无法自拔",你就要多次执行撤销操作,最后写入"沉迷OSC,无法自拔"即可。
另一个例子是程序调用的系统栈(这个例子对于理解递归有很大的作用)
我们来看这张图片,这里模拟计算机中程序的调用系统栈:
现在我们开始启动程序:当函数A运行到函数B的时候,会去调用函数B; 而函数B运行到函数C的时候,会去调用函数C;而函数C运行到函数3的时候继续往后走。。。
但是这样调用顺序计算机必须要记录下来的,这里就是使用系统栈来完成这个目的的,A2代表运行到A函数第二行,B2代表运行到B函数第二行,然后有了这个系统栈,等到最后程序运行完了以后,就会依次使用出栈的方式开始往前执行程序,最后返回执行A函数,等到A函数执行完发现栈里面是空的,那么整个程序就真的执行完毕了。下面我们使用代码来模拟栈。
栈
关于栈,它是一种非常简单的数据结构,而且里面提供的方法也是有限的,一般是这5种方式:
Stack<E> void push(E e); // 向栈中添加元素 E pop(); // 弹出栈顶元素 E peek( ); // 查看栈顶元素 int getSize(); // 获取栈中元素个数 boolean isEmpty(); // 判断栈是否为空
这个就不存在直接删除某个元素的操作了,只能依次通过删除栈顶的元素来慢慢实现删除该元素的目的。
其实从用户的角度来说,只要能支持这些操作就行。至于具体的底层实现,用户是不关心的,因为它实际上底层有多种实现方式。
这里我们就把栈定义为一个接口,然后只要能实现这个接口就可以,这也就是我们前面所说的用户只需要具有这些功能即可的目的。在test包下面新建一个Stack包,然后在里面新建一个接口Stack.java文件,里面的代码如下:
Interface Stack<E> implement ArrayStack<E> int getSize(); boolean isEmpty(); void push(E e); E pop(); E peek();
我们复制之前创建的数组ArrayElement.java文件,因为我们即将实现的ArrayElementStack会用到它。注意前面的addList()方法就是addLast()方法,我打错了,你们记得修改过来哈
前面说过,我们的peek方法是查看栈顶的元素,因此我们需要在ArrayElement.java文件里面新增两个方法,用于获取数组首位和末尾的元素:
/** * 获取开头位置的元素 * * **/ public E getFirst(){ return get(0); } /** * 获取末尾位置的元素 * * @return 末尾位置的元素 * **/ public E getLast(){ return get(size-1); //这里不可以使用data[size-1],因为假设size==0就会出现不合法的索引号。 }
最后打开Stack包,然后在里面新建ArrayElementStack.java文件,这里我就附上完整的ArrayElementStack文件代码:
package com.suanfa.test.Stack; import com.suanfa.test.Array.ArrayElement; //自己定义的数组栈 public class ArrayElementStack<E> implements Stack<E> { //定义一个数组 ArrayElement<E> arrayElement; public ArrayElementStack(){ arrayElement =new ArrayElement<>(); } public ArrayElementStack(int capaciy){ arrayElement =new ArrayElement<>(capaciy); } //实现stack接口中的方法 //实现stack接口中的getSize方法 @Override public int getSize(){ return arrayElement.getSize(); } /** * 实现stack接口中的isEmpty方法 * * @return */ @Override public boolean isEmpty(){ return arrayElement.isEmpty(); } /** * 实现stack接口中的push方法 * * @param e 待添加的元素 * @return */ @Override public void push(E e){ arrayElement.addLast(e); } /** * 实现stack接口中的pop方法 * * @return 栈顶刚删除的元素 */ @Override public E pop(){ return arrayElement.removeLast(); } /** * 实现stack接口中的Peek方法 * * @return 查看栈顶的元素 */ @Override public E peek(){ return arrayElement.getLast(); } /** * * @return 查看栈的容量 */ public int getCapacity(){ return arrayElement.getCapacity(); } /** * * @return 输出栈的元素 */ public String toString(){ //使用StringBuilder;来创建新的字符串对象 StringBuilder res =new StringBuilder(); res.append("Stack"); res.append("["); for(int i=0;i<arrayElement.getSize();i++){ res.append(arrayElement.get(i)); //判断是否是最后一个元素,从而是否需要在后面添加逗号 if(i != arrayElement.getSize()-1){ res.append(","); } } res.append("]top"); return res.toString(); } }
现在你可能要说,我们无法查看和插入元素到栈里面,我前面也说了,栈这种数据结构比较特殊,是无法进行选择插入和查看其它元素的(除了栈顶元素),当然你硬是要这样也是可以的,自己定义方法呗,就是感觉逻辑上说不过去而已。
现在我们来新建一个测试文件ArrayElementStackTest.java文件,里面写入以下代码:
package com.suanfa.test.Stack; public class ArrayElementStackTest { public static void main(String [] args){ ArrayElementStack<Integer> stack =new ArrayElementStack<>(); for(int i=0;i<5;i++){ stack.push(i); System.out.println(stack); } System.out.println("*******************************************"); stack.pop(); System.out.println(stack); } } //运行结果 Stack[0]top Stack[0,1]top Stack[0,1,2]top Stack[0,1,2,3]top Stack[0,1,2,3,4]top ******************************************* Stack[0,1,2,3]top
栈的时间复杂度分析
ArrayStack<E> void push(E e) // O(1) 均摊(触发resize也是O(1)) E pop() // O(1) 均摊 (触发resize也是O(1)) E peek() // O(1) int getSize() // O(1) boolean isEmpty() // O(1)
注意这里面的push和pop操作,尽管都是在末尾进行,但是有可能触发resize。一旦触发resize,但均摊来算还是O(1)。
栈的应用(续)
在前面的栈的应用介绍里,我们介绍了编辑器undo操作(撤销)和操作系统中的系统调用栈这两个例子,但是都是简单的介绍并没有用代码去实现一个例子。下面要举的这个例子,就是需要用代码来实现的。
通常我们在用IDE进行开发的时候,如果你忘记对括号进行闭合,IDE是会给你报错提示的,那么这个对括号匹配,IDE是如何实现的呢?下面就通过用代码来模拟实现一下。其实这也是leetCode的第二十道题,题目是这样的:
给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:
输入: "()"
输出: true
示例 2:
输入: "()[]{}"
输出: true
示例 3:
输入: "(]"
输出: false
示例 4:
输入: "([)]"
输出: false
这个题目是什么意思呢?举个例子:{ [ ( ) ] }首先将左侧符号(其实是指 { [ ()压入栈,然后在开始进行匹配右侧符号的时候,将该符号与栈顶元素进行匹配,如果一样就出栈,继续前面的操作,直到所有字符扫描完毕,栈为空则表明匹配成功。否则,一旦出现栈顶元素与该匹配字符不合,就立即判断该符号匹配不正确。
也就是说栈顶元素反映了在嵌套的层次关系中,最近的需要匹配的元素。
最后的运行代码如下:
import java.util.Stack; class Solution { public boolean isValid(String s) { Stack<Character> stack =new Stack<>(); for(int i =0;i<s.length();i++){ char c =s.charAt(i); if(c == '['|| c == '(' || c == '{'){ stack.push(c); }else{ if(stack.isEmpty()){ return false; } char charTop =stack.pop(); if(c ==']'&&charTop !='['){ return false; } if(c ==')'&&charTop !='('){ return false; } if(c =='}'&&charTop !='{'){ return false; } } } return stack.isEmpty(); } }
上面我们使用的是Java提供给我们的Stack,后面我们会使用到自己编写的Stack来完成这个功能。注意上面charTop中的pop操作,它完成了取出栈顶元素和保存栈顶元素这两个功能。
关于LeetCode的更多说明,首先你肯定好奇为什么我们在前面不需要添加main方法,而LeetCode就能运行呢?那是因为LeetCode会自动创建该类的一个main方法,请注意该方法必须是public修饰,因为它会在该类的外部创建自己的Main来调用执行该类中你定义的方法。
当然,你在提交的时候即使添加了main方法,系统也不会报错的,因为不会执行它。但是请注意不要将自己Package的语句也加入到里面,这个是会报错的。LeetCode只允许你提交一个类,多的则不可以。那么你就可以把其他类当做该类的内部类就能达到这个目的。
你也看到了LeetCode上面关于栈这一块有39个问题,但是我们不是说你现在学到了栈这个数据结构,就要把那39道题目全部都做完了,才能继续学习下一个数据结构,这是不正确的。你不要有完美主义的思想,有时候能做就做,不做就放弃吧,等到后面再来看的时候就发现原来这么简单呐,反正我是经常有这种情况的。所以,有时候完美主义不但没有帮助你学会某个东西,而是相反却成了你成功路上的绊脚石。