Demystifying Stacks in Data Structures and Crafting a Stack in C++

Introduction:

Hello, dear readers! Join me on this exciting journey through the realm of data structures as we unveil the secrets of stacks. We'll not only explore the theoretical foundations of stacks but also roll up our sleeves and delve into the practical side by creating our very own stack data structure using C++. Understanding stacks is a fundamental skill for any budding programmer, so let's get started on this educational adventure.

Getting to Know Stacks:

Before we get our hands dirty with code, let's take a moment to grasp the concept of stacks and why they are indispensable in computer science and programming. A stack is a linear data structure that adheres to the Last-In, First-Out (LIFO) principle. Think of it as a stack of trays in a cafeteria – the last tray placed is the first one to be removed. In a stack, elements are added and removed from a single end, known as the top of the stack. This unique behavior makes stacks a versatile and powerful tool in various computer science applications.

The ABCs of Stack Operations:

Stacks are all about two fundamental operations:

Push: This operation involves adding an element to the top of the stack. Imagine it as placing a new tray on top of the stack of trays.
Pop: The pop operation removes the top element from the stack, just like picking up the top tray from the stack.

Moreover, stacks can offer additional operations such as:

Peek (or Top): This operation allows you to view the element at the top of the stack without removing it.
isEmpty: This operation checks whether the stack is empty or not.

Stacks in Action:

Stacks find applications in a multitude of scenarios, including:

Expression Evaluation: Stacks are employed to evaluate mathematical expressions like arithmetic expressions by maintaining the correct order of operators and operands.
Function Calls: Stacks are crucial for managing function calls and keeping track of the function call hierarchy in programming.
Backtracking: In algorithms like depth-first search (DFS), stacks are used to maintain a record of visited nodes and backtrack when necessary.

Implementation of stack method 1 (coding)

// C Program for Implementation of stack (array) using structure
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>

// A structure to represent a stack
struct Stack {
    int top;
    int maxSize;
    int* array;
};

struct Stack* create(int max)
{
    struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));
    stack->maxSize = max;
    stack->top = -1;
    stack->array = (int*)malloc(stack->maxSize * sizeof(int));
    //here above memory for array is being created
    // size would be 10*4 = 40
    return stack;
}

// Checking with this function is stack is full or not
// Will return true is stack is full else false
//Stack is full when top is equal to the last index
int isFull(struct Stack* stack)
{
    if (stack->top == stack->maxSize - 1) {
        printf("Will not be able to push maxSize reached\n");
    }
    // Since array starts from 0, and maxSize starts from 1
    return stack->top == stack->maxSize - 1;
}

// By definition the Stack is empty when top is equal to -1
// Will return true if top is -1
int isEmpty(struct Stack* stack)
{
    return stack->top == -1;
}

// Push function here, inserts value in stack and increments stack top by 1
void push(struct Stack* stack, int item)
{
    if (isFull(stack))
        return;
    stack->array[++stack->top] = item;
    printf("We have pushed %d to stack\n", item);
}

// Function to remove an item from the stack.  It decreases top by 1
int pop(struct Stack* stack)
{
    if (isEmpty(stack))
        return INT_MIN;
    return stack->array[stack->top--];
}

// Function to return the top from stack without removing it
int peek(struct Stack* stack)
{
    if (isEmpty(stack))
        return INT_MIN;
    return stack->array[stack->top];
}
int size(struct Stack* stack) {
    return (stack->top + 1);
}

int main()
{
    struct Stack* stack = create(10);

    push(stack, 5);
    push(stack, 10);
    push(stack, 15);
    printf("%d\n", peek(stack));
    printf("%d\n", size(stack));
    printf("%d\n", pop(stack));
    printf("%d\n", size(stack));
    printf("%d\n", isFull(stack));
    printf("%d\n", isEmpty(stack));

    return 0;


}

This C program demonstrates the implementation of a stack using an array and a structure. A stack is a linear data structure that follows the Last-In, First-Out (LIFO) principle, meaning the last element added to the stack will be the first one to be removed. In this program, a stack is created using a structure and supports fundamental stack operations, including push, pop, peek, checking if the stack is full, and checking if it is empty.

Let me break down the program step by step:

First, the necessary header files are included, which are <limits.h> for defining the constant INT_MIN, <stdio.h> for standard input and output, and <stdlib.h> for dynamic memory allocation functions.
The program defines a structure called Stack, which has the following members:
- top: an integer that represents the current top of the stack.
- maxSize: an integer indicating the maximum size of the stack.
- array: a pointer to an integer array that holds the stack elements.
The create function is responsible for creating a stack. It dynamically allocates memory for the stack structure and the array based on the specified maximum size (max). The top is initialized to -1, indicating an empty stack. The array is allocated to hold the elements. The create function returns a pointer to the created stack.
The isFull function checks if the stack is full. It returns true if the top is equal to maxSize - 1, indicating that the stack is full. If the stack is full, a message is printed, but the program continues to check if the stack is full by returning a boolean value.
The isEmpty function checks if the stack is empty by examining if the top is equal to -1. It returns true if the stack is empty.
The push function is responsible for adding an item to the stack. It first checks if the stack is full using the isFull function. If not, it increments the top and assigns the provided item to the corresponding index in the array.
The pop function removes an item from the stack and returns it. It first checks if the stack is empty using the isEmpty function. If the stack is not empty, it returns the item at the current top of the stack and then decrements the top.
The peek function returns the top item from the stack without removing it. It first checks if the stack is empty using the isEmpty function. If the stack is not empty, it returns the item at the current top of the stack.
The size function returns the number of elements in the stack, which is equal to top + 1.
In the main function, a stack with a maximum size of 10 is created using the create function.
Elements (5, 10, and 15) are pushed onto the stack using the push function.
The peek function is used to retrieve the top element (15) without removing it and print it.
The size function is used to determine the current size of the stack and print it.
The pop function is used to remove the top element (15) and print it.
The size function is used again to show the updated size of the stack after the pop operation.
The isFull and isEmpty functions are used to check whether the stack is full and empty, respectively. The results are printed.
The program concludes by returning 0, indicating successful execution.

This program demonstrates the essential operations of a stack data structure using an array and is a great starting point for understanding stack implementation in C.

this C program provides a practical implementation of a stack data structure using an array and a structure. It allows us to perform basic stack operations, such as push, pop, peek, and checking if the stack is full or empty.

By studying this program, I have gained valuable insights into the fundamental principles of stack data structures. I've learned how to create and manipulate a stack in C++, which is a foundational concept in computer science and programming. Understanding data structures like stacks is essential for solving a wide range of computational problems efficiently.

As you progress in my programming journey, I find that stacks are used in numerous real-world applications, such as expression evaluation, function call management, and backtracking algorithms. This program serves as a solid starting point for building our knowledge and expertise in data structures and C programming. Happy coding!