15 Stack Interview Questions and Answers

Stacks are a fundamental data structure in computer science, characterized by their Last In, First Out (LIFO) behavior. They are essential for various applications, including expression evaluation, backtracking algorithms, and memory management. Understanding stacks is crucial for solving complex problems efficiently and is a key concept in many programming languages and systems.

This article offers a curated selection of stack-related interview questions designed to test and enhance your understanding of this vital data structure. By working through these questions, you will gain the confidence and knowledge needed to tackle stack-related challenges in technical interviews.

Stack Interview Questions and Answers

1. Explain the concept of a stack and its primary operations (push, pop, peek).

A stack is a linear data structure that follows the Last In, First Out (LIFO) principle. It is used in various applications such as expression evaluation, backtracking algorithms, and function call management in programming languages.

The primary operations of a stack are:

• Push: Adds an element to the top of the stack.
• Pop: Removes the top element from the stack.
• Peek: Returns the top element of the stack without removing it.

Here is a simple implementation of a stack in Python:

class Stack:
    def __init__(self):
        self.items = []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        if not self.is_empty():
            return self.items.pop()
        return None

    def peek(self):
        if not self.is_empty():
            return self.items[-1]
        return None

    def is_empty(self):
        return len(self.items) == 0

# Example usage
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.peek())  # Output: 3
print(stack.pop())   # Output: 3
print(stack.pop())   # Output: 2
print(stack.is_empty())  # Output: False

2. Write a function to reverse a string using a stack.

A stack is particularly useful for reversing a string, as you can push each character onto the stack and then pop them off in reverse order.

Here is a simple implementation in Python:

def reverse_string_using_stack(s):
    stack = []
    
    # Push all characters of the string onto the stack
    for char in s:
        stack.append(char)
    
    # Pop all characters from the stack and form the reversed string
    reversed_string = ''
    while stack:
        reversed_string += stack.pop()
    
    return reversed_string

# Example usage
print(reverse_string_using_stack("hello"))  # Output: "olleh"

3. Write a function to check for balanced parentheses in an expression using a stack.

To check for balanced parentheses in an expression using a stack, traverse the expression and use the stack to keep track of opening parentheses. When a closing parenthesis is encountered, check if it matches the top of the stack. If it does, pop the stack; otherwise, the parentheses are not balanced.

Example:

def is_balanced(expression):
    stack = []
    pairs = {')': '(', '}': '{', ']': '['}

    for char in expression:
        if char in pairs.values():
            stack.append(char)
        elif char in pairs.keys():
            if stack == [] or pairs[char] != stack.pop():
                return False
    return stack == []

# Test cases
print(is_balanced("()"))  # True
print(is_balanced("({[)]}"))  # False
print(is_balanced("{[()]}"))  # True

4. Implement a stack using two queues.

To implement a stack using two queues, use one queue to hold the elements and another to assist in the push operation. The idea is to always keep the newest element at the front of the main queue.

from queue import Queue

class StackUsingQueues:
    def __init__(self):
        self.q1 = Queue()
        self.q2 = Queue()

    def push(self, x):
        self.q2.put(x)
        while not self.q1.empty():
            self.q2.put(self.q1.get())
        self.q1, self.q2 = self.q2, self.q1

    def pop(self):
        if self.q1.empty():
            return None
        return self.q1.get()

    def top(self):
        if self.q1.empty():
            return None
        return self.q1.queue[0]

    def empty(self):
        return self.q1.empty()

# Example usage:
stack = StackUsingQueues()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.pop())  # Output: 3
print(stack.top())  # Output: 2
print(stack.empty())  # Output: False

5. Write a function to sort a stack using only stack operations.

To sort a stack using only stack operations, use an auxiliary stack to hold elements in sorted order. Pop elements from the original stack and push them into the auxiliary stack so that the largest elements are on the top.

def sort_stack(original_stack):
    auxiliary_stack = []

    while original_stack:
        temp = original_stack.pop()
        while auxiliary_stack and auxiliary_stack[-1] > temp:
            original_stack.append(auxiliary_stack.pop())
        auxiliary_stack.append(temp)

    while auxiliary_stack:
        original_stack.append(auxiliary_stack.pop())

    return original_stack

# Example usage
stack = [34, 3, 31, 98, 92, 23]
sorted_stack = sort_stack(stack)
print(sorted_stack)  # Output: [3, 23, 31, 34, 92, 98]

6. Write a function to evaluate a postfix expression using a stack.

A postfix expression is a mathematical notation where operators follow their operands. A stack is ideal for evaluating postfix expressions because it allows for efficient management of operands and operators.

Here is a concise example of how to evaluate a postfix expression using a stack:

