Top 25 Stacks Interview Questions And Answers

Q: Why Are Stacks Useful?

They’re very useful because they afford you constant time O ( 1 ) operations when _inserting_ or _removing_ from the front of a data structure. One common use of a stack is in compilers, where a stack can be used to make sure that the brackets and parentheses in a code file are all balanced, i.e., have an opening and closing counterpart. Stacks are also very useful in evaluating mathematical expressions.

Q: What is complexity of `push` and `pop` for a Stack implemented using a LinkedList?

O ( 1 ) . Note, you don't have to insert at the end of the list. If you insert at the front of a (singly-linked) list, they are both `O(1)`. Stack contains 1,2,3: ```py [1]->[2]->[3] ``` Push 5: ```js [5]->[1]->[2]->[3] ``` Pop: ```js [1]->[2]->[3] // returning 5 ```

Question 1

Define Stack

Accepted Answer

A **Stack** is a container of objects that are inserted and removed according to the last-in first-out (**LIFO**) principle. In the pushdown stacks only two operations are allowed: push the item into the stack, and pop the item out of the stack.

There are basically three operations that can be performed on stacks. They are:
 
1. inserting an item into a stack (**push**). 
2. deleting an item from the stack (**pop**). 
3. displaying the contents of the stack (**peek** or **top**).

A stack is a limited access data structure - elements can be added and removed from the stack only at the top. push adds an item to the top of the stack, pop removes the item from the top. A helpful analogy is to think of a stack of books; you can remove only the top book, also you can add a new book on the top.

