Tutorials

/

Interviewing

/

Stacks

Previous:

Sets

Next:

Queues

Stacks

At this point, you’ve seen techniques for solving interview questions that involve arrays, as well as Map, and Set data structures.

Similar to Map and Set data structures, Stack data structures provide functions that work more efficiently for certain circumstances. Specifically, Stack data structures are handy when you need to add and remove elements from the “front” (or top) of your collection.

You could get this functionality using an ArrayList where you only add or remove elements from the end. But Stack data structures are semantically more correct, and showing familiarity with data structures goes a long way during technical interviews.

Stack vs Deque

Java contains two different stack data structures:

• Stack is older and should generally not be used. This class was implemented before the Java collections framework was added to Java, so its design is inconsistent with other Java collections. (For example, it extends Vector which doesn’t make a ton of sense in modern Java.) It’s also synchronized, which adds performance overhead. (If you need a synchronized stack, there are newer versions!)
• Deque is the newer alternative. Deque (which stands for double ended queue) can act as both a stack and a queue, but this tutorial will focus on using it as a stack.

Deque offers a few functions that let you use it as a stack:

• push(element) adds an element to the top of the stack.
• pop() removes an element from the top of the stack and returns it.
• peek() returns the top element without removing it, or null if the stack is empty.

Alternative Functions

Deque can be used as a stack or a queue, so it has many functions, which can be confusing. You can focus on the functions above for now, but just to be complete:

• addFirst(element), removeFirst(), and peekFirst() are equivalent to push(element) pop(), and peek()
• offerFirst(element), pollFirst(), and getFirst() are similar to the above functions, except offerFirst(element) and pollFirst() return null if the stack is empty instead of throwing exceptions like push(element) and pop(). The getFirst() function is reversed, and throws an exception instead of returning null if the stack is empty.

I suggest reading through the Deque JavaDocs. You don’t need to memorize these implementation details, but mentioning that you remember there are alternatives might score you some bonus points.

The Deque class also contains functions that let it work as a queue, but I’ll save those for the next tutorial.

Implementations

Deque is an interface (similar to how Map and Set are both interfaces), with two common concrete implementations:

• ArrayDeque is newer and the most commonly used.
• LinkedList is older, but is more efficient if you need to insert a new element while you’re iterating (in other words, if you aren’t treating it as a stack). The LinkedList class also offers a get(index) function, but that runs in linear time and is also outside the bounds of the traditional stack data structure.

This is all a lot to remember, but the ArrayDeque class and the push(), pop(), and peek() functions will get you through most questions that require a stack.

Algorithmic Complexity

The power of stack data structures come from the fact that push(element), pop(), and peek() (and their equivalents in the Deque interface) are very efficient. They’re all constant time O(1).

Example: Deque and ArrayDeque

This short example adds three animals to a stack, and then removes them and prints them out.

Deque<String> stack = new ArrayDeque<>();
stack.push("cats");
stack.push("dogs");
stack.push("lizards");

while(!stack.isEmpty()) {
  String animal = stack.pop();
  System.out.println(animal);
}

Because stacks are last-in-first-out, the animals are printed in the reverse of the order they’re added.

Example: Valid Parentheses

A classic interview question involving stacks revolves around something that most programmers have dealt with: making sure parentheses, braces, and brackets are balanced.

