Coding Interview QuestionsInterview Questions and Answers

Latest 60 Stacks Interview Questions

Table of Contents

Introduction

Stacks are a fundamental data structure used in computer science. They follow a “last in, first out” (LIFO) principle, where the last element added is the first one to be removed. Stack interview questions often focus on operations like push (adding an element), pop (removing the top element), and peek (viewing the top element without removing it). They also explore concepts like stack implementation, stack overflow (when the stack is full), and stack underflow (when the stack is empty). These questions assess your understanding of stack functionalities, their applications, and your problem-solving abilities. Familiarizing yourself with stack operations and their typical interview questions can help you prepare effectively.

Stacks

Questions

1. What is a Stack?

A Stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle, meaning the last element inserted is the first one to be removed. It behaves like a collection of items where elements are added and removed only from one end, called the top of the stack.

Example:
Let’s consider a stack of plates. When you put a new plate on top of the stack, you place it on the most recent plate added. When you want to remove a plate, you will always pick the one from the top of the stack.

2. What are the primary operations you can perform on a Stack?

The primary operations performed on a Stack are:

  1. Push: Add an element to the top of the stack.
  2. Pop: Remove and retrieve the top element from the stack.
  3. Peek (or Top): Retrieve the top element without removing it.
  4. IsEmpty: Check if the stack is empty.
  5. Size: Get the number of elements in the stack.

3. In which scenarios would you use a Stack? Give examples.

Stacks are commonly used in scenarios that require the LIFO behavior, such as:

  1. Function Call Stack: Used to store function call information, allowing for function execution and return in the correct order.
  2. Expression Evaluation: Used to convert infix expressions to postfix and for evaluating expressions.
  3. Undo/Redo functionality: Storing the history of actions to enable undoing or redoing.
  4. Backtracking algorithms: Storing states to explore possible solutions.
  5. Browser history: Managing the visited URLs in a browser.

4. What do you understand by LIFO order in the context of Stacks? Explain and give code.

In the context of Stacks, LIFO stands for “Last-In-First-Out,” which means the last element added to the stack will be the first one to be removed.

Example code in C++:

C++
#include <iostream>
#include <stack>

int main() {
    std::stack<int> myStack;
    myStack.push(10); // Add 10 to the top of the stack
    myStack.push(20); // Add 20 to the top of the stack

    // The top element is 20, and it will be removed first
    myStack.pop();

    // The top element is 10
    std::cout << "Top element: " << myStack.top() << std::endl;

    return 0;
}

5. What is the difference between a Stack and a Queue?

StackQueue
LIFO (Last-In-First-Out) data structure.FIFO (First-In-First-Out) data structure.
Elements are inserted and removed from the top (one end).Elements are inserted at the rear and removed from the front.
Examples: stack of plates, function call stack.Examples: queue of people waiting in line.
Primary operations: push, pop, peek.Primary operations: enqueue, dequeue, peek.
Used in backtracking, expression evaluation.Used in task scheduling, breadth-first search.

6. Can you explain how memory is allocated to the Stack? Explain with examples.

In many programming languages, including C++, memory for the stack is automatically allocated and deallocated as functions are called and return. Each function call creates a new stack frame, which contains the function’s local variables and other information needed for execution. When a function returns, its stack frame is popped off the stack, and the memory is freed.

Example:

C++
#include <iostream>

void foo(int x) {
    int y = x + 5;
    // other operations...
}

int main() {
    int a = 10;
    foo(a);
    // other operations...
    return 0;
}

In this example, when main() is called, a stack frame is created for main() with the variable a. When foo(a) is called, a new stack frame is created for foo(), with the parameter x and local variable y. When foo() returns, its stack frame is removed from the stack.

7. What are the applications of a Stack in programming?

Stacks have several applications in programming, including:

  1. Function call management: Used to store information about the current function call and return addresses.
  2. Expression evaluation: Used for infix-to-postfix conversion and expression evaluation.
  3. Backtracking algorithms: Used to store states and backtrack through a problem’s solution space.
  4. Memory management: Used for managing memory allocation and deallocation in certain systems.
  5. Undo/Redo functionality: Storing actions to enable undoing and redoing operations.

8. What is a Stack Overflow, and what causes it?

A Stack Overflow occurs when the stack size limit is exceeded, typically due to excessive recursive function calls or a very deep chain of function calls without returning. Each function call consumes a portion of the stack, and if the stack space is exhausted, it results in a Stack Overflow.

This is often caused by a programming mistake, such as an unbounded recursive function or an infinite loop that prevents functions from returning, leading to the stack being filled up.

9. Can you explain how recursion relates to Stacks?

Recursion in programming is a technique where a function calls itself to solve a problem. When a function is called, its local variables and the return address are pushed onto the stack, forming a new stack frame. The function’s execution continues within this new frame. When the base case is reached, the function calls start to return, and the stack frames are popped off the stack.

Essentially, recursion relies on the stack data structure to manage the function calls and their respective local variables. Recursion can be a powerful tool for solving complex problems but must be used with care to avoid Stack Overflows.

10. What is the difference between a Stack and an Array?

StackArray
A data structure with LIFO behavior.A data structure that stores elements in contiguous memory locations.
Elements are added and removed from the top.Elements can be accessed by their index.
Size can dynamically grow or shrink.Size is fixed upon creation.
Examples: function call stack, browser history.Examples: list of students, temperatures over time.

11. Can you explain the use of Stacks in backtracking?

Backtracking is an algorithmic technique used to find solutions to combinatorial problems. Stacks are often used in backtracking to keep track of the state at each step of the exploration process. When exploring a path, the current state is pushed onto the stack, and if the path leads to a dead end, the algorithm backtracks by popping elements from the stack to return to a previous state and explore other possibilities.

Example:
One common application is the “N-Queens” problem, where you have to place N queens on an N×N chessboard such that no two queens attack each other. The algorithm can use a stack to keep track of the board state at each step and explore different configurations.

12. What is a Stack Frame?

A stack frame, also known as an activation record or stack activation, is a data structure used to store information related to a function call. It contains the function’s local variables, parameters, return address, and other bookkeeping information. When a function is called, a new stack frame is created, and when the function returns, its stack frame is removed.

Example:
Consider the following C++ function:

C++
int add(int a, int b) {
    int sum = a + b;
    return sum;
}

int main() {
    int result = add(5, 3);
    // other operations...
    return 0;
}

When add(5, 3) is called, a stack frame for the add() function is created, containing parameters a and b, as well as the local variable sum. When add() returns, its stack frame is popped off the stack.

13. What is a Stack Pointer?

A stack pointer is a special register or memory location that holds the address of the top of the stack. It points to the last location in the stack where data was added or removed. The stack pointer is updated automatically as elements are pushed or popped from the stack.

Example (x86 assembly pseudo-code):

C++
push 5       ; Push 5 onto the stack
push 10      ; Push 10 onto the stack
pop eax      ; Pop the top element into the eax register

In this example, the stack pointer will be pointing to the location where the value 10 was pushed. After pop eax, the stack pointer is updated to point to the next element on the stack.

14. What is the difference between a static Stack and a dynamic Stack?

Static StackDynamic Stack
The size is fixed upon creation.The size can grow or shrink dynamically.
Memory allocation is done at compile-time.Memory allocation is done at runtime.
May lead to wasted memory if not fully used.Efficient memory usage as size adjusts as needed.
Requires more planning for size estimation.Easier to handle varying data requirements.
Examples: Fixed-size array-based stack.Examples: std::stack in C++ STL.

15. Can you explain the concept of Stack underflow?

Stack underflow occurs when you try to pop or retrieve an element from an empty stack. It is an error condition because there are no elements left in the stack to perform the operation on.

Example:

C++
#include <iostream>
#include <stack>

int main() {
    std::stack<int> myStack;

    // Attempting to pop from an empty stack
    if (myStack.empty()) {
        std::cout << "Stack underflow!" << std::endl;
    } else {
        myStack.pop();
    }

    return 0;
}

In this example, we try to pop an element from an empty stack, resulting in a stack underflow error.

16. What are the limitations of using a Stack?

The limitations of using a Stack include:

  1. Fixed size: Some stack implementations have a fixed size, leading to potential overflow or underflow issues.
  2. Inefficient access: Accessing elements at arbitrary positions in the stack is not efficient due to the LIFO nature.
  3. Recursive depth: Excessive recursion can lead to stack overflow errors.
  4. Not suitable for all data structures: Stacks are not ideal for tasks like sorting or searching, where other data structures (e.g., arrays, heaps) are more efficient.

17. What do you understand by multiple Stacks?

Multiple stacks refer to having more than one stack within the same data structure or memory space. Each stack operates independently and has its own top and elements. The memory for each stack is allocated separately.

Multiple stacks are commonly used in scenarios where different data or tasks need to be managed independently. For example, a two-stack queue uses two stacks to implement a queue data structure.

18. What is a two-stack queue, and how does it work?

A two-stack queue is a queue data structure implemented using two stacks. It provides the same FIFO behavior as a regular queue but uses the LIFO behavior of stacks for efficient enqueue and dequeue operations.

To implement a two-stack queue:

  1. Use one stack for enqueueing elements (in stack 1).
  2. Use the second stack (stack 2) to dequeue elements.
  3. When dequeuing an element, if stack 2 is empty, pop all elements from stack 1 and push them into stack 2, reversing their order.
  4. This way, the front element in the queue will be at the top of stack 2, allowing for efficient dequeue.

19. How is the infix to postfix conversion carried out using a Stack?

Infix to postfix conversion is a process of converting an arithmetic expression from infix notation to postfix notation. The conversion is done using a stack to manage operators and maintain the correct order of operands and operators.

Here’s a simplified algorithm to convert infix to postfix:

  1. Initialize an empty stack to store operators.
  2. Initialize an empty string to store the postfix expression.
  3. Scan the infix expression from left to right.
  4. If the current element is an operand (number), append it to the postfix string.
  5. If the current element is an open parenthesis ‘(‘, push it onto the stack.
  6. If the current element is a closing parenthesis ‘)’, pop operators from the stack and append them to the postfix string until an open parenthesis is encountered. Pop and discard the open parenthesis.
  7. If the current element is an operator, pop operators from the stack and append them to the postfix string until either the stack is empty, or the top operator has lower precedence than the current operator. Push the current operator onto the stack.
  8. After scanning the entire expression, pop any remaining operators from the stack and append them to the postfix string.

Example:
Convert the infix expression “3 + 4 * ( 2 – 1 )” to postfix notation:

C++
Infix:   3 + 4 * ( 2 - 1 )
Postfix: 3 4 2 1 - * +

20. Explain how Stacks can be implemented – using Arrays and Linked Lists.

Stack implementation using Arrays:

A stack can be efficiently implemented using an array. We need to keep track of the top index to know the current position of the top element in the stack.

C++
class StackArray {
private:
    static const int MAX_SIZE = 100; // Max size of the stack
    int arr[MAX_SIZE];
    int top;

public:
    StackArray() {
        top = -1; // Initialize the stack as empty
    }

    bool isEmpty() {
        return top == -1;
    }

    bool isFull() {
        return top == MAX_SIZE - 1;
    }

    void push(int data) {
        if (isFull()) {
            std::cout << "Stack overflow!" << std::endl;
            return;
        }
        arr[++top] = data;
    }

    void pop() {
        if (isEmpty()) {
            std::cout << "Stack underflow!" << std::endl;
            return;
        }
        top--;
    }

    int peek() {
        if (isEmpty()) {
            std::cout << "Stack is empty!" << std::endl;
            return -1;
        }
        return arr[top];
    }
};

Stack implementation using Linked Lists:

A stack can also be implemented using a singly linked list. Each node in the linked list contains data and a pointer to the next node (or nullptr for the last node).

C++
class Node {
public:
    int data;
    Node* next;

    Node(int data) {
        this->data = data;
        next = nullptr;
    }
};

class StackLinkedList {
private:
    Node* top;

public:
    StackLinkedList() {
        top = nullptr; // Initialize the stack as empty
    }

    bool isEmpty() {
        return top == nullptr;
    }

    void push(int data) {
        Node* newNode = new Node(data);
        newNode->next = top;
        top = newNode;
    }

    void pop() {
        if (isEmpty()) {
            std::cout << "Stack underflow!" << std::endl;
            return;
        }
        Node* temp = top;
        top = top->next;
        delete temp;
    }

    int peek() {
        if (isEmpty()) {
            std::cout << "Stack is empty!" << std::endl;
            return -1;
        }
        return top->data;
    }
};

Both implementations have their advantages and trade-offs. Using an array may require resizing when the stack grows beyond the initial capacity, while a linked list implementation can grow dynamically but may require more memory due to the overhead of node pointers.

Coding Questions

1. Write a program to implement a basic stack.

C++
#include <iostream>
#define MAX_SIZE 100

class Stack {
private:
    int top;
    int arr[MAX_SIZE];

public:
    Stack() {
        top = -1;
    }

    bool isEmpty() {
        return (top == -1);
    }

    bool isFull() {
        return (top == MAX_SIZE - 1);
    }

    void push(int value) {
        if (isFull()) {
            std::cout << "Stack Overflow!" << std::endl;
            return;
        }
        arr[++top] = value;
    }

    int pop() {
        if (isEmpty()) {
            std::cout << "Stack Underflow!" << std::endl;
            return -1;
        }
        return arr[top--];
    }

    int peek() {
        if (isEmpty()) {
            std::cout << "Stack is empty!" << std::endl;
            return -1;
        }
        return arr[top];
    }
};

int main() {
    Stack stack;
    stack.push(10);
    stack.push(20);
    stack.push(30);

    std::cout << "Top element: " << stack.peek() << std::endl;

    stack.pop();
    std::cout << "Top element after pop: " << stack.peek() << std::endl;

    stack.pop();
    stack.pop();

    if (stack.isEmpty()) {
        std::cout << "Stack is empty!" << std::endl;
    } else {
        std::cout << "Stack is not empty!" << std::endl;
    }

    return 0;
}

2. Write a function to reverse a stack.

C++
#include <iostream>
#include <stack>

void reverseStack(std::stack<int>& stack) {
    if (stack.empty()) {
        return;
    }

    int temp = stack.top();
    stack.pop();

    reverseStack(stack);
    stack.push(temp);
}

int main() {
    std::stack<int> stack;
    stack.push(1);
    stack.push(2);
    stack.push(3);

    std::cout << "Original Stack: ";
    while (!stack.empty()) {
        std::cout << stack.top() << " ";
        stack.pop();
    }
    std::cout << std::endl;

    stack.push(1);
    stack.push(2);
    stack.push(3);

    reverseStack(stack);

    std::cout << "Reversed Stack: ";
    while (!stack.empty()) {
        std::cout << stack.top() << " ";
        stack.pop();
    }
    std::cout << std::endl;

    return 0;
}

3. Implement a program to check balanced parentheses using a stack.

C++
#include <iostream>
#include <stack>
#include <string>

bool isBalanced(const std::string& parentheses) {
    std::stack<char> stack;

    for (char c : parentheses) {
        if (c == '(' || c == '[' || c == '{') {
            stack.push(c);
        } else {
            if (stack.empty()) {
                return false;
            }

            char top = stack.top();
            stack.pop();

            if ((c == ')' && top != '(') ||
                (c == ']' && top != '[') ||
                (c == '}' && top != '{')) {
                return false;
            }
        }
    }

    return stack.empty();
}