![](https://user-images.githubusercontent.com/13550565/85218531-fea33d80-b3cd-11ea-8ba4-77c37d446d07.png)

Question 2

Explain why Stack is a recursive data structure

Accepted Answer

A **stack** is a **recursive** data structure, so it's:

* a stack is either empty or
* it consists of a top and the rest which is a stack by itself;

Question 3

Why and when should I use Stack or Queue data structures instead of Arrays/Lists?

Accepted Answer

Because they help manage your data in more a _particular_ way than arrays and lists. It means that when you're debugging a problem, you won't have to wonder if someone randomly inserted an element into the middle of your list, messing up some invariants.

Arrays and lists are random access. They are very flexible and also easily *corruptible*. If you want to manage your data as FIFO or LIFO it's best to use those, already implemented, collections.

More practically you should:
* Use a queue when you want to get things out in the order that you put them in (FIFO)
* Use a stack when you want to get things out in the reverse order than you put them in (LIFO)
* Use a list when you want to get anything out, regardless of when you put them in (and when you don't want them to automatically be removed).

Question 4

Design a Stack that supports retrieving the min element in _`O(1)`_

Accepted Answer

Using a linked list store the current minimum value. When you add a new number it looks at the previous min and changes the current min to the current value if the current value is lower. Note, each node stores the `min` value _at or below_ it so we don't need to recalculate `min` on pop.

Question 5

Why Are Stacks Useful?

Accepted Answer

They’re very useful because they afford you constant time O(1) operations when _inserting_ or _removing_ from the front of a data structure. One common use of a stack is in compilers, where a stack can be used to make sure that the brackets and parentheses in a code file are all balanced, i.e., have an opening and closing counterpart. Stacks are also very useful in evaluating mathematical expressions.

Question 6

Implement Stack using Two Queues (with efficient `push`)

Accepted Answer

Given we have `queue1` and `queue2`:

**push** - `O(1)`: 
  - enqueue in `queue1`

**pop** - `O(n)`:
  - while size of `queue1` is bigger than 1, pipe (dequeue + enqueue) dequeued items from `queue1` into `queue2`
  - dequeue and return the last item of `queue1`, then switch the names of `queue1` and `queue2`

Question 7

Reverse a String using Stack

Accepted Answer

The followings are the steps to reversing a String using Stack:

1.  `String` to `char[]`.
2.  Create a `Stack`.
3.  **Push** all characters, one by one.
4.  Then **Pop** all characters, one by one and put into the `char[]`.
5.  Finally, convert to the `String`.

Question 8

How to implement Linked List Using Stack?

Accepted Answer

You can simulate a linked list by using two stacks. One stack is the "list," and the other is used for temporary storage.

* To **add** an item at the head, simply push the item onto the stack. 
* To **remove** from the head, pop from the stack.
* To **insert** into the middle somewhere, pop items from the "list" stack and push them onto the temporary stack until you get to your insertion point. Push the new item onto the "list" stack, then pop from the temporary stack and push back onto the "list" stack. Deletion of an arbitrary node is similar.

This isn't terribly efficient, by the way, but it would in fact work.

Question 9

Implement a Queue using two Stacks

Accepted Answer

Keep two stacks, let's call them `inbox` and `outbox`.

**Enqueue**:

- Push the new element onto `inbox`

**Dequeue**:

- If `outbox` is empty, refill it by popping **each** element from `inbox` and pushing it onto `outbox`
 - Pop and return the top element from `outbox`

Question 10

What is complexity of `push` and `pop` for a Stack implemented using a LinkedList?

Accepted Answer

O(1). Note, you don't have to insert at the end of the list. If you insert at the front of a (singly-linked) list, they are both `O(1)`. Stack contains 1,2,3: ```py [1]->[2]->[3] ``` Push 5: ```js [5]->[1]->[2]->[3] ``` Pop: ```js [1]->[2]->[3] // returning 5 ```

Top 25 Stacks Interview Questions

Define Stack

Explain why Stack is a recursive data structure

Why Are Stacks Useful?

How to implement Linked List Using Stack?

Why and when should I use Stack or Queue data structures instead of Arrays/Lists?

Explain what are Infix, Prefix and Postfix Expressions?

Compare Array based vs Linked List stack implementations

Why do we need Prefix and Postfix notations?

How do I convert a Queue into the Stack?

Reverse a String using Stack

Design a Stack that supports retrieving the min element in `O(1)`

Implement a Queue using two Stacks

Implement Stack using Two Queues (with efficient `push`)

What is complexity of `push` and `pop` for a Stack implemented using a LinkedList?

Sort a Stack using Recursion

Find duplicate parenthesis in expression

How reverse Stack without using any (extra) data structure?

Check if parentheses are balanced using Stack

Sort a Stack using another Stack

Implement Double Linked List from Stack with min complexity

How to implement 3 Stacks with one Array?

Given an extremely large file that contains parenthesis, how would you say that the parenthesis are balanced?

Build a Binary Expression Tree for this expression

How implement a Queue using only One (1) Stack?

How to check for braces balance in a really large (1T) file in parallel?

Top 25 Stacks Interview Questions

Define Stack

Explain why Stack is a recursive data structure

Why Are Stacks Useful?

How to implement Linked List Using Stack?

Why and when should I use Stack or Queue data structures instead of Arrays/Lists?

Explain what are Infix, Prefix and Postfix Expressions?

Compare Array based vs Linked List stack implementations

Why do we need Prefix and Postfix notations?

How do I convert a Queue into the Stack?

Reverse a String using Stack

Design a Stack that supports retrieving the min element in O(1)

Implement a Queue using two Stacks

Implement Stack using Two Queues (with efficient push)

What is complexity of push and pop for a Stack implemented using a LinkedList?

Sort a Stack using Recursion

Find duplicate parenthesis in expression

How reverse Stack without using any (extra) data structure?

Check if parentheses are balanced using Stack

Sort a Stack using another Stack

Implement Double Linked List from Stack with min complexity

How to implement 3 Stacks with one Array?

Given an extremely large file that contains parenthesis, how would you say that the parenthesis are balanced?

Build a Binary Expression Tree for this expression

How implement a Queue using only One (1) Stack?

How to check for braces balance in a really large (1T) file in parallel?

Design a Stack that supports retrieving the min element in `O(1)`

Implement Stack using Two Queues (with efficient `push`)

What is complexity of `push` and `pop` for a Stack implemented using a LinkedList?