Stack in Data Structure: The Ultimate Guide

In the realm of computer science, a stack is a fundamental data structure that follows the principle of Last In First Out (LIFO). It operates on the concept of a pile of items, where the last item added is the first one to be removed. The stack data structure is widely used in various programming languages and plays a crucial role in many algorithms and applications.

What is a Stack?

A stack is a linear data structure that follows a particular order in which operations are performed: Last In First Out (LIFO). This means that the last element added to the stack will be the first element removed.

Key Operations:

Push: To add an item to the top.
Pop: To remove the topmost item.
Peek/Top: To get the topmost item without popping it.

Why Use an Array to Implement a Stack?

Arrays provide a simple and effective way to create a stack. Their fixed size makes memory management straightforward, and the contiguous memory allocation ensures efficient access. However, a primary limitation is that the size of the stack is fixed once declared. For applications requiring dynamic resizing, linked-list implementations might be more appropriate.

Implementation of Stack using Array in C:

Let’s look at a simple code illustration:

#include <stdio.h>
#define MAX_SIZE 10

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

int isFull() {
    return top == MAX_SIZE - 1;
}

int isEmpty() {
    return top == -1;
}

void push(int data) {
    if (!isFull()) {
        stack[++top] = data;
    } else {
        printf("Stack overflow!\n");
    }
}

int pop() {
    if (!isEmpty()) {
        return stack[top--];
    } else {
        printf("Stack underflow!\n");
        return -1; 
    }
}

int peek() {
    if (!isEmpty()) {
        return stack[top];
    } else {
        printf("Stack is empty!\n");
        return -1;
    }
}

int main() {
    push(5);
    push(10);
    push(15);

    printf("Top element is %d\n", peek());
    printf("Popped element is %d\n", pop());
    printf("Top element after pop is %d\n", peek());

    return 0;
}

Code Explanation:

The array stack of sizes MAX_SIZE will store our stack elements.
top is initialized to -1, indicating an empty stack.
isFull() and isEmpty() are utility functions to check if the stack is full or empty.
The push() the function adds an element to the stack if there is space.
The pop() the function removes the topmost element and returns it.
The peek() the function returns the topmost element without removing it.

Illustration of Stack Operations:

Imagine the stack as a stack of books. In the beginning, there’s no book (top = -1).

Push Operation (push(5)): A book with the label ‘5’ is placed on the table.
Push Operation (push(10)): Another book labeled ’10’ is placed on top of the ‘5’ book.
Push Operation (push(15)): A third book labeled ’15’ is placed on top. This is now the topmost book.
Peek Operation (peek()): You check the label of the topmost book without removing it. It’s ’15’.
Pop Operation (pop()): You take away the topmost book (label ’15’). The next book in line (’10’) becomes the topmost.
Peek Operation (peek()): Now, you check the label of the topmost book. It’s ’10’.

Implementing Stack with Linked List

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

// Define the Node structure
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// Define the Stack structure
typedef struct Stack {
    Node* top;
} Stack;

// Create a new node
Node* newNode(int data) {
    Node* temp = (Node*)malloc(sizeof(Node));
    temp->data = data;
    temp->next = NULL;
    return temp;
}

// Initialize a new stack
Stack* createStack() {
    Stack* s = (Stack*)malloc(sizeof(Stack));
    s->top = NULL;
    return s;
}

// Push an item onto the stack
void push(Stack* s, int data) {
    Node* temp = newNode(data);
    temp->next = s->top;
    s->top = temp;
}

// Pop an item from the stack
int pop(Stack* s) {
    if (s->top == NULL) {
        printf("Stack is empty!\n");
        return -1; // Indicating the stack is empty
    }

    Node* temp = s->top;
    int data = temp->data;

    s->top = s->top->next;
    free(temp);

    return data;
}

// Get the top item of the stack without popping
int peek(Stack* s) {
    if (s->top == NULL) {
        printf("Stack is empty!\n");
        return -1; 
    }
    return s->top->data;
}

