by Jasleen Chhabra | Updated on 24 August 2024

Stacks are one of the most fundamental data structures in computer science. They follow a Last In, First Out (LIFO) principle, which means the last element added to the stack will be the first one to be removed. This characteristic makes stacks incredibly useful for a variety of applications, from algorithm implementation to managing function calls in programming languages.

What is a Stack?

A stack is an abstract data type that serves as a collection of elements with two primary operations:

• Push: Adds an element to the top of the stack.
• Pop: Removes the element from the top of the stack.

Stacks can also include other operations such as:

• Peek/Top: Returns the top element of the stack without removing it.
• isEmpty: Checks if the stack is empty.
• isFull: Checks if the stack is full (in the case of a stack with a fixed size).

Characteristics of Stacks

1. LIFO Principle: The most recently added element is the first to be removed.
2. Dynamic Nature: Stacks can grow and shrink dynamically, depending on the operations performed.
3. Memory Management: Stacks are used for managing memory in recursive function calls and in the evaluation of expressions.

Applications of Stacks

Stacks are versatile and can be used in various applications, including:

• Expression Evaluation: Infix, postfix (Reverse Polish Notation), and prefix expressions.
• Backtracking: Used in algorithms like maze solving and navigating through search trees.
• Function Call Management: Managing the sequence of function calls and local variables.
• Undo Mechanisms: Implementing undo features in text editors and other software applications.
• Syntax Parsing: Parsing nested structures like parentheses, HTML/XML tags, and more.

Basic Operations on Stacks

Push Operation

The push operation adds an element to the top of the stack. If the stack is implemented using an array, it involves:

1. Incrementing the top index.
2. Adding the new element at the top index position.

Pop Operation

The pop operation removes the top element from the stack. If the stack is implemented using an array, it involves:

1. Returning the element at the top index.
2. Decrementing the top index.

Stack Implementation

Stacks can be implemented using arrays or linked lists. Here, we'll demonstrate a stack implementation using arrays in C++.

C++ Implementation of Stack Using Arrays

#include <iostream>
#define MAX 1000

class Stack {
    int top;

public:
    int arr[MAX]; // Maximum size of Stack

    Stack() { top = -1; }
    bool push(int x);
    int pop();
    int peek();
    bool isEmpty();
};

bool Stack::push(int x) {
    if (top >= (MAX - 1)) {
        std::cout << "Stack Overflow" << std::endl;
        return false;
    } else {
        arr[++top] = x;
        std::cout << x << " pushed into stack" << std::endl;
        return true;
    }
}

int Stack::pop() {
    if (top < 0) {
        std::cout << "Stack Underflow" << std::endl;
        return 0;
    } else {
        int x = arr[top--];
        return x;
    }
}

int Stack::peek() {
    if (top < 0) {
        std::cout << "Stack is Empty" << std::endl;
        return 0;
    } else {
        int x = arr[top];
        return x;
    }
}

bool Stack::isEmpty() {
    return (top < 0);
}

int main() {
    Stack stack;
    stack.push(10);
    stack.push(20);
    stack.push(30);
    std::cout << stack.pop() << " popped from stack" << std::endl;

    std::cout << "Top element is " << stack.peek() << std::endl;
    std::cout << "Stack empty: " << (stack.isEmpty() ? "true" : "false") << std::endl;

    return 0;
}

Conclusion

Stacks are a simple yet powerful data structure that provides an efficient way to manage data in a LIFO manner. They are widely used in various applications, from basic algorithm implementation to complex memory management in programming languages. Understanding how to implement and use stacks effectively can greatly enhance your problem-solving skills and efficiency in programming.

---