Java堆栈数据结构的问与答

Java的集合类库是最常用的类库之一。栈的后进先出机制可以在很多地方派上用场，比如，表达式预估/语法解析，验证和解析XML，还原文本编辑器的内容，web浏览器的页面访问记录等等。下面是一些关于栈的知识。

 

Q.Java中有什么后入先出的实现可以使用？

A.向量是栈的传统实现并且Java文档中规定使用Deque来代替是因为提供了更好的后进先出的操作支持。Deque的实现通常都比Stack的要好。J2SE5引入了Queue接口，并且加入了实现Queue接口的Deque。Deque接口应该被读作“deck”而不是“de-queue”，并且在从queue中移除元素也不会被认为是dequeue。双端队列支持从任何一端进行元素的增加和删除，因此它可以被用作队列（先进先出/FIFO）或者栈（后进先出LIFO）.

 

注意：在它之前的Vector向量类使用的是内部同步，在数据一致性上很差劲，不恰当的使用会让性能大打折扣。新引入的java.util.concurrent包提供了更有效的线程安全的实现。

 

Q.让你在指定的字符串里匹配开括号的对应的闭括号，应该怎么实现？

A.首先,把实现用伪代码写出来，然后按照伪代码实现

  1.将所有的圆括号存储在栈中。可以保证后进先出的顺序

  2.当遇到一个闭括号时，从栈中取出最后一个压入的元素，这就是对应的开括号

  3.如果没有匹配到，则不存在成对的括号

如果需要，下面这个图描述了这个逻辑。

 

 

 

下面是演示使用栈匹配括号对的例子，其中枚举数据定义了不同的括号类型

 

 

public enum PARENTHESIS {
 
 LP('('), RP(')'), LB('{'), RB('}'), LSB('['), RSB(']');
 
 char symbol;
 
 PARENTHESIS(Character symbol) {
  this.symbol = symbol;
 }
 
 char getSymbol() {
  return this.symbol;
 }
} 

 

 

 

现在，是栈的后进先出特性在开括号匹配闭括号的时候起了作用。如果匹配到左侧开括号就压入栈中，然后查找匹配的闭括号，如果匹配则把对应的开括号从栈中弹出。

 

 

import java.util.ArrayDeque;
import java.util.Deque;
 
public class Evaluate {
 
 //存储括号
 final Deque<character> paranthesesStack = new ArrayDeque<character>();
 
 public boolean isBalanced(String s) {
 
  for (int i = 0; i < s.length(); i++) {
 
   if (s.charAt(i) == PARENTHESIS.LP.getSymbol() || 
       s.charAt(i) == PARENTHESIS.LB.getSymbol() ||
       s.charAt(i) == PARENTHESIS.LSB.getSymbol())
     
     paranthesesStack.push(s.charAt(i));      //自动装箱
                                              // 把开括号压入栈中
 
   //对每一个闭括号都要检查是否在栈中有匹配的开括号
   else if (s.charAt(i) == PARENTHESIS.RP.getSymbol()){  
    if (paranthesesStack.isEmpty() || paranthesesStack.pop() != PARENTHESIS.LP.getSymbol())
     return false;
   }
 
   else if (s.charAt(i) == PARENTHESIS.RB.getSymbol() ) {
    if (paranthesesStack.isEmpty() || paranthesesStack.pop() !=PARENTHESIS.LB.getSymbol() )
     return false;
   }
 
   else if (s.charAt(i) == PARENTHESIS.RSB.getSymbol()) {
    if (paranthesesStack.isEmpty() || paranthesesStack.pop() != PARENTHESIS.LSB.getSymbol())
     return false;
   }
 
  }
   
  return paranthesesStack.isEmpty(); //如果栈中元素全部弹出，则括号全部匹配上
 }
 
}

 

 

 

注意：ArrayDeque不是线程安全的，也不允许保存为null的元素。并发包中有BlockingQueue和LinkedBlockingQueue两种实现。

 

最后，写一个简单的测试用例。需要将junit的jar包放入类路径中，这里使用的版本是4.8.2.

 

 

import junit.framework.Assert;
import org.junit.Before;
import org.junit.Test;
 
 
public class EvaluateTest {
  
 Evaluate eval = null;
  
 @Before
 public void setUp(){
  eval = new Evaluate();
 }
  
 @Test
 public void testPositiveIsBalanced(){
   boolean result = eval.isBalanced("public static void main(String[] args) {}");
      Assert.assertTrue(result);   
       
 }
  
  
 @Test
 public void testNegativeIsBalanced(){
   boolean result = eval.isBalanced("public static void main(String[ args) {}");   // missing ']'
      Assert.assertFalse(result);
       
      result = eval.isBalanced("public static void main(String[] args) }");          // missing '{'
      Assert.assertFalse(result);
       
       
      result = eval.isBalanced("public static void main String[] args) {}");        // missing '('
      Assert.assertFalse(result);
       
 }
 
}

 

 

 

提示：测试的时候用例要覆盖正负两个方向

 