def evaluate_postfix(expression):
    stack = []
    for token in expression.split():
        if token.isdigit():
            stack.append(int(token))
        else:
            b = stack.pop()
            a = stack.pop()
            if token == '+':
                stack.append(a + b)
            elif token == '-':
                stack.append(a - b)
            elif token == '*':
                stack.append(a * b)
            elif token == '/':
                stack.append(a / b)
    return stack[0]

expression = "3 4 + 2 * 7 /"
print(evaluate_postfix(expression))  # Output: 2.0

7. Explain how recursion uses the call stack.

Recursion uses the call stack to keep track of function calls. When a recursive function is called, the current state is pushed onto the call stack. This allows the function to return to the correct state once the recursive call completes. Each recursive call creates a new frame on the stack, and the function continues to call itself until a base case is reached. Once the base case is met, the stack begins to unwind, and each function call is popped off the stack, returning control to the previous call.

Example:

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)

print(factorial(5))  # Output: 120

In this example, the factorial function calls itself with n-1 until n is 0. Each call to factorial is pushed onto the call stack. When n reaches 0, the base case is met, and the stack unwinds, returning the result of each multiplication.

8. Write a function to find the minimum element in a stack in constant time.

To find the minimum element in a stack in constant time, use an auxiliary stack to keep track of the minimum elements. Maintain a secondary stack that stores the minimum values corresponding to the elements in the main stack.

Here is a concise implementation:

class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, x):
        self.stack.append(x)
        if not self.min_stack or x <= self.min_stack[-1]:
            self.min_stack.append(x)

    def pop(self):
        if self.stack:
            if self.stack[-1] == self.min_stack[-1]:
                self.min_stack.pop()
            return self.stack.pop()

    def get_min(self):
        if self.min_stack:
            return self.min_stack[-1]

In this implementation, the push method adds an element to the main stack and also updates the minimum stack if the new element is smaller than or equal to the current minimum. The pop method removes the top element from the main stack and also updates the minimum stack if the removed element is the current minimum. The get_min method retrieves the minimum element in constant time.

9. Write a function to convert an infix expression to a postfix expression using a stack.

Infix expressions are the common arithmetic expressions where operators are placed between operands. Postfix expressions, also known as Reverse Polish Notation (RPN), place operators after their operands. Converting an infix expression to a postfix expression can be efficiently done using a stack to handle operator precedence and parentheses.

Here is a concise example of how to implement this conversion using a stack:

def infix_to_postfix(expression):
    precedence = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3}
    stack = []
    output = []

    for char in expression:
        if char.isalnum():
            output.append(char)
        elif char == '(':
            stack.append(char)
        elif char == ')':
            while stack and stack[-1] != '(':
                output.append(stack.pop())
            stack.pop()
        else:
            while stack and stack[-1] != '(' and precedence[char] <= precedence[stack[-1]]:
                output.append(stack.pop())
            stack.append(char)

    while stack:
        output.append(stack.pop())

    return ''.join(output)

# Example usage:
expression = "A*(B+C)/D"
print(infix_to_postfix(expression))  # Output: "ABC+*D/"

10. Write a function to implement a stack that supports push, pop, and retrieving the maximum element in constant time.

To implement a stack that supports push, pop, and retrieving the maximum element in constant time, use two stacks: one for storing the actual stack elements and another for keeping track of the maximum elements.

Here is a concise implementation:

class MaxStack:
    def __init__(self):
        self.stack = []
        self.max_stack = []

    def push(self, x):
        self.stack.append(x)
        if not self.max_stack or x >= self.max_stack[-1]:
            self.max_stack.append(x)

    def pop(self):
        if self.stack:
            if self.stack[-1] == self.max_stack[-1]:
                self.max_stack.pop()
            return self.stack.pop()

    def get_max(self):
        if self.max_stack:
            return self.max_stack[-1]

# Example usage:
max_stack = MaxStack()
max_stack.push(5)
max_stack.push(1)
max_stack.push(5)
print(max_stack.get_max())  # Output: 5
max_stack.pop()
print(max_stack.get_max())  # Output: 5
max_stack.pop()
print(max_stack.get_max())  # Output: 5

11. Discuss the time complexity of various stack operations.

In a stack, the primary operations are push, pop, peek, and isEmpty. The time complexity of these operations is important for understanding the efficiency of stack usage in different scenarios.

• Push: The push operation adds an element to the top of the stack. This operation has a time complexity of O(1) because it involves adding an element to the end of a list, which is a constant-time operation.
• Pop: The pop operation removes the top element from the stack. Similar to push, this operation also has a time complexity of O(1) as it involves removing the last element from a list, which is a constant-time operation.
• Peek: The peek operation returns the top element of the stack without removing it. This operation has a time complexity of O(1) because it simply accesses the last element of the list.
• isEmpty: The isEmpty operation checks whether the stack is empty. This operation has a time complexity of O(1) as it involves checking the length of the list or comparing the top pointer to a base value.

