10 Stack & Queues Interview Questions Devs Must Know
A stack is a basic data structure that can be logically thought of as a linear structure represented by a real physical stack or pile, a structure where insertion and deletion of items takes place at one end called top of the stack.
Q1: Explain why Stack is a recursive data structure
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;
Q2: Design a Stack that supports retrieving the min element in O(1)
O(1)Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
push(x)- Push element x onto stack.pop()- Removes the element on top of the stack.top()- Get the top element.getMin()- Retrieve the minimum element in the stack.
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.
class MinStack {
private class Node {
int val;
int min;
Node next;
private Node(int val, int min) {
this(val, min, null);
}
private Node(int val, int min, Node next) {
this.val = val;
this.min = min;
this.next = next;
}
}
private Node head;
public void push(int x) {
if(head == null)
head = new Node(x, x);
else
head = new Node(x, Math.min(x, head.min), head);
}
public void pop() {
head = head.next;
}
public int top() {
return head.val;
}
public int getMin() {
return head.min;
}
}Q3: Implement a Queue using two Stacks
Suppose we have two stacks and no other temporary variable. Is to possible to "construct" a queue data structure using only the two stacks?
Keep two stacks, let's call them inbox and outbox.
Enqueue:
- Push the new element onto
inbox
Dequeue:
- If
outboxis empty, refill it by popping each element frominboxand pushing it ontooutbox - Pop and return the top element from
outbox
In the worst case scenario when outbox stack is empty, the algorithm pops n elements from inbox stack and pushes n elements to outbox, where n is the queue size. This gives 2*n operations, which is O(n). But when outbox stack is not empty the algorithm has O(1) time complexity that gives amortised O(1).
public class Queue<T> where T : class
{
private Stack<T> input = new Stack<T>();
private Stack<T> output = new Stack<T>();
public void Enqueue(T t)
{
input.Push(t);
}
public T Dequeue()
{
if (output.Count == 0)
{
while (input.Count != 0)
{
output.Push(input.Pop());
}
}
return output.Pop();
}
}Q4: What is Complexity Analysis of Queue operations?
- Queues offer random access to their contents by shifting the first element off the front of the queue. You have to do this repeatedly to access an arbitrary element somewhere in the queue. Therefore, access is
O(n). - Searching for a given value in the queue requires iterating until you find it. So search is
O(n). - Inserting into a queue, by definition, can only happen at the back of the queue, similar to someone getting in line for a delicious Double-Double burger at In 'n Out. Assuming an efficient queue implementation, queue insertion is
O(1). - Deleting from a queue happens at the front of the queue. Assuming an efficient queue implementation, queue deletion is `
O(1).
Q5: Why and when should I use Stack or Queue data structures instead of Arrays/Lists?
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).
Q6: Check if parentheses are balanced using Stack
One of the most important applications of stacks is to check if the parentheses are balanced in a given expression. The compiler generates an error if the parentheses are not matched.
Here are some of the balanced and unbalanced expressions:
Algorithm
- Declare a character stack which will hold an array of all the opening parenthesis.
- Now traverse the expression string exp.
- If the current character is a starting bracket (
(or{or[) then push it to stack. - If the current character is a closing bracket (
)or}or]) then pop from stack and if the popped character is the matching starting bracket then fine else parenthesis are not balanced. - After complete traversal, if there is some starting bracket left in stack then “not balanced”
- We are traversing through each character of string, Time complexity
O(n). - We are storing the opposite parentheses characters in the stack, in the worst case there can be all the opposite characters in the string, Space complexity
O(n).
let isMatchingBrackets = function (str) {
let stack = [];
let map = {
'(': ')',
'[': ']',
'{': '}'
}
for (let i = 0; i < str.length; i++) {
// If character is an opening brace add it to a stack
if (str[i] === '(' || str[i] === '{' || str[i] === '[' ) {
stack.push(str[i]);
}
// If that character is a closing brace, pop from the stack, which will also reduce the length of the stack each time a closing bracket is encountered.
else {
let last = stack.pop();
//If the popped element from the stack, which is the last opening brace doesn’t match the corresponding closing brace in the map, then return false
if (str[i] !== map[last]) {return false};
}
}
// By the completion of the for loop after checking all the brackets of the str, at the end, if the stack is not empty then fail
if (stack.length !== 0) {return false};
return true;
}Q7: Compare Array-Based vs List-Based implementation of Queues
Queue backed by a singly-linked list. Enqueuing into the linked list can be implemented by appending to the back of the singly-linked list, which takes worst-case time
O(1). Dequeuing can be implemented by removing the first element, which also takes worst-case timeO(1). This also requires a new allocation per enqueue, which may be slow.Queue backed by a growing circular buffer. Enqueuing into the circular buffer works by inserting something at the next free position in the circular buffer. This works by growing the array if necessary, then inserting the new element. Using a similar analysis for the dynamic array, this takes best-case time
O(1), worst-case timeO(n), and amortized timeO(1). Dequeuing from the buffer works by removing the first element of the circular buffer, which takes timeO(1)in the worst case.
To summarise, all of the structures support pushing and popping n elements in O(n) time. The linked list versions have better worst-case behavior, but may have a worse overall runtime because of the number of allocations performed. The array versions are slower in the worst-case, but have better overall performance if the time per operation isn't too important.
Q8: Sort a Stack using Recursion
Note we can't use another stack or queue.
The idea of the solution is to hold all values in system stack until the stack becomes empty. When the stack becomes empty, insert all held items one by one in sorted order.
void sort(stack s) {
if (!IsEmpty(s)) {
int x = Pop(s);
sort(s);
insert(s, x);
}
}
void insert(stack s, int x) {
if (!IsEmpty(s)) {
int y = Top(s);
if (x < y) {
Pop(s);
insert(s, x);
Push(s, y);
} else {
Push(s, x);
}
} else {
Push(s, x);
}
}Q9: What are benefits of Circular Queue?
- In circular queue, memory is utilized. If we delete any element that position is used later.
- Circular queue consumes less memory than linear queue because in queue while doing insertion after deletion operation it allocate an extra space the first remaining vacant but in circular queue the first is used as it comes immediate after the last.
- In CQ the memory of the deleted process can be used by some other new process.
- A standard queue suffers from a rebuffering problem during deque operations. By making the queue circular and linking the head to the tail, this alleviates the problem and allows insertion and deletion in constant time.
Q10: How to implement 3 Stacks with one Array?
Rust has been Stack Overflow’s most loved language for four years in a row and emerged as a compelling language choice for both backend and system developers, offering a unique combination of memory safety, performance, concurrency without Data races...
Clean Architecture provides a clear and modular structure for building software systems, separating business rules from implementation details. It promotes maintainability by allowing for easier updates and changes to specific components without affe...
Azure Service Bus is a crucial component for Azure cloud developers as it provides reliable and scalable messaging capabilities. It enables decoupled communication between different components of a distributed system, promoting flexibility and resili...
FullStack.Cafe is a biggest hand-picked collection of top Full-Stack, Coding, Data Structures & System Design Interview Questions to land 6-figure job offer in no time.
Coded with 🧡 using React in Australia 🇦🇺
by @aershov24, Full Stack Cafe Pty Ltd 🤙, 2018-2023
Privacy • Terms of Service • Guest Posts • Contacts • MLStack.Cafe
based on 86 Trustpilot 
Reviews