Assignment: Stacks | DSA in C++ - Software Development PDF Download

Multiple Choice Questions (MCQs)

Q.1. Which of the following data structure follows the LIFO (Last In, First Out) principle?
(a) Queue
(b) Stack
(c) Linked List
(d) Array

Ans. (b)

Q.2. Which operation is not performed on a stack?
(a) Push
(b) Pop
(c) Insert
(d) Peek

Ans. (c)

Q.3. Which of the following is the correct implementation of a stack using an array?

(a) Stack<int> stackArray;
(b) ArrayStack<int> stack;
(c) StackArray<int> stack;
(d) Array<int> stackArray;

Ans. (d)

Q.4. In a stack, which pointer points to the topmost element of the stack?

(a) front
(b) rear
(c) head
(d) top

Ans. (d)

Q.5. Which algorithm is used for reversing a stack efficiently?
(a) Depth First Search (DFS)
(b) Breadth First Search (BFS)
(c) Quick Sort
(d) None of the above

Ans. (d)

High Order Thinking Questions (HOTS)

void reverseStack(stack<int>& st) {

  stack<int> tempStack;

  while (!st.empty()) {

    int element = st.top();

    st.pop();

    tempStack.push(element);

  }

  st = tempStack;

}

Q.2. Given a stack, write a C++ function to find the minimum element in the stack without using any extra space.

int getMinElement(stack<int>& st) {

  int minElement = INT_MAX;

  while (!st.empty()) {

    int element = st.top();

    st.pop();

    minElement = min(minElement, element);

  }

  return minElement;

}

Q.3. Write a C++ program to check if a given expression containing parentheses is balanced or not using a stack.

bool isBalanced(string expr) {

  stack<char> st;

  for (char c : expr) {

    if (c == '(' || c == '{' || c == '[') {

      st.push(c);

    } else if (c == ')' || c == '}' || c == ']') {

      if (st.empty()) {

        return false;

      }

      char top = st.top();

      st.pop();

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

        return false;

      }

    }

  }

  return st.empty();

}

Q.4. Write a C++ program to evaluate a postfix expression using a stack.

int evaluatePostfix(string expr) {

  stack<int> st;

  for (char c : expr) {

    if (isdigit(c)) {

      st.push(c - '0');

    } else {

      int operand2 = st.top();

      st.pop();

      int operand1 = st.top();

      st.pop();

      switch (c) {

        case '+':

          st.push(operand1 + operand2);

          break;

        case '-':

          st.push(operand1 - operand2);

          break;

        case '*':

          st.push(operand1 * operand2);

          break;

        case '/':

          st.push(operand1 / operand2);

          break;

      }

    }

  }

  return st.top();

}

Q.5. Write a C++ program to implement a stack that supports push, pop, and getMin operations in O(1) time complexity.

class MinStack {

  stack<int> st;

  stack<int> minSt;

public:

  void push(int value) {

    st.push(value);

    if (minSt.empty() || value <= minSt.top()) {

      minSt.push(value);

    }

  }

  void pop() {

    if (st.empty()) {

      return;

    }

    int value = st.top();

    st.pop();

    if (value == minSt.top()) {

      minSt.pop();

    }

  }

  int getMin() {

    return minSt.top();

  }

};

Fill in the Blanks

1. In a stack, the operation to add an element is called _______.

In a stack, the operation to add an element is called Push.

2. The operation to remove an element from a stack is called _______.

The operation to remove an element from a stack is called Pop.

3. The _______ function in C++ returns the top element of the stack without removing it.

The top() function in C++ returns the top element of the stack without removing it.

4. The _______ function in C++ returns the number of elements in the stack.

The size() function in C++ returns the number of elements in the stack.

5. A stack is an example of a _______ data structure.

A stack is an example of a Linear data structure.

True/False

1. In a stack, the first element added is the last one to be removed. (True/False)

True

2. A stack can be implemented using an array or a linked list. (True/False)

True

3. The time complexity of the push operation in a stack implemented using an array is O(1). (True/False)

True

4. The time complexity of the pop operation in a stack implemented using a linked list is O(1). (True/False)

True

5. A stack can contain duplicate elements. (True/False)

True

Hands-On Questions

Q.1. Implement a stack using an array in C++. Include the necessary operations: push, pop, and display.

#define MAX_SIZE 100

class ArrayStack {

  int topIndex;

  int stack[MAX_SIZE];

public:

  ArrayStack() {

    topIndex = -1;

  }

  void push(int value) {

    if (topIndex == MAX_SIZE - 1) {

      cout << "Stack Overflow!" << endl;

      return;

    }

    stack[++topIndex] = value;

  }

  void pop() {

    if (topIndex == -1) {

      cout << "Stack Underflow!" << endl;

      return;

    }

    topIndex--;

  }

  void display() {

    if (topIndex == -1) {

      cout << "Stack is empty." << endl;

      return;

    }

    cout << "Stack elements: ";

    for (int i = topIndex; i >= 0; i--) {

      cout << stack[i] << " ";

    }

    cout << endl;

  }

};

int main() {

  ArrayStack stack;

  stack.push(10);

  stack.push(20);

  stack.push(30);

  stack.display(); // Output: Stack elements: 30 20 10

  stack.pop();

  stack.display(); // Output: Stack elements: 20 10

  return 0;

}

Q.2. Implement a stack using a linked list in C++. Include the necessary operations: push, pop, and display.

class Node {

public:

  int data;

  Node* next;

};

class LinkedListStack {

  Node* top;

public:

  LinkedListStack() {

    top = nullptr;

  }

  void push(int value) {

    Node* newNode = new Node();

    newNode->data = value;

    newNode->next = top;

    top = newNode;

  }

  void pop() {

    if (top == nullptr) {

      cout << "Stack Underflow!" << endl;

      return;

    }

    Node* temp = top;

    top = top->next;

    delete temp;

  }

  void display() {

    if (top == nullptr) {

      cout << "Stack is empty." << endl;

      return;

    }

    cout << "Stack elements: ";

    Node* current = top;

    while (current != nullptr) {

      cout << current->data << " ";

      current = current->next;

    }

    cout << endl;

  }

};

int main() {

  LinkedListStack stack;

  stack.push(10);

  stack.push(20);

  stack.push(30);

  stack.display(); // Output: Stack elements: 30 20 10

  stack.pop();

  stack.display(); // Output: Stack elements: 20 10

  return 0;

}

Q.3. Write a C++ program to check if a given string is a palindrome using a stack.

bool isPalindrome(string str) {

  stack<char> st;

  for (char c : str) {

    st.push(c);

  }

  string reverseStr = "";

  while (!st.empty()) {

    reverseStr += st.top();

    st.pop();

  }

  return str == reverseStr;

}

Q.4. Write a C++ program to reverse a string using a stack.

string reverseString(string str) {

  stack<char> st;

  for (char c : str) {

    st.push(c);

  }

  string reversedStr = "";

  while (!st.empty()) {

    reversedStr += st.top();

    st.pop();

  }

  return reversedStr;

}

Q.5. Write a C++ program to convert an infix expression to a postfix expression using a stack.

bool isOperator(char c) {

  return (c == '+' || c == '-' || c == '*' || c == '/');

}

int getPrecedence(char c) {

  if (c == '+' || c == '-') {

    return 1;

  } else if (c == '*' || c == '/') {

    return 2;

  }

  return 0;

}

string infixToPostfix(string expr) {

  stack<char> st;

  string postfix = "";

  for (char c : expr) {

    if (isalpha(c) || isdigit(c)) {

      postfix += c;

    } else if (c == '(') {

      st.push(c);

    } else if (c == ')') {

      while (!st.empty() && st.top() != '(') {

        postfix += st.top();

        st.pop();

      }

      if (!st.empty()) {

        st.pop();

      }

    } else if (isOperator(c)) {

      while (!st.empty() && getPrecedence(st.top()) >= getPrecedence(c)) {

        postfix += st.top();

        st.pop();

      }

      st.push(c);

    }

  }

  while (!st.empty()) {

    postfix += st.top();

    st.pop();

  }

  return postfix;

}