• (){}[] is valid because every opening symbol matches a closing symbol, and vice-versa.
• ({}([])) is also valid, because valid opening and closing symbols can contain other valid opening and closing symbol pairs.
• {) is not valid, because neither symbol has a matching partner.
• ()) is not valid, because the last ) does not have a matching (.

Can you write a function that takes a String, and returns whether that String contains a valid set of parentheses and braces?

You might start off by making sure there’s an equal number of opening and closing symbols, but that won’t handle cases like this:

• (}{)
• ])([
• {(}[)]

You might try using a two pointer approach that matches symbols from the outside in, but how would you handle cases like this?

• ()[]{}
• ([]{})
• ({}([]))

It’s trickier than it first appears! But think about how you do this in your head, or with a piece of paper and a pencil. How do you decide whether this is a valid set of braces?

( { } [ ( ) ] )

The way I do this in my head, I look for the smallest (), {}, or [] pairs, and I remove them from the string one at a time. If I remove them all and I’m left with nothing, then the string is valid. If I remove them all and I still have at least one symbol left over, then the string is not valid.

Here’s an example of running through that algorithm with a valid string. Each iteration looks for a matching opening and closing braces and then removes them until nothing is left.

• ( { } [ ( ) ] )

• ( { } [ ( ) ] )

• (     [ ( ) ] )

• (     [     ] )

• (             )

• The string is now empty, so it’s valid!

And here’s an example of applying the algorithm to an invalid string:

• ( { } [ ( ) ( )

• ( { } [ ( ) ( )

• (     [ ( ) ( )

• (     [     ( )

• (     [

• The string is not empty, so it’s not valid!

Putting that into code, it might look like this:

public boolean isValid(String s) {

  while(s.contains("()") || s.contains("{}") || s.contains("[]")) {
    s = s.replace("()", "");
    s = s.replace("{}", "");
    s = s.replace("[]", "");
  }

  return s.length() == 0;

}

This code uses a while loop to check whether the string contains any brace pairs. As long as it does, it replaces the pair with the empty string to remove it. When the while loop exits, the string is valid only if it’s now empty.

What’s the algorithmic complexity of this function?

This is a little tricky because it depends on the content of the string. But imagine the worst case scenario, which is a string like this:

({[({[({[()]})]})]})

This string has a length of 20, and contains 10 pairs of nested braces.

How many times will the while loop iterate? Each iteration of the loop removes one pair, so for this string, it’ll need to loop 10 times. That’s n/2, or O(n) so far.

Then within each iteration, it calls contains() to evaluate whether to continue looping. In this example, it has to search through 10 characters, which also makes it O(n). Then the code calls replace() to remove the pair. That requires copying over the contents of the string, which is again O(n) linear. Since this code calls linear O(n) functions inside a linear O(n) loop, the whole function is O(n ^ 2).

Can you do better?

Improving the Algorithm

Rather than looking for each individual pair, you might iterate over the string and keep track of a history of which opening braces you’ve seen. When you encounter a closing brace, you look at your history. If the closing brace matches the most recently seen opening brace, you found a pair and can remove the opening brace from the history. If it doesn’t match, then you know you’ve encountered an invalid string. If you get to the end of the string and your history still contains an opening brace, then you’ve also got an invalid string.

For example, for this valid string ( { } [ ( ) ] ), here are the steps the “history” algorithm follows:

And for an invalid string ( { } [ ( ) ( ), here’s how the algorithm works:

The algorithm also needs to check for cases where it encounters a mismatched closing bracket.

public boolean isValid(String s) {

  String openingBraceHistory = "";

  for (int i = 0; i < s.length(); i++) {
    char currentChar = s.charAt(i);

    if(currentChar == '(' || currentChar == '{' || currentChar == '[') {
      // Add the opening brace to the history
      openingBraceHistory += currentChar;
    } else {

      // Found a closing brace without an opening brace
      if(openingBraceHistory.isEmpty()){
        return false;
      }

      // Get and remove the previous closing brace from the history
      char previousOpeningBrace = openingBraceHistory.charAt(openingBraceHistory.length() -1);
      openingBraceHistory = openingBraceHistory.substring(0, openingBraceHistory.length() -1);

      // Check for mismatched braces
      if (previousOpeningBrace == '(' && currentChar != ')') {
        return false;
      } else if (previousOpeningBrace == '{' && currentChar != '}') {
        return false;
      } else if (previousOpeningBrace == '[' && currentChar != ']') {
        return false;
      }
    }
  }

  // Found opening braces without closing braces
  if (!openingBraceHistory.isEmpty()) {
    return false;
  }

  // History is empty and we didn't find any mismatched braces
  return true;
}

What’s the algorithmic complexity of this function?

This code contains a for loop, and then inside that for loop it maintains a String openingBraceHistory using the += append operator and the substring() function. Both of those are linear, which means this code is still O(n ^ 2).

Can you do better?

Stack to the Rescue

You could improve this by using an ArrayList to represent your history and then only adding or removing elements from the end. But if you want to show off a more semantic (and slightly more runtime efficient) data structure, you can use a stack! (Or rather, a Deque and ArrayDeque)

public boolean isValid(String s) {

  Deque<Character> openingBraceHistory = new ArrayDeque<>();

  for (int i = 0; i < s.length(); i++) {
    char currentChar = s.charAt(i);

    if(currentChar == '(' || currentChar == '{' || currentChar == '[') {
      // Add the opening brace to the history
      openingBraceHistory.push(currentChar);
    } else {

      // Found a closing brace without an opening brace
      if(openingBraceHistory.isEmpty()){
        return false;
      }

      // Get and remove the previous closing brace
      char previousOpeningBrace = openingBraceHistory.pop();

      // Check for mismatched braces
      if (previousOpeningBrace == '(' && currentChar != ')') {
        return false;
      } else if (previousOpeningBrace == '{' && currentChar != '}') {
        return false;
      } else if (previousOpeningBrace == '[' && currentChar != ']') {
        return false;
      }
    }
  }

  // Found opening braces without closing braces
  if (!openingBraceHistory.isEmpty()) {
    return false;
  }

  // History is empty and we didn't find any mismatched braces
  return true;
}

Now what’s the algorithmic complexity?

The code still loops over the input string for O(n) linear complexity. But inside that loop, the code calls the push(), and pop() functions, which are both O(1) constant time. So the algorithmic complexity for the whole function is O(n) linear!

Practice Questions

• Valid Parentheses
• Simplify Path
• Reverse Polish Notation
• Basic Calculator
• Basic Calculator II
• Remove All Adjacent Duplicates in String

Previous:

Sets

Next:

Queues