Stack

A stack is a linear data structure that follows the Last In, First Out (LIFO) principle, where the last element added to the stack is the first one to be removed. It can be thought of as a collection of elements with two main operations: push, which adds an element to the top of the stack, and pop, which removes the top element from the stack.

Implementation

Stacks can be implemented using arrays or linked lists.

1. Array Implementation:
   • An array can be used to represent a stack by keeping track of the top element's index.
   • Operations like push and pop can be performed by updating the top index accordingly.

#define MAX_SIZE 100 // Maximum size of the stack

typedef struct {
    int arr[MAX_SIZE];
    int top; // Index of the top element
} Stack;

// Function to initialize a stack
void initializeStack(Stack *s) {
    s->top = -1; // Empty stack
}

// Function to push an element onto the stack
void push(Stack *s, int value) {
    if (s->top == MAX_SIZE - 1) {
        printf("Stack Overflow!\n");
        return;
    }
    s->arr[++s->top] = value;
}

// Function to pop an element from the stack
int pop(Stack *s) {
    if (s->top == -1) {
        printf("Stack Underflow!\n");
        return -1; // Returning a default value
    }
    return s->arr[s->top--];
}

2. Linked List Implementation:
   • A linked list can also be used to implement a stack, where each node stores an element and a pointer to the next node.
   • Push and pop operations involve adding or removing nodes at the beginning (top) of the linked list.

typedef struct Node {
    int data;
    struct Node* next;
} Node;

typedef struct {
    Node* top; // Pointer to the top node
} Stack;

// Function to initialize a stack
void initializeStack(Stack *s) {
    s->top = NULL; // Empty stack
}

// Function to push an element onto the stack
void push(Stack *s, int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("Memory allocation failed!\n");
        return;
    }
    newNode->data = value;
    newNode->next = s->top;
    s->top = newNode;
}

// Function to pop an element from the stack
int pop(Stack *s) {
    if (s->top == NULL) {
        printf("Stack Underflow!\n");
        return -1; // Returning a default value
    }
    int data = s->top->data;
    Node* temp = s->top;
    s->top = s->top->next;
    free(temp);
    return data;
}

Operations

Common operations performed on stacks include:

• Push: Adds an element to the top of the stack.
• Pop: Removes the top element from the stack.
• Peek/Top: Retrieves the top element without removing it.
• isEmpty: Checks if the stack is empty.
• isFull: Checks if the stack is full (for array implementation).

Advantages of Stacks

• Simple and easy to implement.
• Efficient for certain algorithms and applications such as function calls, expression evaluation, and backtracking.

Disadvantages of Stacks

• Limited functionality compared to other data structures like queues or lists.
• Fixed size in array implementation, leading to potential overflow or underflow issues.

Applications of Stacks

• Function Call Management: Stacks are used to manage function calls in programming languages, storing return addresses and local variables.
• Expression Evaluation: Stacks are used to evaluate postfix, infix, and prefix expressions.
• Backtracking Algorithms: Stacks are utilized in backtracking algorithms like depth-first search (DFS).
• Undo Mechanisms: Stacks are employed in software applications to implement undo operations.
• Memory Management: Stacks are used in memory management systems for call stack allocation.

Examples of Stack Usage

• Parentheses Matching: Checking if parentheses in an expression are properly balanced.
• Reverse Polish Notation (RPN): Evaluating mathematical expressions in postfix notation.
• Function Call Stack: Managing function calls and return addresses during program execution.