// Check if the stack is empty
int isEmpty(Stack* s) {
    return s->top == NULL;
}

int main() {
    Stack* s = createStack();

    push(s, 10);
    push(s, 20);
    push(s, 30);

    printf("Top element: %d\n", peek(s));
    printf("Popped element: %d\n", pop(s));
    printf("Top element after pop: %d\n", peek(s));

    return 0;
}

Advantages and Limitations:

Advantages:

Direct access to the topmost element with O(1) complexity.
Memory allocation is straightforward, ensuring efficient access.

Limitations:

The size of the stack is fixed. If the stack exceeds its capacity, we’ll encounter a “Stack Overflow”.
Similarly, if you try to pop an element from an empty stack, it will result in a “Stack Underflow”.

Applications of Stack

Stacks find applications in a wide range of scenarios, including:

Expression Evaluation: Stacks are commonly used to evaluate arithmetic expressions, such as infix, postfix, and prefix expressions.
Function Call Stack: During the execution of a program, the stack is used to keep track of function calls and their corresponding return addresses.
Memory Management: Stacks play a crucial role in managing memory in computer systems, including managing function calls, local variables, and dynamic memory allocation.
Undo-Redo Operations: Stacks are utilized to implement undo and redo functionalities in software applications.
Parsing and Syntax Analysis: Stacks are employed in parsing and syntax analysis of programming languages to check for correct syntax and enforce proper language rules.
Backtracking Algorithms: Backtracking algorithms often rely on stacks to keep track of the search space and to efficiently explore different paths.
Browser History: Web browsers use stacks to implement the forward and backward navigation functionalities by maintaining a history of visited web pages.
Operating System Tasks: Stacks are used in operating systems for tasks such as managing system calls, interrupt handling, and maintaining process information.

These are just a few examples of the vast range of applications where stacks are employed to solve complex problems efficiently.

Time and Space Complexity of Stack

Array-based Implementation:

Time Complexity:

Push (Insertion): O(1) – Directly inserts at the top of the array.
Pop (Deletion): O(1) – Directly deletes from the top of the array.
Peek (Top element): O(1) – Direct access to the top of the stack using the top index.
isEmpty or isFull checks: O(1) – Checks the top index against predefined constants or values.

Space Complexity:

O(n) – The entire array reserves space even if the stack utilizes only a part of it. Here, n is the predefined size of the array.

Linked List-based Implementation:

Time Complexity:

Push (Insertion): O(1) – Inserts at the head (top) of the linked list.
Pop (Deletion): O(1) – Deletes from the head (top) of the linked list.
Peek (Top element): O(1) – Direct access to the head of the linked list (which is the top of the stack).
isEmpty checks: O(1) – Checks if the head (top) is null.

Space Complexity:

O(n) – Each node in the linked list consumes space for its data and a pointer/reference to the next node. Here, n refers to the number of items in the stack.

For both implementations, the primary operations (push, pop, and peek) occur in constant time, O(1). The space complexities differ based on overhead. In the array-based implementation, memory allocation is static, and unused portions of the array can’t be utilized by other parts of the program. In the linked-list version, each entry requires additional space for the pointer/reference, but it can grow or shrink dynamically.

the best implementation to use depends on the specific requirements and constraints of your application. If you have a good estimate of the maximum size the stack will ever need to be, an array might be more efficient. If you need dynamic resizing and can afford the extra overhead of pointers, a linked list might be preferable.

Conclusion

In conclusion, the stack is a fundamental data structure in computer science that follows the Last In First Out (LIFO) principle. It allows efficient insertion and deletion of elements, making it a valuable tool for various algorithms and applications. By implementing stacks using arrays or other data structures and utilizing the basic stack operations, developers can manage and manipulate data in a structured and organized manner. Understanding the concepts and applications of stacks is crucial for any programmer or computer science enthusiast, as it forms the building blocks of many advanced data structures and algorithms.