12. Explain how a stack can be used to perform depth-first search (DFS) on a graph.

Depth-first search (DFS) is an algorithm used to traverse or search through graph data structures. DFS explores as far as possible along each branch before backtracking, making it a natural fit for a stack-based approach.

In DFS, a stack is used to keep track of the nodes to be explored. The algorithm starts at a given node, marks it as visited, and pushes it onto the stack. It then iteratively pops nodes from the stack, explores their unvisited neighbors, marks them as visited, and pushes them onto the stack. This process continues until the stack is empty.

Example:

def dfs(graph, start):
    visited = set()
    stack = [start]

    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            stack.extend(neighbor for neighbor in graph[node] if neighbor not in visited)

    return visited

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

print(dfs(graph, 'A'))
# Output: {'A', 'B', 'C', 'D', 'E', 'F'}

13. How does a stack support backtracking algorithms? Provide an example.

A stack is particularly useful for backtracking algorithms, where you need to explore possible solutions and revert to previous states when a dead end is reached.

In backtracking algorithms, a stack is used to keep track of the choices made at each step. When a decision leads to a dead end, the algorithm can backtrack by popping the last choice off the stack and trying a different path.

Example:

def solve_maze(maze, start, end):
    stack = [(start, [start])]
    while stack:
        (position, path) = stack.pop()
        for next_position in get_neighbors(position, maze):
            if next_position == end:
                return path + [next_position]
            if next_position not in path:
                stack.append((next_position, path + [next_position]))
    return None

def get_neighbors(position, maze):
    neighbors = []
    for move in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
        new_position = (position[0] + move[0], position[1] + move[1])
        if 0 <= new_position[0] < len(maze) and 0 <= new_position[1] < len(maze[0]) and maze[new_position[0]][new_position[1]] == 0:
            neighbors.append(new_position)
    return neighbors

maze = [
    [0, 1, 0, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 1, 0],
    [0, 1, 1, 1, 0],
    [0, 0, 0, 0, 0]
]

start = (0, 0)
end = (4, 4)

print(solve_maze(maze, start, end))
# Output: [(0, 0), (1, 0), (2, 0), (2, 1), (2, 2), (3, 2), (4, 2), (4, 3), (4, 4)]

14. What are some common pitfalls when using stacks in concurrent programming?

In concurrent programming, stacks can present several common pitfalls:

• Race Conditions: When multiple threads access and modify the stack simultaneously without proper synchronization, it can lead to inconsistent or incorrect data.
• Deadlocks: Improper use of locks can lead to deadlocks, where two or more threads are waiting indefinitely for each other to release locks.
• Starvation: If a stack is used in a way that prioritizes certain threads over others, some threads may be starved of resources.
• Improper Synchronization: Failing to use synchronization mechanisms like mutexes or semaphores can result in unpredictable behavior. Conversely, overusing synchronization can lead to performance bottlenecks.

Example:

import threading

stack = []

def push_item(item):
    stack.append(item)

def pop_item():
    if stack:
        return stack.pop()
    return None

# Simulating race condition
thread1 = threading.Thread(target=push_item, args=(1,))
thread2 = threading.Thread(target=pop_item)

thread1.start()
thread2.start()

thread1.join()
thread2.join()

In this example, the lack of synchronization can lead to a race condition where the stack’s state becomes inconsistent.

15. Write a function to implement a stack that supports push, pop, and retrieving the median element in logarithmic time.

import heapq

class MedianStack:
    def __init__(self):
        self.min_heap = []
        self.max_heap = []
        self.stack = []

    def push(self, val):
        self.stack.append(val)
        if not self.max_heap or val <= -self.max_heap[0]:
            heapq.heappush(self.max_heap, -val)
        else:
            heapq.heappush(self.min_heap, val)
        self._balance_heaps()

    def pop(self):
        if not self.stack:
            return None
        val = self.stack.pop()
        if val <= -self.max_heap[0]:
            self.max_heap.remove(-val)
            heapq.heapify(self.max_heap)
        else:
            self.min_heap.remove(val)
            heapq.heapify(self.min_heap)
        self._balance_heaps()
        return val

    def get_median(self):
        if len(self.max_heap) > len(self.min_heap):
            return -self.max_heap[0]
        elif len(self.min_heap) > len(self.max_heap):
            return self.min_heap[0]
        else:
            return (-self.max_heap[0] + self.min_heap[0]) / 2

    def _balance_heaps(self):
        if len(self.max_heap) > len(self.min_heap) + 1:
            heapq.heappush(self.min_heap, -heapq.heappop(self.max_heap))
        elif len(self.min_heap) > len(self.max_heap) + 1:
            heapq.heappush(self.max_heap, -heapq.heappop(self.min_heap))

# Example usage:
stack = MedianStack()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.get_median())  # Output: 2
stack.pop()
print(stack.get_median())  # Output: 1.5