Stacks are one of the most straightforward yet robust data structures used in computer science. They are widely implemented in various applications, from expression parsing to system call management. Stacks follow the Last In First Out (LIFO) principle, meaning the most recently added item to the data structure will be accessed first. This tutorial provides a detailed understanding of the mechanics behind stacks, highlighting their operations, advantages, and implementation techniques.



The Principles of a Stack

A stack is a linear data structure data structure that follows a "last in, first out" (LIFO) principle. It means the last element to be added is the first to be removed. The structure restricts adding or removing elements to one end, called the "top." It's similar to a stack of plates where you can only put or remove the top plate. This mechanism is essential in many computing processes, such as managing function calls in programming languages and evaluating expressions.

Data Structures & Algorithms Stack

Core Operations of a Stack

The functionality of a stack can be encapsulated in a few critical operations:

  • Initialize: Create an empty stack.
  • isEmpty: Verify if the stack has no elements.
  • isFull: Check if the stack has reached its maximum capacity.
  • Push: Add an element to the top of the stack.
  • Pop: Remove the topmost element from the stack.
  • Peek: Retrieve the topmost element without removing it.

These operations form the foundation of stack manipulation, allowing developers to manage data efficiently in a LIFO manner.

Representation of Stack using Arrays

Arrays provide a straightforward approach to implementing stacks, requiring a linear array and a top pointer to track the stack's top element. Below is a detailed C++ example demonstrating essential stack operations through array utilization:

Example:

#include <iostream>
#include <limits> // Necessary for std::numeric_limits
using namespace std;

// Defines a stack for integer storage
class Stack {
    int* arr; // Stores stack elements
    int capacity; // Maximum size of the stack
    int top; // Index of the top element in the stack

public:
    // Initializes an empty stack with given capacity
    Stack(int size) : capacity(size), top(-1) {
        arr = new int[capacity];
    }

    // Adds an element to the top of the stack
    void push(int element) {
        if (top >= capacity - 1) { // Check for overflow
            cout << "Stack Overflow\n";
            return;
        }
        arr[++top] = element; // Increment top and add element
        cout << element << " pushed into the stack.\n";
    }

    // Removes the top element from the stack
    void pop() {
        if (top < 0) { // Check for underflow
            cout << "Stack Underflow\n";
            return;
        }
        cout << arr[top--] << " popped from the stack.\n"; // Decrement top and remove element
    }

    // Displays all elements from top to bottom
    void display() {
        if (top < 0) { // Check if stack is empty
            cout << "Stack is empty\n";
            return;
        }
        cout << "Stack elements are:\n";
        for (int i = top; i >= 0; i--) {
            cout << arr[i] << " ";
        }
        cout << "\n";
    }

    // Deallocates the dynamically allocated memory
    ~Stack() {
        delete[] arr;
    }
};

// Demonstrates stack operations
int main() {
    int size, choice, value;
    cout << "Enter the size of the stack: ";
    cin >> size;
    Stack stack(size); // Create a stack of the given size

    do {
        cout << "\n1. Push 2. Pop 3. Display 4. Exit\nEnter your choice: ";
        cin >> choice;

        // Validates input and continues according to the choice
        if(cin.fail()) {
            cin.clear(); // Clears error flags
            cin.ignore(numeric_limits<streamsize>::max(), '\n'); // Discards invalid input
            cout << "Invalid input. Please enter a numeric value.\n";
            continue;
        }

        switch (choice) {
            case 1: // Push operation
                cout << "Enter the value to push: ";
                cin >> value;
                if(cin.fail()) {
                    cin.clear(); // Clear error flags
                    cin.ignore(numeric_limits<streamsize>::max(), '\n'); // Discard invalid input
                    cout << "Invalid input. Please enter a numeric value for the element.\n";
                    continue;
                }
                stack.push(value);
                break;
            case 2: // Pop operation
                stack.pop();
                break;
            case 3: // Display stack contents
                stack.display();
                break;
            case 4: // Exit the program
                cout << "Exiting program.\n";
                return 0;
            default: // Handles invalid choices
                cout << "Invalid choice. Please try again.\n";
        }
    } while (true); // Infinite loop until the user chooses to exit

    return 0;
}

This above code snippet demonstrates creating a stack, pushing elements onto it, popping elements from it, and displaying its contents, along with proper input validation to ensure robust user interaction.

Output:

Enter the size of the stack: 3

1. Push 2. Pop 3. Display 4. Exit
Enter your choice: 1
Enter the value to push: 200
200 pushed into the stack.

1. Push 2. Pop 3. Display 4. Exit
Enter your choice: 1
Enter the value to push: 300
300 pushed into the stack.

1. Push 2. Pop 3. Display 4. Exit
Enter your choice: 1
Enter the value to push: 400
400 pushed into the stack.

1. Push 2. Pop 3. Display 4. Exit
Enter your choice: 1
Enter the value to push: 500
Stack Overflow

1. Push 2. Pop 3. Display 4. Exit
Enter your choice: 2
400 popped from the stack.

1. Push 2. Pop 3. Display 4. Exit
Enter your choice: 3
Stack elements are:
300 200

Conclusion

Stacks are fundamental in programming, providing a structured way to manage data following the LIFO principle. This tutorial covers the basics of stack operations and demonstrates how to implement a stack using arrays in C++. Understanding and utilizing stacks is crucial for efficient problem-solving and enhancing application functionality in various computational contexts.



Found This Page Useful? Share It!
Get the Latest Tutorials and Updates
Join us on Telegram