| The Java Collection library is one of the most frequently used libraries.The LIFO access mechanism used by a stack has many practical uses. For example, Evaluation of expressions / syntax Parsing, validating and parsing XML, undo sequence in a text editor, pages visited history in a web browser, etc. Here are a few Java based interview questions and answers on a stack. Q. What LIFO implementation would you use in Java? A. The Vector based Stack class is a legacy and the Javadoc documentation for this class states that Deque should be used instead because it provides better LIFO operation support. Implementations of Deque are typically expected to perform better than Stack. J2SE 5 introduced a Queue interface and the Deque interface extends this interface. The Deque interface supports should be pronounced "deck" rather than "de-queue" and is not related to dequeue used to indicate removal from a queue. The double-ended queue supports addition or removal of elements from either end of the data structure, so it can be used as a queue (first-in-first-out/FIFO) or as a stack (last-in-first-out/LIFO). Note: The legacy Vector class uses internal synchronization, and it is rarely good enough for actual consistency, and can slow down execution when it is not really needed. The new java.util.concurrent package provides a more efficient way of thread-safety. Q. Can you write a program to evaluate if a given string input has proper closing bracket for every opening bracket? A. Firstly, think of the pseudo code. The pseudo-code goes as follows. 1. Store every opening parenthesis (i.e. a LHS parenthesis) in a stack. This will enable LIFO. 2. When you encounter a closing parenthesis (i.e. RHS parenthesis ), pop the last entry, which should be the corresponding opening parenthesis. 3. If not found, then the parentheses are not matched. If required, draw a diagram as shown below. |
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 {
//stores the parentheses
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)); // auto boxing takes place
// push the opening parentheses
//for each RHS parenthesis check if there is a matching LHS Parenthesis
//if the stack is empty or does not have a matching LHS parenthesis then not balanced.
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(); //if the stack is empty, then all matched well, otherwise not matched.
}
}
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);
}
}
Thread.currentThread().getStackTrace() ; //handy for tracing
ThreadMXBean bean = ManagementFactory.getThreadMXBean();
ThreadInfo[] infos = bean.dumpAllThreads(true, true);
for (ThreadInfo info : infos) {
StackTraceElement[] elems = info.getStackTrace();
//...do something
}
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)
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
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]); // push the numbers in given order
}
Integer[] valuesReversed = new Integer[values.length];
int i = 0;
while (!numberStack.isEmpty()) {
valuesReversed[i++] = numberStack.pop(); // pop it - as this happens in reverse order
// 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]