int main() {
    std::string parentheses1 = "((()))";
    std::string parentheses2 = "([{}])";
    std::string

 parentheses3 = "{[()]}";
    std::string parentheses4 = "({[}])";

    std::cout << "Is " << parentheses1 << " balanced? " << (isBalanced(parentheses1) ? "Yes" : "No") << std::endl;
    std::cout << "Is " << parentheses2 << " balanced? " << (isBalanced(parentheses2) ? "Yes" : "No") << std::endl;
    std::cout << "Is " << parentheses3 << " balanced? " << (isBalanced(parentheses3) ? "Yes" : "No") << std::endl;
    std::cout << "Is " << parentheses4 << " balanced? " << (isBalanced(parentheses4) ? "Yes" : "No") << std::endl;

    return 0;
}

4. Write a program to evaluate postfix expression using a stack.

C++
#include <iostream>
#include <stack>
#include <string>
#include <cmath>

int evaluatePostfix(const std::string& postfix) {
    std::stack<int> stack;

    for (char c : postfix) {
        if (isdigit(c)) {
            stack.push(c - '0');
        } else {
            int operand2 = stack.top();
            stack.pop();
            int operand1 = stack.top();
            stack.pop();

            switch (c) {
                case '+':
                    stack.push(operand1 + operand2);
                    break;
                case '-':
                    stack.push(operand1 - operand2);
                    break;
                case '*':
                    stack.push(operand1 * operand2);
                    break;
                case '/':
                    stack.push(operand1 / operand2);
                    break;
                case '^':
                    stack.push(pow(operand1, operand2));
                    break;
            }
        }
    }

    return stack.top();
}

int main() {
    std::string postfix = "34+2*";
    int result = evaluatePostfix(postfix);
    std::cout << "Postfix: " << postfix << std::endl;
    std::cout << "Evaluation Result: " << result << std::endl;

    return 0;
}

5. Implement a program to convert infix expression to postfix using a stack.

C++
#include <iostream>
#include <stack>
#include <string>

int precedence(char op) {
    if (op == '^')
        return 3;
    else if (op == '*' || op == '/')
        return 2;
    else if (op == '+' || op == '-')
        return 1;
    else
        return -1;
}

std::string infixToPostfix(const std::string& infix) {
    std::stack<char> stack;
    std::string postfix;

    for (char c : infix) {
        if (isalpha(c) || isdigit(c)) {
            postfix += c;
        } else if (c == '(') {
            stack.push(c);
        } else if (c == ')') {
            while (!stack.empty() && stack.top() != '(') {
                postfix += stack.top();
                stack.pop();
            }
            stack.pop(); // Discard '('
        } else {
            while (!stack.empty() && precedence(c) <= precedence(stack.top())) {
                postfix += stack.top();
                stack.pop();
            }
            stack.push(c);
        }
    }

    while (!stack.empty()) {
        postfix += stack.top();
        stack.pop();
    }

    return postfix;
}

int main() {
    std::string infix = "a+b*(c^d-e)^(f+g*h)-i";
    std::string postfix = infixToPostfix(infix);
    std::cout << "Infix: " << infix << std::endl;
    std::cout << "Postfix: " << postfix << std::endl;

    return 0;
}

6. Write a program to design a stack that supports getMin() in O(1) time and O(1) extra space.

C++
#include <iostream>
#include <stack>

class MinStack {
private:
    std::stack<int> stack;
    int minElement;

public:
    MinStack() {
        minElement = INT_MAX;
    }

    void push(int value) {
        if (value <= minElement) {
            stack.push(minElement);
            minElement = value;
        }
        stack.push(value);
    }

    void pop() {
        if (stack.top

() == minElement) {
            stack.pop();
            minElement = stack.top();
            stack.pop();
        } else {
            stack.pop();
        }
    }

    int top() {
        return stack.top();
    }

    int getMin() {
        return minElement;
    }
};

int main() {
    MinStack stack;
    stack.push(3);
    stack.push(5);
    stack.push(2);
    stack.push(1);
    stack.push(6);

    std::cout << "Minimum Element: " << stack.getMin() << std::endl;

    stack.pop();
    stack.pop();

    std::cout << "Top Element: " << stack.top() << std::endl;
    std::cout << "Minimum Element: " << stack.getMin() << std::endl;

    return 0;
}

7. Implement a program to sort a stack using a temporary stack.

C++
#include <iostream>
#include <stack>

void sortStack(std::stack<int>& stack) {
    std::stack<int> tempStack;

    while (!stack.empty()) {
        int temp = stack.top();
        stack.pop();

        while (!tempStack.empty() && tempStack.top() > temp) {
            stack.push(tempStack.top());
            tempStack.pop();
        }

        tempStack.push(temp);
    }

    stack = tempStack;
}

int main() {
    std::stack<int> stack;
    stack.push(34);
    stack.push(3);
    stack.push(31);
    stack.push(98);
    stack.push(92);
    stack.push(23);

    std::cout << "Original Stack: ";
    while (!stack.empty()) {
        std::cout << stack.top() << " ";
        stack.pop();
    }
    std::cout << std::endl;

    stack.push(34);
    stack.push(3);
    stack.push(31);
    stack.push(98);
    stack.push(92);
    stack.push(23);

    sortStack(stack);

    std::cout << "Sorted Stack: ";
    while (!stack.empty()) {
        std::cout << stack.top() << " ";
        stack.pop();
    }
    std::cout << std::endl;

    return 0;
}

8. Write a program to implement two stacks in an array.

C++
#include <iostream>

class TwoStacks {
private:
    int* arr;
    int size;
    int top1;
    int top2;

public:
    TwoStacks(int n) {
        size = n;
        arr = new int[size];
        top1 = -1;
        top2 = size;
    }

    void push1(int value) {
        if (top1 < top2 - 1) {
            arr[++top1] = value;
        } else {
            std::cout << "Stack Overflow!" << std::endl;
        }
    }

    void push2(int value) {
        if (top1 < top2 - 1) {
            arr[--top2] = value;
        } else {
            std::cout << "Stack Overflow!" << std::endl;
        }
    }

    int pop1() {
        if (top1 >= 0) {
            return arr[top1--];
        } else {
            std::cout << "Stack Underflow!" << std::endl;
            return -1;
        }
    }

    int pop2() {
        if (top2 < size) {
            return arr[top2++];
        } else {
            std::cout << "Stack Underflow!" << std::endl;
            return -1;
        }
    }
};

int main() {
    Two

Stacks twoStacks(5);
    twoStacks.push1(5);
    twoStacks.push2(10);
    twoStacks.push2(15);
    twoStacks.push1(11);
    twoStacks.push2(7);

    std::cout << "Popped element from stack1: " << twoStacks.pop1() << std::endl;
    std::cout << "Popped element from stack2: " << twoStacks.pop2() << std::endl;

    return 0;
}

9. Implement a program to find the next greater element using a stack.

C++
#include <iostream>
#include <stack>
#include <vector>

std::vector<int> nextGreaterElement(const std::vector<int>& nums) {
    int n = nums.size();
    std::vector<int> result(n, -1);
    std::stack<int> stack;

    for (int i = 0; i < n; i++) {
        while (!stack.empty() && nums[i] > nums[stack.top()]) {
            result[stack.top()] = nums[i];
            stack.pop();
        }
        stack.push(i);
    }

    return result;
}

