Introduction to Stack Data Structure with Practical Examples

• Stack Data Structure
• Operations in Stack
  • Push Operation
  • Pop Operation
  • Peek (or Top) Operation
  • isEmpty Operation
• Implementation of Stack Using Array and Struct in C
• Stack Overflow and Stack Underflow
• Stack in C++ STL
  • Functions in C++ STL Stack
• Applications of Stack
• Infix to Postfix Expression Conversion Using Stack
• Run C Programming Online Compiler

A stack data structure operates similarly to adding or removing plates from a stack of plates. It follows the Last In, First Out (LIFO) principle. Adding a plate to the top and removing from the top ensure that the last plate added is the first one taken. It only lets you add or remove plates from the top and doesn’t allow any changes in other parts of the stack.

¶Stack Data Structure

A stack is a fundamental data structure in computer science that operates on the Last-In-First-Out (LIFO) principle. The last element added is the first to be removed, creating a sequential order where the most recent addition is the priority for removal.

Stack is a versatile data structure and find applications across various domains in computer science. They are essential for tasks such as tracking function calls in programs, managing memory efficiently, and undo mechanisms in software applications.

¶Operations in Stack

¶Push Operation

The push operation involves adding an element to the top of the stack. The newly added element becomes the top of the stack. It’s like placing a plate on top of a pile of plates. When we push a new plate onto the stack, we’re placing it directly on the top. As a result, the plate we just added becomes the new top of the stack.
Time Complexity: O(1) - Constant time complexity, as the push operation does not depend on the size of the stack.

¶Pop Operation

The pop operation removes the element from the top of the stack. After this operation, the element below the removed one becomes the new top. it’s like removing the top plate from a pile of plates. The plate just below the one we removed becomes the new top.
Time Complexity: O(1) - Constant time complexity, as the pop operation’s duration is independent of the stack’s size.

¶Peek (or Top) Operation

Peek retrieves the element at the top of the stack without removing it. It allows you to inspect the top element without altering the stack.
Time Complexity: O(1) - Constant time complexity, as it involves accessing the top element directly.

¶isEmpty Operation

The isEmpty operation checks if the stack is empty, i.e., it has no elements. It returns a boolean indicating whether the stack is devoid of elements.
Time Complexity: O(1) - Constant time complexity, as checking if the stack is empty doesn’t depend on its size.

¶Implementation of Stack Using Array and Struct in C

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100

// Define the stack structure
struct Stack {
    int arr[MAX_SIZE];
    int top;
};

// Function to initialize the stack
void initialize(struct Stack *stack) {
    stack->top = -1; // Initialize top to -1 to indicate an empty stack
}

// Function to check if the stack is empty
int isEmpty(struct Stack *stack) {
    return stack->top == -1;
}

// Function to check if the stack is full
int isFull(struct Stack *stack) {
    return stack->top == MAX_SIZE - 1;
}

// Function to push an element onto the stack
void push(struct Stack *stack, int element) {
    if (isFull(stack)) {
        printf("Stack Overflow: Cannot push element %d, stack is full.\n", element);
        return;
    }
    stack->arr[++stack->top] = element;
    printf("Pushed %d onto the stack.\n", element);
}

// Function to pop an element from the stack
int pop(struct Stack *stack) {
    if (isEmpty(stack)) {
        printf("Stack is empty. Cannot pop from an empty stack.\n");
        return -1; // Return a special value to indicate underflow
    }
    int poppedElement = stack->arr[stack->top--];
    printf("Popped %d from the stack.\n", poppedElement);
    return poppedElement;
}

// Function to get the top element without removing it
int peek(struct Stack *stack) {
    if (isEmpty(stack)) {
        printf("Stack is empty. No element to peek.\n");
        return -1; // Return a special value to indicate underflow
    }
    return stack->arr[stack->top];
}

int main() {
    // Declare and initialize a stack
    struct Stack myStack;
    initialize(&myStack);

    // Push elements onto the stack
    push(&myStack, 10);
    push(&myStack, 20);
    push(&myStack, 30);

    // Peek at the top element
    printf("Top element: %d\n", peek(&myStack));

    // Pop elements from the stack
    pop(&myStack);
    pop(&myStack);
    pop(&myStack);

    // Try popping from an empty stack
    pop(&myStack);

    return 0;
}

¶Stack Overflow and Stack Underflow

Stack overflow occurs when an attempt is made to push an element onto a stack that is already at its maximum capacity, leading to a situation where there is no more space for additional elements. Stack underflow occurs when an attempt is made to pop an element from an empty stack, where there are no elements to remove.

#include <stdio.h>

#define MAX_SIZE 3

int stack[MAX_SIZE];
int top = -1;

// Function to push an element onto the stack
void push(int element) {
    if (top == MAX_SIZE - 1) {
        printf("Stack Overflow: Cannot push %d, stack is full.\n", element);
        return;
    }
    stack[++top] = element;
    printf("Pushed %d onto the stack.\n", element);
}

// Function to pop an element from the stack
int pop() {
    if (top == -1) {
        printf("Stack Underflow: Cannot pop from an empty stack.\n");
        return -1; // Return a special value to indicate underflow
    }
    printf("Popped %d from the stack.\n", stack[top]);
    return stack[top--];
}

int main() {
    // Attempting to push more elements than the stack can hold
    push(1);
    push(2);
    push(3);
    push(4); // This will cause a stack overflow

    pop(); 
    pop(); 
    pop(); 
    // Attempting to pop from an empty stack
    pop();   // This will cause a stack underflow
    return 0;
}

