Stacks & Queues - DSA Interview Questions

Stacks and queues are fundamental data structures used to efficiently manage and process data in a structured order. Stacks follow the Last In, First Out (LIFO) principle, while queues operate on the First In, First Out (FIFO) method.

Understanding these structures is essential for solving a wide range of coding problems, including recursion, backtracking, and scheduling tasks.

Practice Stacks & Queues DSA Coding Problems with Solutions

Learning Objectives:

Learn how to implement and use stacks and queues to solve real-world computational problems. Develop problem-solving skills for handling dynamic data operations, including push-pop and enqueue-dequeue methods.

Exercise Instructions:

Start with the first problem and attempt to solve it before checking the hint or solution.
Ensure you understand the logic behind each solution, as this will help you with more complex problems.
Use these exercises to reinforce your learning and identify areas that may require further study.

1. Implement a Stack Using an Array

Required Input:

operations = ['push 10', 'push 20', 'push 30', 'pop', 'peek', 'is_empty']

Expected Output:

Popped element: 30
Top element: 20
Stack is empty: False

Code In Python

class StackArray: def __init__(self): # Write your logic here pass def push(self, x): pass def pop(self): pass def peek(self): pass def is_empty(self): pass # Prefilled input stack = StackArray() operations = ["push 10", "push 20", "push 30", "pop", "peek", "is_empty"] for op in operations: if "push" in op: stack.push(int(op.split()[1])) elif op == "pop": print("Popped element:", stack.pop()) elif op == "peek": print("Top element:", stack.peek()) elif op == "is_empty": print("Stack is empty:", stack.is_empty())

Run Code?

Click Run Button to view compiled output

2. Implement a Stack Using a Linked List

Required Input:

operations = ['push 5', 'push 15', 'push 25', 'pop', 'peek', 'is_empty']

Expected Output:

Popped element: 25
Top element: 15
Stack is empty: False

Code In Python

class StackLinkedList: class Node: def __init__(self, data): pass def __init__(self): pass def push(self, x): pass def pop(self): pass def peek(self): pass def is_empty(self): pass # Prefilled input stack = StackLinkedList() operations = ["push 5", "push 15", "push 25", "pop", "peek", "is_empty"] for op in operations: if "push" in op: stack.push(int(op.split()[1])) elif op == "pop": print("Popped element:", stack.pop()) elif op == "peek": print("Top element:", stack.peek()) elif op == "is_empty": print("Stack is empty:", stack.is_empty())

Run Code?

Click Run Button to view compiled output

3. Check for Balanced Parentheses

Required Input:

s = '{[()()]}'

Expected Output:

True

Code In Python

def is_valid_parentheses(s): # Write your logic here pass # Prefilled input s = "{[()()]}" print(is_valid_parentheses(s))

Run Code?

Click Run Button to view compiled output

4. Reverse a String Using a Stack

Required Input:

s = 'hello'

Expected Output:

olleh

Code In Python

def reverse_string(s): # Write your logic here pass # Prefilled input s = "hello" print(reverse_string(s))

Run Code?

Click Run Button to view compiled output

5. Sort a Stack Using Recursion

Required Input:

stack = [3, 1, 4, 2]

Expected Output:

[1, 2, 3, 4]

Code In Python

def sort_stack(stack): # Write your logic here pass # Prefilled input stack = [3, 1, 4, 2] print(sort_stack(stack))

Run Code?

Click Run Button to view compiled output

6. Find the Next Greater Element

Required Input:

arr = [4, 5, 2, 25]

Expected Output:

[5, 25, 25, -1]

Code In Python

def next_greater_element(arr): # Write your logic here pass # Prefilled input arr = [4, 5, 2, 25] print(next_greater_element(arr))

Run Code?

Click Run Button to view compiled output

7. Implement Min Stack

Required Input:

operations = ['push 5', 'push 2', 'push 10', 'getMin', 'pop', 'getMin']

Expected Output:

Current minimum: 2
Current minimum: 2

Code In Python

class MinStack: def __init__(self): # Write your logic here pass def push(self, x): pass def pop(self): pass def top(self): pass def getMin(self): pass # Prefilled input stack = MinStack() operations = ["push 5", "push 2", "push 10", "getMin", "pop", "getMin"] for op in operations: if "push" in op: stack.push(int(op.split()[1])) elif op == "pop": stack.pop() elif op == "getMin": print("Current minimum:", stack.getMin())

Run Code?

Click Run Button to view compiled output

8. Evaluate a Postfix Expression

Required Input:

expression = ['2', '1', '+', '3', '*']

Expected Output:

Code In Python

def evaluate_postfix(expression): # Write your logic here pass # Prefilled input expression = ["2", "1", "+", "3", "*"] print(evaluate_postfix(expression))

Run Code?

Click Run Button to view compiled output

9. Largest Rectangle in Histogram

Required Input:

heights = [2, 1, 5, 6, 2, 3]

Expected Output:

Code In Python

def largest_rectangle_area(heights): # Write your logic here pass # Prefilled input heights = [2, 1, 5, 6, 2, 3] print(largest_rectangle_area(heights))

Run Code?

Click Run Button to view compiled output

10. Stock Span Problem

Required Input:

prices = [100, 80, 60, 70, 60, 75, 85]

Expected Output:

[1, 1, 1, 2, 1, 4, 6]

Code In Python

def calculate_stock_span(prices): # Write your logic here pass # Prefilled input prices = [100, 80, 60, 70, 60, 75, 85] print(calculate_stock_span(prices))

Run Code?

Click Run Button to view compiled output

1 of 3