int main() {
    std::vector<int> nums = {4, 2, 7, 3, 10, 6};
    std::vector<int> result = nextGreaterElement(nums);

    std::cout << "Next Greater Elements: ";
    for (int num : result) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

10. Write a program to implement a special stack that is efficient than using pair or an auxiliary stack.

C++
#include <iostream>
#include <stack>

class SpecialStack {
private:
    std::stack<int> stack;
    int minElement;

public:
    SpecialStack() {
        minElement = INT_MAX;
    }

    void push(int value) {
        if (value < minElement) {
            stack.push(2 * value - minElement);
            minElement = value;
        } else {
            stack.push(value);
        }
    }

    void pop() {
        if (stack.top() < minElement) {
            minElement = 2 * minElement - stack.top();
        }
        stack.pop();
    }

    int top() {
        if (stack.top() < minElement) {
            return minElement;
        } else {
            return stack.top();
        }
    }

    int getMin() {
        return minElement;
    }
};

int main() {
    SpecialStack stack;
    stack.push(3);
    stack.push(5);
    stack.push(2);
    stack.push(1);
    stack.push(6);

    std::cout << "Minimum Element: " << stack.getMin() << std::endl;

    stack.pop();
    stack.pop();

    std::cout << "Top Element: " << stack.top() << std::endl;
    std::cout << "Minimum Element: " << stack.getMin() << std::endl;

    return 0;
}

11. Implement a program to check if an expression contains redundant brackets or not.

C++
#include <iostream>
#include <stack>
#include <string>

bool containsRedundantBrackets(const std::string& expression) {
    std::stack<char> stack;

    for (char ch : expression) {
        if (ch == ')') {
            char top = stack.top();
            stack.pop();

            bool hasOperator = false;
            while (top != '(') {
                if (top == '+' || top == '-' || top == '*' || top == '/') {
                    hasOperator = true;
                }
                top = stack.top();
                stack.pop();
            }

            if (!hasOperator) {
                return true;
            }
        } else {
            stack.push(ch);
        }
    }

    return false;
}

int main() {
    std::string expression1 = "((a+b))";
    std::string expression2 = "(a+(b)/c)";
    std::string expression3 = "(a+b*(c-d))";

    std::cout << "Expression 1 contains redundant brackets: " << std::boolalpha << containsRedundantBrackets(expression1) << std::endl;
    std::cout << "Expression 2 contains redundant brackets: " << std::boolalpha << containsRedundantBrackets(expression2) << std::endl;
    std::cout << "Expression 3 contains redundant brackets: " << std::boolalpha << containsRedundantBrackets(expression3) << std::endl;

    return 0;
}

12. Write a program to reverse a stack without using extra space in O(n).

C++
#include <iostream>
#include <stack>

void insertAtBottom(std::stack<int>& stack, int value) {
    if (stack.empty()) {
        stack.push(value);
    } else {
        int temp = stack.top();
        stack.pop();
        insertAtBottom(stack, value);
        stack.push(temp);
    }
}

void reverseStack(std::stack<int>& stack) {
    if (!stack.empty()) {
        int value = stack.top();
        stack.pop();
        reverseStack(stack);
        insertAtBottom(stack, value);
    }
}

int main() {
    std::stack<int> stack;
    stack.push(1);
    stack.push(2);
    stack.push(3);
    stack.push(4);
    stack.push(5);

    std::cout << "Original Stack: ";
    while (!stack.empty()) {
        std::cout << stack.top() << " ";
        stack.pop();
    }
    std::cout << std::endl;

    stack.push(1);
    stack.push(2);
    stack.push(3);
    stack.push(4);
    stack.push(5);

    reverseStack(stack);

    std::cout << "Reversed Stack: ";
    while (!stack.empty()) {
        std::cout << stack.top() << " ";
        stack.pop();
    }
    std::cout << std::endl;

    return 0;
}

13. Implement a program to implement k stacks in a single array.

C++
#include <iostream>
#include <vector>

class KStacks {
private:
    std::vector<int> arr;
    std::vector<int> top;
    std::vector<int> next;
    int free;

public:
    KStacks(int k, int n) {
        arr.resize(n);
        top.resize(k, -1);
        next.resize(n);
        free = 0;
        for (int i = 0; i < n - 1; i++) {
            next[i] = i + 1;


 }
        next[n - 1] = -1;
    }

    void push(int stackNumber, int value) {
        if (free == -1) {
            std::cout << "Stack Overflow" << std::endl;
            return;
        }
        int insertAt = free;
        free = next[insertAt];
        next[insertAt] = top[stackNumber];
        top[stackNumber] = insertAt;
        arr[insertAt] = value;
    }

    int pop(int stackNumber) {
        if (top[stackNumber] == -1) {
            std::cout << "Stack Underflow" << std::endl;
            return INT_MIN;
        }
        int removeAt = top[stackNumber];
        int value = arr[removeAt];
        top[stackNumber] = next[removeAt];
        next[removeAt] = free;
        free = removeAt;
        return value;
    }

    bool isEmpty(int stackNumber) {
        return (top[stackNumber] == -1);
    }
};

int main() {
    int k = 3;
    int n = 9;
    KStacks kStacks(k, n);

    kStacks.push(0, 1);
    kStacks.push(1, 2);
    kStacks.push(2, 3);
    kStacks.push(0, 4);
    kStacks.push(1, 5);
    kStacks.push(2, 6);
    kStacks.push(0, 7);
    kStacks.push(1, 8);
    kStacks.push(2, 9);

    std::cout << "Popped element from stack 0: " << kStacks.pop(0) << std::endl;
    std::cout << "Popped element from stack 1: " << kStacks.pop(1) << std::endl;
    std::cout << "Popped element from stack 2: " << kStacks.pop(2) << std::endl;

    return 0;
}

14. Write a program to implement a stack using a linked list.

C++
#include <iostream>

class Node {
public:
    int data;
    Node* next;

    Node(int value) {
        data = value;
        next = nullptr;
    }
};

class Stack {
private:
    Node* top;

public:
    Stack() {
        top = nullptr;
    }

    void push(int value) {
        Node* newNode = new Node(value);
        newNode->next = top;
        top = newNode;
    }

    int pop() {
        if (isEmpty()) {
            std::cout << "Stack Underflow" << std::endl;
            return INT_MIN;
        }
        int value = top->data;
        Node* temp = top;
        top = top->next;
        delete temp;
        return value;
    }

    int peek() {
        if (isEmpty()) {
            std::cout << "Stack is empty" << std::endl;
            return INT_MIN;
        }
        return top->data;
    }

    bool isEmpty() {
        return (top == nullptr);
    }
};

int main() {
    Stack stack;
    stack.push(1);
    stack.push(2);
    stack.push(3);
    stack.push(4);

    std::cout << "Top element: " << stack.peek() << std::endl;

    std::cout << "Popped element: " << stack.pop() << std::endl;
    std::cout << "Popped element: " << stack.pop() << std::endl;

    std::cout

 << "Top element: " << stack.peek() << std::endl;

    return 0;
}

15. Implement a program to reverse a string using a stack.

C++
#include <iostream>
#include <stack>
#include <string>

std::string reverseString(const std::string& str) {
    std::stack<char> stack;
    for (char ch : str) {
        stack.push(ch);
    }

    std::string reversed;
    while (!stack.empty()) {
        reversed += stack.top();
        stack.pop();
    }

    return reversed;
}

int main() {
    std::string str = "Hello, World!";
    std::string reversed = reverseString(str);

    std::cout << "Original String: " << str << std::endl;
    std::cout << "Reversed String: " << reversed << std::endl;

    return 0;
}

16. Write a program to implement a stack using queues.

C++
#include <iostream>
#include <queue>

class Stack {
private:
    std::queue<int> q1;
    std::queue<int> q2;
    int topElement;

public:
    Stack() {
        topElement = -1;
    }

    void push(int value) {
        q2.push(value);
        topElement = value;

        while (!q1.empty()) {
            q2.push(q1.front());
            topElement = q1.front();
            q1.pop();
        }

        std::swap(q1, q2);
    }

    int pop() {
        if (isEmpty()) {
            std::cout << "Stack Underflow" << std::endl;
            return INT_MIN;
        }

        int value = q1.front();
        q1.pop();
        if (!q1.empty()) {
            topElement = q1.front();
        }

        return value;
    }

    int peek() {
        if (isEmpty()) {
            std::cout << "Stack is empty" << std::endl;
            return INT_MIN;
        }

        return topElement;
    }

    bool isEmpty() {
        return q1.empty();
    }
};

int main() {
    Stack stack;
    stack.push(1);
    stack.push(2);
    stack.push(3);
    stack.push(4);

    std::cout << "Top element: " << stack.peek() << std::endl;

    std::cout << "Popped element: " << stack.pop() << std::endl;
    std::cout << "Popped element: " << stack.pop() << std::endl;

    std::cout << "Top element: " << stack.peek() << std::endl;

    return 0;
}

17. Implement a program to find a celebrity using stack.

C++
#include <iostream>
#include <stack>

bool knows(int a, int b) {
    // Implementation not provided
}

int findCelebrity(int n) {
    std::stack<int> stack;

    for (int i = 0; i < n; ++i) {
        stack.push(i);
    }

    while (stack.size() > 1) {
        int a = stack.top();
        stack.pop();
        int b = stack.top();
        stack.pop();

        if (knows(a, b)) {
            stack.push(b);
        } else {
            stack.push(a);
        }
    }

    int candidate = stack.top();
    stack.pop();

    for (int i = 0; i < n; ++i) {
        if (i != candidate && (knows(candidate, i) || !knows(i, candidate))) {
            return -

1; // No celebrity found
        }
    }

    return candidate;
}

int main() {
    int n = 4;
    int celebrity = findCelebrity(n);

    if (celebrity == -1) {
        std::cout << "No celebrity found" << std::endl;
    } else {
        std::cout << "Celebrity: " << celebrity << std::endl;
    }

    return 0;
}

18. Write a program to design and implement a data structure for Least Recently Used (LRU) cache using a stack.

C++
#include <iostream>
#include <unordered_map>

class LRUCache {
private:
    int capacity;
    std::unordered_map<int, std::pair<int, std::list<int>::iterator>> cache;
    std::list<int> lruList;

public:
    LRUCache(int capacity) {
        this->capacity = capacity;
    }

    int get(int key) {
        if (cache.find(key) != cache.end()) {
            int value = cache[key].first;
            lruList.erase(cache[key].second);
            lruList.push_front(key);
            cache[key] = {value, lruList.begin()};
            return value;
        }

        return -1;
    }

    void put(int key, int value) {
        if (cache.find(key) != cache.end()) {
            lruList.erase(cache[key].second);
        } else if (lruList.size() >= capacity) {
            int leastRecent = lruList.back();
            lruList.pop_back();
            cache.erase(leastRecent);
        }

        lruList.push_front(key);
        cache[key] = {value, lruList.begin()};
    }
};

int main() {
    LRUCache cache(2);

    cache.put(1, 1);
    cache.put(2, 2);

    std::cout << cache.get(1) << std::endl; // Output: 1

    cache.put(3, 3);

    std::cout << cache.get(2) << std::endl; // Output: -1

    cache.put(4, 4);

    std::cout << cache.get(1) << std::endl; // Output: -1
    std::cout << cache.get(3) << std::endl; // Output: 3
    std::cout << cache.get(4) << std::endl; // Output: 4

    return 0;
}

19. Implement a program to delete the middle of a stack.

C++
#include <iostream>
#include <stack>

void deleteMiddle(std::stack<int>& stack, int k) {
    if (stack.empty() || k == 0) {
        stack.pop();
        return;
    }

    int top = stack.top();
    stack.pop();
    deleteMiddle(stack, k - 1);
    stack.push(top);
}

int main() {
    std::stack<int> stack;
    stack.push(1);
    stack.push(2);
    stack.push(3);
    stack.push(4);
    stack.push(5);

    std::cout << "Original Stack: ";
    while (!stack.empty()) {
        std::cout << stack.top() << " ";
        stack.pop();
    }
    std::cout << std::endl;

    int k = 3;
    deleteMiddle(stack, k);

    std::cout << "Stack after deleting middle element: ";
    while (!stack.empty()) {
        std::cout << stack.top() << " ";
        stack.pop();
    }
    std::cout << std::endl;

    return 0;
}

20. Write a program to find whether a given array can represent the Preorder Traversal of a Binary Search Tree using a stack.

C++
#include <iostream>
#include <stack>
#include <climits>

bool canRepresentPreorderBST(int pre[], int n) {
    std::stack<int> stack;
    int root = INT_MIN;

    for (int i = 0; i < n; i++) {
        if (pre[i] < root) {
            return false;
        }

        while (!stack.empty() && stack.top() < pre[i]) {
            root = stack.top();
            stack.pop();
        }

        stack.push(pre[i]);
    }

    return true;
}

int main() {
    int pre1[] = {2, 4, 3};
    int n = sizeof(pre1) / sizeof(pre1[0]);
    std::cout << "Array can represent Preorder Traversal of a BST: " << std::boolalpha << canRepresentPreorderBST(pre1, n) << std::endl;

    int pre2[] = {2, 4, 1};
    n = sizeof(pre2) / sizeof(pre2[0]);
    std::cout << "Array can represent Preorder Traversal of a BST: " << std::boolalpha << canRepresentPreorderBST(pre2, n) << std::endl;

    return 0;
}

21. Implement a program to find the maximum of all subarrays of size k using a stack.

C++
#include <iostream>
#include <stack>
#include <vector>

std::vector<int> findMaxOfSubarrays(const std::vector<int>& arr, int k) {
    std::vector<int> result;
    std::stack<int> stack;

    for (int i = 0; i < arr.size(); i++) {
        while (!stack.empty() && arr[i] >= arr[stack.top()]) {
            stack.pop();
        }

        stack.push(i);

        if (i >= k - 1) {
            result.push_back(arr[stack.top()]);
            if (stack.top() == i - k + 1) {
                stack.pop();
            }
        }
    }

    return result;
}

int main() {
    std::vector<int> arr = {1, 3, -1, -3, 5, 3, 6, 7};
    int k = 3;

    std::vector<int> maxValues = findMaxOfSubarrays(arr, k);

    std::cout << "Maximum values of subarrays of size " << k << ":" << std::endl;
    for (int value : maxValues) {
        std::cout << value << " ";
    }
    std::cout << std::endl;

    return 0;
}

22. Write a program to design a stack with operations on the middle element.

C++
#include <iostream>
#include <stack>

class StackWithMiddleOperations {
private:
    std::stack<int> stack;
    std::stack<int> middleStack;
    int size;
    int middle;

public:
    StackWithMiddleOperations() {
        size = 0;
        middle = -1;
    }

    void push(int value) {
        stack.push(value);
        size++;

        if (size == 1) {
            middleStack.push(value);
            middle = value;
        } else if (size % 2 == 0) {
            middleStack.push(middle);
        }
    }

    int pop() {
        if (size == 0) {
            throw std::runtime_error("Stack is empty");
        }

        int value = stack.top();
        stack.pop();
        size--;

        if (size % 2 == 0) {
            middleStack.pop();
        }

        if (size > 0) {
            middle = middleStack.top();
        } else {
            middle = -1;
        }

        return value;
    }

    int getMiddle() {
        if (size == 0) {
            throw std::runtime_error("Stack is empty");
        }

        return middle;
    }
};

int main() {
    StackWithMiddleOperations stack;

    stack.push(1);
    stack.push(2);
    stack.push(3);
    stack.push(4);
    stack.push(5);

    std::cout << "Middle element: " << stack.getMiddle() << std::endl; //Output:3

    stack.pop();

    std::cout << "Middle element: " << stack.getMiddle() << std::endl; //Output:3

    stack.pop();

    std::cout << "Middle element: " << stack.getMiddle() << std::endl; //Output:2

    return 0;
}

23. Implement a program to count natural numbers in a stack.

C++
#include <iostream>
#include <stack>

int countNaturalNumbers(std::stack<int>& stack) {
    int count = 0;
    std::stack<int> tempStack

;

    while (!stack.empty()) {
        int number = stack.top();
        stack.pop();

        if (number > 0) {
            count++;
        }

        tempStack.push(number);
    }

    while (!tempStack.empty()) {
        stack.push(tempStack.top());
        tempStack.pop();
    }

    return count;
}

int main() {
    std::stack<int> stack;

    stack.push(0);
    stack.push(-1);
    stack.push(2);
    stack.push(4);
    stack.push(0);
    stack.push(6);

    int count = countNaturalNumbers(stack);

    std::cout << "Count of natural numbers: " << count << std::endl; // Output: 4

    return 0;
}

24. Write a program to reverse a stack using recursion.

C++
#include <iostream>
#include <stack>

void insertAtBottom(std::stack<int>& stack, int item) {
    if (stack.empty()) {
        stack.push(item);
    } else {
        int temp = stack.top();
        stack.pop();
        insertAtBottom(stack, item);
        stack.push(temp);
    }
}

void reverseStack(std::stack<int>& stack) {
    if (!stack.empty()) {
        int item = stack.top();
        stack.pop();
        reverseStack(stack);
        insertAtBottom(stack, item);
    }
}

int main() {
    std::stack<int> stack;

    stack.push(1);
    stack.push(2);
    stack.push(3);
    stack.push(4);
    stack.push(5);

    std::cout << "Original stack: ";
    while (!stack.empty()) {
        std::cout << stack.top() << " ";
        stack.pop();
    }
    std::cout << std::endl;

    reverseStack(stack);

    std::cout << "Reversed stack: ";
    while (!stack.empty()) {
        std::cout << stack.top() << " ";
        stack.pop();
    }
    std::cout << std::endl;

    return 0;
}

25. Implement a program to find the largest rectangular area under a histogram using a stack.

C++
#include <iostream>
#include <stack>

int largestRectangleArea(std::vector<int>& heights) {
    int n = heights.size();
    std::stack<int> stack;
    int maxArea = 0;

    for (int i = 0; i <= n; i++) {
        while (!stack.empty() && (i == n || heights[i] < heights[stack.top()])) {
            int height = heights[stack.top()];
            stack.pop();

            int width = stack.empty() ? i : i - stack.top() - 1;
            maxArea = std::max(maxArea, height * width);
        }

        stack.push(i);
    }

    return maxArea;
}

int main() {
    std::vector<int> heights = {6, 2, 5, 4, 5, 1, 6};
    int area = largestRectangleArea(heights);

    std::cout << "Largest rectangular area: " << area << std::endl; // Output: 12

    return 0;
}

26. Write a program to find if a given expression contains duplicate parentheses or not.

C++
#include <iostream>
#include <stack>

bool hasDuplicateParentheses(const std::string& expression) {
    std::stack<char> stack;

    for (char ch : expression) {
        if (ch == ')') {
            if (stack.top() == '(') {
                return true;
            }

            while

 (stack.top() != '(') {
                stack.pop();
            }

            stack.pop();
        } else {
            stack.push(ch);
        }
    }

    return false;
}

int main() {
    std::string expression = "((a+b)+((c+d)))";

    bool hasDuplicate = hasDuplicateParentheses(expression);

    std::cout << "Expression contains duplicate parentheses: " << std::boolalpha << hasDuplicate << std::endl; // Output: true

    return 0;
}

27. Implement a program to design a stack with the find-middle operation.

C++
#include <iostream>
#include <stack>

class StackWithFindMiddle {
private:
    std::stack<int> stack;
    std::stack<int> middleStack;
    int size;
    int middle;

public:
    StackWithFindMiddle() {
        size = 0;
        middle = -1;
    }

    void push(int value) {
        stack.push(value);
        size++;

        if (size == 1) {
            middleStack.push(value);
            middle = value;
        } else if (size % 2 == 0) {
            middleStack.push(middle);
        }
    }

    int pop() {
        if (size == 0) {
            throw std::runtime_error("Stack is empty");
        }

        int value = stack.top();
        stack.pop();
        size--;

        if (size % 2 == 0) {
            middleStack.pop();
        }

        if (size > 0) {
            middle = middleStack.top();
        } else {
            middle = -1;
        }

        return value;
    }

    int findMiddle() {
        if (size == 0) {
            throw std::runtime_error("Stack is empty");
        }

        return middle;
    }
};

int main() {
    StackWithFindMiddle stack;

    stack.push(1);
    stack.push(2);
    stack.push(3);
    stack.push(4);
    stack.push(5);

    std::cout << "Middle element: " << stack.findMiddle() << std::endl; // Output: 3

    stack.pop();

    std::cout << "Middle element: " << stack.findMiddle() << std::endl; // Output: 3

    stack.pop();

    std::cout << "Middle element: " << stack.findMiddle() << std::endl; // Output: 2

    return 0;
}

28. Write a program to create a stack data structure for holding elements within a given range.

C++
#include <iostream>
#include <stack>

class RangeStack {
private:
    std::stack<int> stack;
    int minRange;
    int maxRange;

public:
    RangeStack(int minRange, int maxRange) {
        this->minRange = minRange;
        this->maxRange = maxRange;
    }

    void push(int value) {
        if (value >= minRange && value <= maxRange) {
            stack.push(value);
        } else {
            throw std::runtime_error("Value out of range");
        }
    }

    void pop() {
        stack.pop();
    }

    int top() {
        return stack.top();
    }

    bool empty() {
        return stack.empty();
    }
};

int main() {
    RangeStack stack(1, 10);

    stack.push(5);
    stack.push(8);
    stack.push(3);
    stack.push(12); // Throws exception: Value out of range

    std::cout << "Top element: " << stack.top() << std::endl; // Output: 3

    stack.pop

();

    std::cout << "Top element: " << stack.top() << std::endl; // Output: 8

    return 0;
}

29. Implement a program to check if a given array can represent the Level Order Traversal of a Binary Search Tree using a stack.

C++
#include <iostream>
#include <stack>
#include <vector>

bool isLevelOrderBST(const std::vector<int>& arr) {
    std::stack<int> stack;
    int root = INT_MIN;

    for (int i = 0; i < arr.size(); i++) {
        if (arr[i] < root) {
            return false;
        }

        while (!stack.empty() && arr[i] > stack.top()) {
            root = stack.top();
            stack.pop();
        }

        stack.push(arr[i]);
    }

    return true;
}

int main() {
    std::vector<int> arr = {7, 4, 12, 3, 6, 8, 1, 5, 10};
    bool isBST = isLevelOrderBST(arr);

    std::cout << "The given array represents a Level Order Traversal of a Binary Search Tree: " << std::boolalpha << isBST << std::endl; // Output: true

    return 0;
}

30. Write a program to find an efficient way to store an extendable array.

C++
#include <iostream>
#include <vector>

class ExtendableArray {
private:
    std::vector<std::vector<int>> array;
    int blockSize;

public:
    ExtendableArray(int blockSize) {
        this->blockSize = blockSize;
    }

    void set(int index, int value) {
        int blockIndex = index / blockSize;
        int innerIndex = index % blockSize;

        if (blockIndex >= array.size()) {
            array.resize(blockIndex + 1);
        }

        if (innerIndex >= array[blockIndex].size()) {
            array[blockIndex].resize(innerIndex + 1);
        }

        array[blockIndex][innerIndex] = value;
    }

    int get(int index) {
        int blockIndex = index / blockSize;
        int innerIndex = index % blockSize;

        if (blockIndex >= array.size() || innerIndex >= array[blockIndex].size()) {
            throw std::runtime_error("Index out of range");
        }

        return array[blockIndex][innerIndex];
    }
};

int main() {
    ExtendableArray array(3);

    array.set(0, 1);
    array.set(3, 5);
    array.set(5, 10);

    std::cout << "Value at index 0: " << array.get(0) << std::endl; // Output: 1
    std::cout << "Value at index 3: " << array.get(3) << std::endl; // Output: 5
    std::cout << "Value at index 5: " << array.get(5) << std::endl; // Output: 10

    return 0;
}

31. Implement a program to design a data structure that supports insert, delete, search, and getRandom in constant time.

C++
#include <iostream>
#include <unordered_map>
#include <vector>

class RandomizedSet {
private:
    std::vector<int> nums;
    std::unordered_map<int, int> indexMap;

public:
    bool insert(int val) {
        if (indexMap.find(val) != indexMap.end()) {
            return false;
        }

        nums.push_back(val);
        indexMap[val] = nums.size() - 1;

        return true;
    }

    bool remove(int val) {
        if (indexMap.find(val) == indexMap.end()) {
            return false;
        }

        int index = indexMap[val];
        int last = nums.back();

        nums[index] = last;
        indexMap[last] = index;

        nums.pop_back();
        indexMap.erase(val);

        return true;
    }

    int getRandom() {
        int randomIndex = rand() % nums.size();
        return nums[randomIndex];
    }
};

int main() {
    RandomizedSet set;

    set.insert(1);
    set.insert(2);
    set.insert(3);
    set.insert(4);

    std::cout << "Random element: " << set.getRandom() << std::endl;

    set.remove(3);

    std::cout << "Random element: " << set.getRandom() << std::endl;

    return 0;
}

32. Write a program to find the length of the longest valid (well-formed) parentheses substring.

C++
#include <iostream>
#include <stack>

int longestValidParentheses(const std::string& s) {
    std::stack<int> stack;
    int maxLen = 0;
    int start = -1;

    for (int i = 0; i < s.length(); i++) {
        if (s[i] == '(') {
            stack.push(i);
        } else {
            if (stack.empty()) {
                start = i;
            } else {
                stack.pop();

                if (stack.empty()) {
                    maxLen = std::max(maxLen, i - start);
                } else {
                    maxLen = std::max(maxLen, i - stack.top());
                }
            }
        }
    }

    return maxLen;
}

int main() {
    std::string parentheses = "((())()(()(";

    int length = longestValidParentheses(parentheses);

    std::cout << "Length of longest valid parentheses substring: " << length << std::endl;

    return 0;
}

33. Implement a program to find the Stock Span Problem.

C++
#include <iostream>
#include <stack>
#include <vector>

std::vector<int> calculateSpan(const std::vector<int>& prices) {
    std::vector<int> span(prices.size(), 0);
    std::stack<int> stack;
    stack.push(0);
    span[0] = 1;

    for (int i = 1; i < prices.size(); i++) {
        while (!stack.empty() && prices[i] >= prices[stack.top()]) {
            stack.pop();
        }

        span[i] = (stack.empty()) ? (i + 1) : (i - stack.top());
        stack.push(i);
    }

    return span;
}

int main() {
    std::vector<int> prices = {100, 80, 60, 70, 60, 75, 85};

    std::vector<int> span = calculateSpan(prices);

    std::cout << "Stock span: ";


 for (int i : span) {
        std::cout << i << " ";
    }
    std::cout << std::endl;

    return 0;
}

34. Write a program to find a queue using a stack.

C++
#include <iostream>
#include <stack>

class Queue {
private:
    std::stack<int> stack1;
    std::stack<int> stack2;

public:
    void enqueue(int value) {
        stack1.push(value);
    }

    int dequeue() {
        if (stack2.empty()) {
            while (!stack1.empty()) {
                stack2.push(stack1.top());
                stack1.pop();
            }
        }

        int front = stack2.top();
        stack2.pop();

        return front;
    }

    bool isEmpty() {
        return stack1.empty() && stack2.empty();
    }
};

int main() {
    Queue queue;

    queue.enqueue(1);
    queue.enqueue(2);
    queue.enqueue(3);

    std::cout << "Dequeued element: " << queue.dequeue() << std::endl; // Output: 1

    queue.enqueue(4);

    std::cout << "Dequeued element: " << queue.dequeue() << std::endl; // Output: 2

    return 0;
}

35. Implement a program to find the largest rectangular area possible in a given histogram.

C++
#include <iostream>
#include <stack>
#include <vector>

int largestRectangleArea(const std::vector<int>& heights) {
    int maxArea = 0;
    std::stack<int> stack;
    int i = 0;

    while (i < heights.size()) {
        if (stack.empty() || heights[i] >= heights[stack.top()]) {
            stack.push(i);
            i++;
        } else {
            int top = stack.top();
            stack.pop();

            int area = heights[top] * (stack.empty() ? i : (i - stack.top() - 1));
            maxArea = std::max(maxArea, area);
        }
    }

    while (!stack.empty()) {
        int top = stack.top();
        stack.pop();

        int area = heights[top] * (stack.empty() ? i : (i - stack.top() - 1));
        maxArea = std::max(maxArea, area);
    }

    return maxArea;
}

int main() {
    std::vector<int> heights = {2, 1, 5, 6, 2, 3};

    int maxArea = largestRectangleArea(heights);

    std::cout << "Largest rectangular area: " << maxArea << std::endl;

    return 0;
}

36. Write a program to find the Longest Absolute File Path.

C++
#include <iostream>
#include <stack>
#include <sstream>

int lengthLongestPath(const std::string& input) {
    std::stringstream ss(input);
    std::stack<int> stack;
    int maxLength = 0;

    while (!ss.eof()) {
        std::string token;
        std::getline(ss, token, '\n');

        int level = token.find_last_of('\t') + 1;
        int length = token.length() - level;

        while (level < stack.size()) {
            stack.pop();
        }

        if (stack.empty()) {
            stack.push(length);
        } else {
            stack.push(stack.top() + 1 + length);
        }

        if (token.find('.') != std::string::npos) {
            maxLength = std::max(maxLength, stack.top());
        }
    }

    return maxLength;
}

int main() {
    std::string input = "dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext";

    int maxLength = lengthLongestPath(input);

    std::cout << "Longest absolute file path length: " << maxLength << std::endl;

    return 0;
}

37. Implement a program to find the Asteroid Collision problem.

C++
#include <iostream>
#include <stack>
#include <vector>

std::vector<int> asteroidCollision(const std::vector<int>& asteroids) {
    std::vector<int> result;
    std::stack<int> stack;

    for (int asteroid : asteroids) {
        if (asteroid > 0) {
            stack.push(asteroid);
        } else {
            while (!stack.empty() && stack.top() > 0 && stack.top() < abs(asteroid)) {
                stack.pop();
            }

            if (stack.empty() || stack.top() < 0) {
                stack.push(asteroid);
            } else if (stack.top() == abs(asteroid)) {
                stack.pop();
            }
        }
    }

    while (!stack.empty()) {
        result.insert(result.begin(), stack.top());
        stack.pop();
    }

    return result;
}

int main() {
    std::vector<int> asteroids = {5, 10, -5};

    std::vector<int> result = asteroidCollision(asteroids);

    std::cout << "Asteroids after collision: ";
    for (int i : result) {
        std::cout << i << " ";
    }
    std::cout << std::endl;

    return 0;
}

38. Write a program to find a stack that keeps track of maximums.

C++
#include <iostream>
#include <stack>

class MaxStack {
private:
    std::stack<int> stack;
    std::stack<int> maxStack;

public:
    void push(int value) {
        stack.push(value);

        if (maxStack.empty() || value >= maxStack.top()) {
            maxStack.push(value);
        }
    }

    void pop() {
        if (stack.top() == maxStack.top()) {
            maxStack.pop();
        }

        stack.pop();
    }

    int top() {
        return stack.top();
    }

    int getMax() {
        return maxStack.top();
    }
};

int main() {
    MaxStack stack;

    stack.push(3);
    stack.push(5);
    stack.push(2);
    stack.push(7);

    std::cout << "Max element: " << stack.getMax() << std::endl; // Output: 7

    stack.pop();
    stack.pop();

    std::cout << "Max element: " << stack.getMax() << std::endl; // Output: 5

    return 0;
}

39. Implement a program to find the Validate Stack Sequences problem.

C++
#include <iostream>
#include <stack>
#include <vector>

bool validateStackSequences(const std::vector<int>& pushed, const std::vector<int>& popped) {
    std::stack<int> stack;
    int i = 0;

    for (int num : pushed) {
        stack.push(num);

        while (!stack.empty() && stack.top() == popped[i]) {
            stack.pop();
            i++;
        }
    }

    return stack.empty();
}

int main() {
    std::vector<int> pushed = {1, 2, 3, 4, 5};
    std::vector<int> popped = {4, 5, 3, 2

, 1};

    bool isValid = validateStackSequences(pushed, popped);

    std::cout << "Stack sequences are " << (isValid ? "valid" : "invalid") << std::endl;

    return 0;
}

40. Write a program to find the Shortest Unsorted Continuous Subarray problem.

C++
#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>

int findUnsortedSubarray(const std::vector<int>& nums) {
    std::stack<int> stack;
    int start = nums.size();
    int end = 0;

    for (int i = 0; i < nums.size(); i++) {
        while (!stack.empty() && nums[stack.top()] > nums[i]) {
            start = std::min(start, stack.top());
            stack.pop();
        }

        stack.push(i);
    }

    stack = std::stack<int>();

    for (int i = nums.size() - 1; i >= 0; i--) {
        while (!stack.empty() && nums[stack.top()] < nums[i]) {
            end = std::max(end, stack.top());
            stack.pop();
        }

        stack.push(i);
    }

    return (end - start >= 0) ? (end - start + 1) : 0;
}

int main() {
    std::vector<int> nums = {2, 6, 4, 8, 10, 9, 15};

    int length = findUnsortedSubarray(nums);

    std::cout << "Length of shortest unsorted subarray: " << length << std::endl;

    return 0;
}

MCQ Questions

1. What is a Stack in data structures?

– A. A linear data structure
– B. A hierarchical data structure
– C. A non-linear data structure
– D. None of the above
– Answer: A

2. Which operation adds an element to the top of the Stack?

– A. Push
– B. Pop
– C. Peek
– D. Insert
– Answer: A

3. Which operation removes the topmost element from the Stack?

– A. Push
– B. Pop
– C. Peek
– D. Remove
– Answer: B

4. Which data structure follows the Last-In-First-Out (LIFO) principle?

– A. Queue
– B. Linked List
– C. Stack
– D. Tree
– Answer: C

5. In which order are elements accessed in a Stack?

– A. First-In-First-Out (FIFO)
– B. Last-In-First-Out (LIFO)
– C. Random
– D. None of the above
– Answer: B

6. Which operation retrieves the top element of the Stack without removing it?

– A. Push
– B. Pop
– C. Peek
– D. Get
– Answer: C

7. Which data structure can be efficiently implemented using a Stack?

– A. Queue
– B. Linked List
– C. Binary Search Tree
– D. Recursion
– Answer: D

8. Which operation checks if a Stack is empty?

– A. IsEmpty
– B. HasElements
– C. IsFull
– D. CheckEmpty
– Answer: A

9. What happens when you try to pop an element from an empty Stack?

– A. An error is thrown
– B. The program crashes
– C. The Stack remains unchanged
– D. None of the above
– Answer: A

10. Which data structure is typically used to implement the Stack?

– A. Array
– B. Linked List
– C. Tree
– D. Hash Table
– Answer: A

11. What is the time complexity of the push operation in a Stack implemented using an array?

– A. O(1)
– B. O(log n)
– C. O(n)
– D. O(n^2)
– Answer: A

12. What is the time complexity of the pop operation in a Stack implemented using an array?

– A. O(1)
– B. O(log n)
– C. O(n)
– D. O(n^2)
– Answer: A

13. Which one is similar to Stack?

– A. Array
– B. Linked List
– C. Tree
– D. Hash Table
– Answer: B

14. Which of the following algorithms is NOT typically implemented using a Stack?

– A. Depth-First Search (DFS)
– B. Breadth-First Search (BFS)
– C. Infix to Postfix conversion
– D. Reverse a linked list
– Answer: B

15. Which data structure can be used to reverse the order of elements in a Stack?

– A. Queue
– B. Linked List
– C. Stack (with an auxiliary Stack)
– D. Binary Search Tree
– Answer: C

16. Which operation reverses the order of elements in a Stack?

– A. Push
– B. Pop
– C. Reverse
– D. Swap
– Answer: C

17. Which operation in a Stack removes all elements from it?

– A. Push
– B. Pop
– C. Clear
– D. RemoveAll
– Answer: C

18. Which data structure is typically used to implement a function call stack?

– A. Queue
– B. Linked List
– C. Stack
– D. Heap
– Answer: C

19. Which data structure is NOT involved in the implementation of the Undo/Redo feature in text editors?

– A. Stack
– B. Linked List
– C. Queue
– D. Tree
– Answer: D

20. Which data structure provides the fastest lookup time for a specific element in a Stack?

– A. Array
– B. Linked List
– C. Stack
– D. Hash Table
– Answer: D

21. Which operation is used to check the size of a Stack?

– A. Size
– B. Length
– C. Count
– D. CheckSize
– Answer: A

22. Which data structure can be used to implement an Undo/Redo feature efficiently?

– A. Array
– B. Linked List
– C. Stack
– D. Tree
– Answer: C

23. Which operation reverses the order of elements in a Stack without using an auxiliary Stack?

– A. Push
– B. Pop
– C. Reverse
– D. Swap
– Answer: C

24. Which data structure allows elements to be added or removed from both ends?

– A. Queue
– B. Linked List
– C. Stack
– D. Deque
– Answer: D

25. Which operation checks if a Stack is full?

– A. IsEmpty
– B. HasElements
– C. IsFull
– D. CheckFull
– Answer: C

26. Which data structure is used in implementing the function call stack?

– A. Array
– B. Linked List
– C. Stack
– D. Heap
– Answer: C

27. Which operation returns the minimum element from a Stack in constant time?

– A. Push
– B. Pop
– C. Peek
– D. GetMin
– Answer: D

28. Which data structure is suitable for evaluating arithmetic expressions?

– A. Queue
– B. Linked List
– C. Stack
– D. Tree
– Answer: C

29. Which operation checks if an element exists in a Stack?

– A. Contains
– B. Exists
– C. Search
– D. Find
– Answer: C

30. Which data structure can be used to implement the back button in web browsers efficiently?

– A. Queue
– B. LinkedList
– C. Stack
– D. Tree
– Answer: C