Stacks in C Language

Introduction to Stacks

A stack is a linear data structure that follows the Last In First Out (LIFO) principle. The element that is added last is the first one to be removed. Stacks are used in various applications such as function call management, expression evaluation, and backtracking algorithms.

Basic Operations

Stacks support the following primary operations:

• Push: Adds an element to the top of the stack.
• Pop: Removes the element from the top of the stack.
• Peek: Returns the top element of the stack without removing it.
• IsEmpty: Checks if the stack is empty.
• IsFull: Checks if the stack is full (in case of a bounded stack).

Implementation of Stack in C

Below is a simple implementation of a stack using an array in C.

#include <stdio.h>
#define MAX 10

typedef struct {
    int data[MAX];
    int top;
} Stack;

void initialize(Stack *s) {
    s->top = -1;
}

int isFull(Stack *s) {
    return s->top == MAX - 1;
}

int isEmpty(Stack *s) {
    return s->top == -1;
}

void push(Stack *s, int value) {
    if (isFull(s)) {
        printf("Stack is full\n");
    } else {
        s->data[++s->top] = value;
    }
}

int pop(Stack *s) {
    if (isEmpty(s)) {
        printf("Stack is empty\n");
        return -1;
    } else {
        return s->data[s->top--];
    }
}

int peek(Stack *s) {
    if (isEmpty(s)) {
        printf("Stack is empty\n");
        return -1;
    } else {
        return s->data[s->top];
    }
}

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

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

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

    return 0;
}
                

Explanation

Let's break down the code:

• Stack structure: Defines a stack with a maximum size and a top pointer.
• initialize: Initializes the stack by setting the top pointer to -1.
• isFull: Checks if the stack is full.
• isEmpty: Checks if the stack is empty.
• push: Adds an element to the top of the stack if it's not full.
• pop: Removes and returns the top element of the stack if it's not empty.
• peek: Returns the top element of the stack without removing it.
• main: Demonstrates the usage of the stack by pushing, popping, and peeking elements.

Use Cases of Stacks

Stacks are used in various scenarios such as:

• Handling function calls and recursion.
• Expression evaluation and conversion (e.g., infix to postfix).
• Backtracking algorithms (e.g., maze solving).
• Undo mechanisms in text editors.

Conclusion

Stacks are a fundamental data structure with various applications in computer science. Understanding how to implement and use stacks is crucial for solving many algorithmic problems. The provided C implementation serves as a basic example to get started with stacks.