Implementing Stack Data Structure in C: A Practical Approach

Table of Contents

1. Fundamental Concepts of Stacks
2. Implementing a Stack in C
   • Array - Based Stack
   • Linked List - Based Stack
3. Usage Methods
4. Common Practices
5. Best Practices
6. Conclusion
7. References

Fundamental Concepts of Stacks

A stack has two main operations:

• Push: This operation adds an element to the top of the stack. If the stack is full, it is said to be in an overflow state.
• Pop: This operation removes the top - most element from the stack. If the stack is empty, it is said to be in an underflow state.

Other useful operations include:

• Peek: This operation returns the top - most element of the stack without removing it.
• isEmpty: Checks if the stack is empty.
• isFull: Checks if the stack is full (only applicable for array - based stacks).

Implementing a Stack in C

Array - Based Stack

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

#define MAX_SIZE 100

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

// Function to initialize the stack
void initialize(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 value) {
    if (isFull(s)) {
        printf("Stack overflow\n");
        return;
    }
    s->items[++(s->top)] = value;
}

// Function to pop an element from the stack
int pop(Stack *s) {
    if (isEmpty(s)) {
        printf("Stack underflow\n");
        return -1;
    }
    return s->items[(s->top)--];
}

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

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

    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;
}

Linked List - Based Stack

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

// Structure for a node in the linked list
typedef struct Node {
    int data;
    struct Node *next;
} Node;

// Structure for the stack
typedef struct {
    Node *top;
} Stack;

// Function to initialize the stack
void initialize(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 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 (isEmpty(s)) {
        printf("Stack underflow\n");
        return -1;
    }
    Node *temp = s->top;
    int value = temp->data;
    s->top = s->top->next;
    free(temp);
    return value;
}

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

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

    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;
}

Usage Methods

• Expression Evaluation: Stacks can be used to evaluate postfix or prefix expressions. For example, in postfix expression evaluation, operands are pushed onto the stack, and when an operator is encountered, the appropriate number of operands are popped from the stack, the operation is performed, and the result is pushed back onto the stack.
• Backtracking: In algorithms like maze - solving or the N - Queens problem, stacks can be used to keep track of the path taken so far. If a dead - end is reached, the last decision can be popped from the stack and a different path can be explored.

Common Practices

• Error Handling: Always check for stack overflow and underflow conditions when performing push and pop operations. This helps prevent unexpected behavior in your program.
• Initialization: Initialize the stack properly before using it. For array - based stacks, set the top pointer to - 1, and for linked - list - based stacks, set the top pointer to NULL.

Best Practices

• Modularity: Separate the stack operations into functions. This makes the code more organized and easier to maintain.
• Memory Management: In linked - list - based stacks, make sure to free the memory of the popped nodes to avoid memory leaks.

Conclusion

Implementing a stack data structure in C is a fundamental skill for any programmer. We have explored two common ways to implement a stack: using an array and using a linked list. Each method has its own advantages and disadvantages. Array - based stacks are simple and have constant - time access, but they have a fixed size. Linked - list - based stacks can grow dynamically but require more memory management.

By understanding the basic operations, usage methods, common practices, and best practices, you can effectively use stacks in your C programs to solve a wide range of problems.

References

• “Introduction to Algorithms” by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.
• “Data Structures and Algorithms in C” by Adam Drozdek.

You can run the provided code examples to see the stack in action and experiment with different operations to gain a better understanding.