Stacks

Data Structures and Algorithms (DSA) in C++: Stacks

Stacks are linear data structures that follow the Last In, First Out (LIFO) principle, where the last element added is the first one to be removed. They are widely used in programming for tasks that require sequential processing, such as expression evaluation, function call management (call stack), and backtracking algorithms. Here’s an overview of stacks in C++:

Overview of Stacks

• LIFO Principle: Last In, First Out. The element pushed last onto the stack is the first one to be popped off.
• Operations: Stacks typically support operations such as push (add an element to the top of the stack) and pop (remove an element from the top of the stack).
• Applications: Used in scenarios where elements are processed in a last-in, first-out manner, like function calls, parsing expressions, and undo mechanisms.

Implementing a Stack in C++

Using Standard Template Library (STL)

C++ provides a built-in stack container in the <stack> header, which implements all necessary functionalities efficiently.

Example:

        #include 
          #include 
          
          int main() {
              std::stack s;
          
              // Push elements onto the stack
              s.push(10);
              s.push(20);
              s.push(30);
          
              // Pop elements from the stack and print them
              while (!s.empty()) {
                  std::cout << s.top() << " ";
                  s.pop();
              }
              std::cout << std::endl;
          
              return 0;
          }
          
      

Implementing Stack from Scratch

If you want to understand how stacks work internally, here’s a basic implementation using an array:

        #include 

          const int MAX_SIZE = 100;
          
          class Stack {
          private:
              int top;
              int data[MAX_SIZE];
          
          public:
              Stack() : top(-1) {}
          
              bool isEmpty() {
                  return top == -1;
              }
          
              bool isFull() {
                  return top == MAX_SIZE - 1;
              }
          
              void push(int val) {
                  if (isFull()) {
                      std::cout << "Stack overflow" << std::endl;
                      return;
                  }
                  data[++top] = val;
              }
          
              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 data[top];
              }
          };
          
          int main() {
              Stack s;
          
              s.push(10);
              s.push(20);
              s.push(30);
          
              std::cout << "Top element: " << s.peek() << std::endl;
          
              s.pop();
          
              std::cout << "Top element after pop: " << s.peek() << std::endl;
          
              return 0;
          }
      

Applications of Stacks

• Function Calls: Managing function calls and recursion (call stack).
• Expression Evaluation: Evaluating infix, prefix, or postfix expressions using stacks.
• Undo Mechanisms: Implementing undo operations in applications.
• Backtracking Algorithms: Used in backtracking to store choices and backtrack efficiently.