注意：上面的例子演示了后进先出机制来实现括号成对的匹配。但是事实上的实现远没有如此适合。当需要很大一坨if-else判断或者switch语句的时候，就应该考虑一个面向对象的解决方案了。

 

Q.为什么Deque接口和其他集合接口不同？

A.对于Deque，可以在集合的两端随意的添加或者删除元素。而其他集合却只能在末尾一端进行插入和删除操作

 

Q.程序的执行可以用什么不同的方式来查询跟踪？

A.

  1.Java是基于栈实现的语言，程序的执行伴随着出栈和入栈。当进入一个方法时，会将程序和数据压入栈中，如果方法还要调用很多其他的方法，就会根据方法执行的顺序将数据压入栈中。当方法执行完成后，需要根据后进先出的原则将栈中的数据弹出，比如方法A调用方法B，然后方法B再调用方法C，那么当方法C执行完成后，C方法相关的会先弹出，然后是方法B的，最后才是方法A的。当有异常发生时，会生成方便跟踪异常发生点的堆栈信息并打印出来。

 

                                                  

 
 

 

  2.Java程序员随时都可以拿到堆栈信息。调用方式如下

 

 

Thread.currentThread().getStackTrace() ; //获取堆栈信息

 

 

 

可以使用Java工具箱中的jstack之类的工具来获取线程的堆栈信息，其他工具还有Jconsole，还或者在Win32平台上使用CTRL+BREAK组合键、在Posix操作系统上通过信号Kill -quit生成线程堆栈转储信息。你还可以使用下面代码的方式使用JMX API获取。ThreadMXBean是JVM线程子系统的管理接口。

 

ThreadMXBean bean = ManagementFactory.getThreadMXBean();
ThreadInfo[] infos = bean.dumpAllThreads(true, true);
for (ThreadInfo info : infos) {  
    StackTraceElement[] elems = info.getStackTrace();  
 //TODO
}

 

线程堆栈转出信息对于寻找比如死锁、资源争用、线程饥饿等并发问题很有用。

 

Q.Java中有递归的方法调用吗？

A.答案是确定的，Java是基于栈的并且是借助的后进先出的特性，它会记住调用者的位置，所以当方法返回的时候知道将结果返回到正确的地方。

 

Q.你怎么正确的分析堆栈跟踪信息？

A.

  1.堆栈信息需要正确理解的一个最重要的概念是它显示的是按照操作执行的时间排序的路径。也就是它的后进先出特性。

  2.下面是一段很简单的堆栈信息，它可以告诉你的是在代码类C的16行上发生了空指针异常。可以从最上面的类中看到。

 

Exception in thread "main" java.lang.NullPointerException
        at com.myapp.ClassC.methodC(ClassC.java:16)
        at com.myapp.ClassB.methodB(ClassB.java:25)
        at com.myapp.ClassA.main(ClassA.java:14)

 

3.包含多个“caused by”段的堆栈信息会显得更复杂，在当前例子中你可以从最底部的“caused by”看到最根本的原因，例如，

 

Exception in thread "main" java.lang.IllegalStateException: ClassC has a null property
        at com.myapp.ClassC.methodC(ClassC.java:16)
        at com.myapp.ClassB.methodB(ClassB.java:25)
        at com.myapp.ClassA.main(ClassA.java:14)
Caused by: com.myapp.MyAppValidationException
        at com.myapp.ClassB.methodB(ClassB.java:25)
        at com.myapp.ClassC.methodC(ClassC.java:16)
        ... 1 more
Caused by: java.lang.NullPointerException
        at com.myapp.ClassC.methodC(ClassC.java:16)
        ... 1 more

 

最根本的原因是由最后一个“caused by”也就是类C的第16行代码出抛出的空指针异常

 

4.当你使用过多的第三方类库比如Spring、Hibernate等等，显示在你面前的堆栈异常会有很多，这时你需要查看最底部的“caused by”段，那里是才是异常发生的地方。

 

Q.怎样反向输出数组{1,4,6,7,8,9}?

A.有很多方式可以实现。谈到LIFO，下面的例子演示了使用栈来实现的代码

 

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
 
 
public class ReverseNumbers {
 
 public static void main(String[] args) {
  Integer[] values = {1, 4, 6, 7, 8, 9};
  Deque<integer> numberStack = new ArrayDeque<integer>(10);
   
  for (int i = 0; i < values.length; i++) {
   numberStack.push(values[i]);                   // 按照给定的顺序压入栈中
  }
   
  Integer[] valuesReversed = new Integer[values.length];
   
  int i = 0;
  while (!numberStack.isEmpty()) {
   valuesReversed[i++] = numberStack.pop(); //反向顺序弹出
                                            // i++ is a post increment i.e.
                                            // assign it and then increment it 
                                            // for the next round 
  }
   
  System.out.println(Arrays.deepToString(valuesReversed));
   
 }
}

 

 

输出结果如下

 

   

[9, 8, 7, 6, 4, 1]