Pop Operation on Stack in DSA C

Mental Model

A stack is like a pile of plates where you only remove the top plate. Pop means taking off the top item.

Analogy: Imagine a stack of books on a table. You can only take the top book off first, not the ones below it.

Top
 ↑
[3] -> [2] -> [1] -> null
Bottom

Dry Run Walkthrough

Input: stack: 3 -> 2 -> 1 -> null, pop operation

Goal: Remove the top element (3) from the stack and update the top pointer

Step 1: Check if stack is empty

Top -> [3] -> [2] -> [1] -> null

Why: We must ensure there is something to pop

Step 2: Save top element (3) to return later

Top -> [3] -> [2] -> [1] -> null

Why: We need to know which element is being removed

Step 3: Move top pointer to next element (2)

Top -> [2] -> [1] -> null

Why: Removing the top means the next element becomes the new top

Step 4: Return saved element (3) as popped value

Top -> [2] -> [1] -> null

Why: Pop operation outputs the removed top element

Result:

Top -> [2] -> [1] -> null
Popped element: 3

Annotated Code

DSA C

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

// Node structure for stack
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// Push function to add element to stack
void push(Node** top_ref, int new_data) {
    Node* new_node = (Node*)malloc(sizeof(Node));
    new_node->data = new_data;
    new_node->next = *top_ref;
    *top_ref = new_node;
}

// Pop function to remove top element from stack
int pop(Node** top_ref) {
    if (*top_ref == NULL) {
        printf("Stack Underflow\n");
        return -1; // Indicate empty stack
    }
    Node* temp = *top_ref; // Save top node
    int popped = temp->data; // Save data to return
    *top_ref = temp->next; // Move top to next node
    free(temp); // Free old top node
    return popped; // Return popped data
}

// Print stack from top to bottom
void printStack(Node* top) {
    Node* current = top;
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("null\n");
}

int main() {
    Node* stack = NULL;
    push(&stack, 1);
    push(&stack, 2);
    push(&stack, 3);

    printf("Stack before pop: ");
    printStack(stack);

    int popped = pop(&stack);
    printf("Popped element: %d\n", popped);

    printf("Stack after pop: ");
    printStack(stack);

    return 0;
}

if (*top_ref == NULL) {

Check if stack is empty to avoid popping from empty stack

Node* temp = *top_ref; // Save top node

Save current top node to remove it safely

int popped = temp->data; // Save data to return

Store the data of the top node to return after removal

*top_ref = temp->next; // Move top to next node

Update top pointer to next node, effectively removing top

free(temp); // Free old top node

Free memory of removed node to avoid leaks

return popped; // Return popped data

Return the value popped from the stack

Output

Stack before pop: 3 -> 2 -> 1 -> null

Popped element: 3

Stack after pop: 2 -> 1 -> null

Complexity Analysis

Time: O(1) because pop removes only the top element without traversal

Space: O(1) as no extra space is needed besides temporary variables

vs Alternative: Compared to array-based stack pop which is also O(1), linked list pop avoids resizing issues

Edge Cases

Empty stack

Prints 'Stack Underflow' and returns -1 to indicate no element to pop

DSA C

if (*top_ref == NULL) {

Single element stack

Pops the only element and sets top to NULL, resulting in empty stack

DSA C

*top_ref = temp->next;

When to Use This Pattern

When you see a problem requiring last-in-first-out removal, reach for the pop operation on stack because it removes the top element efficiently.

Common Mistakes

Mistake: Not checking if the stack is empty before popping
Fix: Add a condition to check if top is NULL before removing to avoid errors

Mistake: Not updating the top pointer after popping
Fix: Set top to next node after removing the current top to maintain stack integrity

Summary

Removes the top element from the stack and returns it.

Use when you need to retrieve and remove the most recently added item.

The key is to update the top pointer to the next element after removal.