Here, we first attempt to push more elements than the stack’s capacity, causing a stack overflow. Subsequently, we attempt to pop elements from an empty stack, resulting in a stack underflow. These scenarios highlight the importance of checking the stack’s status before performing push and pop operations to prevent overflow and underflow.

¶Stack in C++ STL

The C++ STL stack provides a convenient way to implement and use stacks, offering various methods for common stack operations. To use the stack in C++ STL, we need to include the <stack> header.

¶Functions in C++ STL Stack

• empty() Checks if the stack is empty. Returns true if the stack has no elements; otherwise, returns false.
  
• size() Returns the number of elements in the stack.
  
• push() Adds an element to the top of the stack.
  
• pop()Removes the top element from the stack.
• top() Provides access to the top element without removing it. Retrieves a reference to the top element.
  

Here’s a simple example that demonstrates how to declare a stack, push elements onto it, pop elements from it, and perform other common operations:

#include <iostream>
#include <stack>

int main() {
   // Declare a stack of integers
   std::stack<int> myStack;

   // Push elements onto the stack
   myStack.push(10);
   myStack.push(20);
   myStack.push(30);

   // Display the size of the stack
   std::cout << "Size of the stack: " << myStack.size() << std::endl;

   // Access the top element without removing it
   std::cout << "Top element: " << myStack.top() << std::endl;

   // Pop elements from the stack
   myStack.pop();

   // Check if the stack is empty
   if (myStack.empty()) {
       std::cout << "The stack is empty." << std::endl;
   } else {
       std::cout << "The stack is not empty." << std::endl;
   }

   return 0;
}

¶Applications of Stack

• Function Call Management: Stacks are used to manage function calls in programming languages. When a function is called, its context is pushed onto the stack, and when the function completes, its context is popped off.

• Expression Evaluation: Stacks help in evaluating expressions, especially arithmetic expressions. They are used to convert infix expressions to postfix or prefix form, making them easier to evaluate.

• Undo Mechanisms in Software: Stacks are employed to implement undo functionalities in software applications. Each action performed is pushed onto the stack, allowing easy reversal of operations.

• Memory Management: Stacks are used in memory management to keep track of allocated memory. Local variables and function call information are stored on the stack during program execution.

• Backtracking Algorithms: Stacks are instrumental in backtracking algorithms. They store the state of the system at different decision points, allowing the algorithm to backtrack when needed.

• Browser History Implementation: Stacks can be used to implement the back and forward buttons in web browsers. Each visited page is pushed onto the stack, allowing easy navigation.

• Parentheses Matching: Stacks are employed to check the correctness of parentheses in expressions. Each opening parenthesis is pushed onto the stack, and when a closing parenthesis is encountered, it is matched with the top element.

¶Infix to Postfix Expression Conversion Using Stack

Infix to postfix conversion involves converting an infix expression to a postfix expression using a stack. Here’s a basic algorithm and explanation of how to perform infix to postfix conversion using a stack:

Let’s convert the infix expression "3 + 5 * ( 2 - 8 )" to postfix:

• Scan from left to right:

1. Operand 3, add to postfix.
2. Operator +, push onto stack.
3. Operand 5, add to postfix.
4. Operator *' push onto stack.
5. Open parenthesis (, push onto stack.
6. Operand 2, add to postfix.
7. Operator ‘-’, push onto stack.
8. Operand 8, add to postfix.
9. Close parenthesis ‘)’, pop operators and add to postfix until ( is encountered.
10. Pop *, add to postfix.
11. Pop + add to postfix.
12. Postfix expression: "3 5 2 8 - * +"

This postfix expression is equivalent to the original infix expression “3 + 5 * ( 2 - 8 )”.

#include <iostream>
#include <stack>
#include <cctype>

bool isOperator(char ch) {
    return (ch == '+' || ch == '-' || ch == '*' || ch == '/');
}

int getPrecedence(char op) {
    if (op == '+' || op == '-') {
        return 1;
    } else if (op == '*' || op == '/') {
        return 2;
    }
    return 0;  // For '('
}

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

    for (char ch : infix) {
        if (std::isalnum(ch)) {
            postfix += ch;  // Operand, add to postfix
        } else if (isOperator(ch)) {
            while (!operatorStack.empty() && getPrecedence(operatorStack.top()) >= getPrecedence(ch)) {
                postfix += operatorStack.top();
                operatorStack.pop();
            }
            operatorStack.push(ch);
        } else if (ch == '(') {
            operatorStack.push(ch);
        } else if (ch == ')') {
            while (!operatorStack.empty() && operatorStack.top() != '(') {
                postfix += operatorStack.top();
                operatorStack.pop();
            }
            operatorStack.pop();  // Discard '('
        }
    }

    // Pop remaining operators from the stack
    while (!operatorStack.empty()) {
        postfix += operatorStack.top();
        operatorStack.pop();
    }

    return postfix;
}

int main() {
    std::string infixExpression = "3 + 5 * ( 2 - 8 )";
    std::string postfixExpression = infixToPostfix(infixExpression);
    std::cout << "Infix Expression: " << infixExpression << std::endl;
    std::cout << "Postfix Expression: " << postfixExpression << std::endl;

    return 0;
}

¶Run C Programming Online Compiler

To make your learning more effective, exercise the coding examples in the text editor below.