C Programming Data Structures Stack Implementation Array And Linked List Complete Guide

Stack Implementation in C: Array vs. Linked List

Introduction to Stacks

A stack is a linear data structure that operates on the Last-In-First-Out (LIFO) principle. This means that the last element added to the stack will be the first one to be removed. Stacks are commonly used in scenarios like function call management, undo mechanisms, parsing expressions, and more.

Stack Operations

Regardless of the underlying implementation (array or linked list), a stack typically supports the following operations:

1. Push: Adds an element to the top of the stack.
2. Pop: Removes and returns the top element of the stack.
3. Peek/Top: Returns the top element without removing it.
4. IsEmpty: Checks if the stack is empty.
5. IsFull (applicable to array implementation): Checks if the stack is full.

Stack Implementation Using Arrays

Advantages of Array Implementation

• Fixed Size: Easy to implement with a predefined size.
• Memory Efficiency: Elements are stored contiguously in memory, which can lead to cache-friendly access patterns.
• Simplicity: The implementation is straightforward and involves basic array operations.

Disadvantages of Array Implementation

• Fixed Size Limitation: Once the array is full, it cannot dynamically resize without additional operations.
• Wasted Space: If the stack size is significantly larger than needed, memory space is wasted.

Array-Based Stack Implementation

Here's a simple C program demonstrating a stack using an array:

#include <stdio.h>
#include <stdlib.h>
#include <limits.h> // For INT_MIN

#define MAX_SIZE 100 // Maximum size of the stack

typedef struct {
    int items[MAX_SIZE];
    int top;
} Stack;

// Function to initialize the stack
void initStack(Stack *s) {
    s->top = -1;
}

// Function to check if the stack is empty
int isEmpty(Stack *s) {
    return s->top == -1;
}

// Function to check if the stack is full
int isFull(Stack *s) {
    return s->top == MAX_SIZE - 1;
}

// Function to push an element onto the stack
void push(Stack *s, int item) {
    if (isFull(s)) {
        printf("Stack is full! Cannot push %d.\n", item);
        return;
    }
    s->items[++s->top] = item;
}

// Function to pop an element from the stack
int pop(Stack *s) {
    if (isEmpty(s)) {
        printf("Stack is empty! Cannot pop.\n");
        return INT_MIN;
    }
    return s->items[s->top--];
}

// Function to get the top element of the stack
int peek(Stack *s) {
    if (isEmpty(s)) {
        printf("Stack is empty! Cannot peek.\n");
        return INT_MIN;
    }
    return s->items[s->top];
}

// Function to display the stack elements
void display(Stack *s) {
    if (isEmpty(s)) {
        printf("Stack is empty!\n");
        return;
    }
    printf("Stack elements: ");
    for (int i = 0; i <= s->top; i++) {
        printf("%d ", s->items[i]);
    }
    printf("\n");
}

int main() {
    Stack s;
    initStack(&s);

    push(&s, 10);
    push(&s, 20);
    push(&s, 30);
    display(&s); // Stack elements: 10 20 30

    printf("Top element: %d\n", peek(&s)); // Top element: 30

    pop(&s);
    display(&s); // Stack elements: 10 20

    return 0;
}

Stack Implementation Using Linked Lists

Advantages of Linked List Implementation

• Dynamic Size: Can grow or shrink as needed without a predefined limit.
• No Wasted Space: Memory usage is proportional to the number of elements.
• Flexibility: Easier to insert and delete elements at any position, though not typically used for these operations in a stack.

Disadvantages of Linked List Implementation

• Additional Memory Overhead: Each node requires extra space for the pointer to the next node.
• Slower Access: Elements are not contiguous, leading to increased cache misses and potential performance degradation.

Linked List-Based Stack Implementation

Below is a C program demonstrating a stack using a singly linked list:

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

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

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

// Function to create a new node
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (!newNode) {
        printf("Memory allocation failed!\n");
        exit(1);
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// Function to initialize the stack
void initStack(Stack *s) {
    s->top = NULL;
}

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

// Function to push an element onto the stack
void push(Stack *s, int item) {
    Node* newNode = createNode(item);
    newNode->next = s->top;
    s->top = newNode;
}

// Function to pop an element from the stack
int pop(Stack *s) {
    if (isEmpty(s)) {
        printf("Stack is empty! Cannot pop.\n");
        return INT_MIN;
    }
    Node* temp = s->top;
    int poppedData = temp->data;
    s->top = s->top->next;
    free(temp);
    return poppedData;
}

// Function to get the top element of the stack
int peek(Stack *s) {
    if (isEmpty(s)) {
        printf("Stack is empty! Cannot peek.\n");
        return INT_MIN;
    }
    return s->top->data;
}

// Function to display the stack elements
void display(Stack *s) {
    if (isEmpty(s)) {
        printf("Stack is empty!\n");
        return;
    }
    Node* temp = s->top;
    printf("Stack elements: ");
    while (temp) {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}

int main() {
    Stack s;
    initStack(&s);

    push(&s, 10);
    push(&s, 20);
    push(&s, 30);
    display(&s); // Stack elements: 30 20 10

    printf("Top element: %d\n", peek(&s)); // Top element: 30

    pop(&s);
    display(&s); // Stack elements: 20 10

    return 0;
}

Comparative Analysis

| Feature | Array Implementation | Linked List Implementation | |------------------|-----------------------------------------|-----------------------------------------| | Size | Fixed size (predefined) | Dynamic size (grows and shrinks) | | Memory Usage | Efficient, contiguous memory | Inefficient due to pointers | | Access Time | Fast access time | Slower due to non-contiguous memory | | Flexibility | Limited flexibility | Highly flexible due to dynamic resizing | | Ease of Use | Simpler and faster for small data sets | More complex but offers better scalability|

Choosing Between Array and Linked List Implementations

• Use Arrays when you have a known, fixed size for your stack and prioritize memory efficiency.
• Use Linked Lists when you need a stack that can dynamically grow and shrink, and memory is not a critical concern.

Conclusion

Understanding how to implement stacks using both arrays and linked lists is essential for developers, especially when optimizing performance and resource usage based on specific requirements. While arrays offer simplicity and efficiency, linked lists provide flexibility and dynamic resizing capabilities, making them suitable for varying use cases.