Stack

Stack is a data structure that supports two typical operations:

  1. Push an element to the end of the stack.
  2. Pop an element from the end of the stack.

You may read more about stack in the Wikipedia article.

There is a built-in stack in most languages. In most cases, you should use it when solving interview questions:

Java
C++
Stack<Integer> stack = new Stack<>();
      
stack.push(2);
stack.push(3);
stack.push(5);
stack.push(8);
System.out.println(stack);        // [2, 3, 5, 8]

int topElement = stack.peek();
System.out.println(topElement);   // 8

stack.pop();
System.out.println(stack);        // [2, 3, 5]

stack.pop();
System.out.println(stack);        // [2, 3]

It's a good exercise though to write your own stack from scratch. How would you write it? Be sure that all operations take O(1) time.

Practice

So, why do you even need stack?

There are a lot of situations that can be nicely modeled with stack. Let's look at some problems.

Try to solve the following problem:

Hint
Solution

Here is another great problem where stack comes handy:

Solution

Here are some more nice stack problems: