首先,栈是什么?
在代码当中,栈主要是一种实现特殊功能的一种数据结构,而不是像数组、集合之类的数据存储工具。它最大的特点就是后进先出。
那么后进先出是什么?
假设有一个数组,我们向里面添加一个数据,再添加一个。这里有两个术语,新添加的数据叫做栈顶,而第一个添加的数据叫做栈底。每次读取数据都是读取栈顶的数据,而栈底的数据在最后才能被读取。此时我们读出一个数据,那么只能读出栈顶的数据,就是2。这,就是后进先出。
现在我们已经了解了栈,接下来我们来看一个小问题。
通常我们使用开发工具编写代码时,如果少写了一对括号中的一个,那么开发工具就会马上告诉我们,出现了语法错误。
下面我们模拟并实现一下这个功能。
Map<String, int[]> demo = new HashMap<String, int]>();
大家看这段代码,这里少了一个中括号。如果在没有了解栈之前,我们可能会先读取出这行代码中所有的左括号,再读取出所有的右括号,最后判断他们的数量是否相同。这样做是可以的,但是有很大的限制,比如说,我们将括号的位置换一下,将中括号加在这里,那么我们刚才的逻辑就不能够有效的工作了。
这时,我们就可以用刚才讲的栈,来完成这个任务。
这个功能看起来需要不少的逻辑代码才能实现,但用栈来实现的话,却简单的令人不可思议。我们只需要从这段代码的左侧逐个读取字符,如果是左括号,则将它压入栈中,比如现在读取到了这里发现是左括号,就添加到数组中。
如果是右括号,就将最后添加的左括号取出并判断它们是否是一对,比如读取到了这里发现是右括号,那么现在数组中保存的是<[,我们只要将最后添加的这个括号取出并和读取到的右括号进行比较。
如果是一对,则将栈顶数据删除,新的栈顶是前一个添加的左括号<,程序继续运行。如果不是一对或栈为空则退出程序。但当读取完字符串之后,我们最后还要判断一下数组是否为空。因为左括号可能出现在最后,此时没有右括号和它进行配对。
比如这样,只是将它压入到栈中,但没有右括号来和它进行比较。程序还是会正常退出。这时我们就需要判断一下,如果数组为空,则判定这段代码没有语法错误。否则这段代码有语法错误。
当然从右边开始读取也是可以的,只是反过来实现而已。