Overview of Stacks and Queues

Stacks and queues are essential data structures that manage collections of elements in specific ways. A stack follows the Last In First Out (LIFO) principle, meaning the last element added is the first to be removed. On the other hand, a queue operates on the First In First Out (FIFO) principle, where the first element added is the first to be removed. Understanding these concepts is crucial for effective problem-solving in programming, as they are widely used in algorithms and real-world applications.

Prerequisites

• Basic understanding of C programming
• Familiarity with functions and pointers
• Knowledge of dynamic memory allocation
• Concept of arrays and structures in C

Implementing a Stack in C

A stack can be implemented using an array or a linked list. In this section, we will create a stack using an array.

#include 
#include 

#define MAX 100

struct Stack {
    int top;
    int items[MAX];
};

struct Stack* createStack() {
    struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));
    stack->top = -1;
    return stack;
}

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

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

void push(struct Stack* stack, int item) {
    if (isFull(stack)) {
        printf("Stack is full!\n");
        return;
    }
    stack->items[++stack->top] = item;
}

int pop(struct Stack* stack) {
    if (isEmpty(stack)) {
        printf("Stack is empty!\n");
        return -1;
    }
    return stack->items[stack->top--];
}

void display(struct Stack* stack) {
    if (isEmpty(stack)) {
        printf("Stack is empty!\n");
        return;
    }
    for (int i = stack->top; i >= 0; i--) {
        printf("%d \n", stack->items[i]);
    }
}

int main() {
    struct Stack* stack = createStack();
    push(stack, 10);
    push(stack, 20);
    push(stack, 30);
    printf("Elements in stack:\n");
    display(stack);
    printf("Popped element: %d\n", pop(stack));
    return 0;
}

This code implements a stack using an array. Here's a breakdown of the code:

• #include and #include : Import standard libraries for input/output and memory allocation.
• #define MAX 100: Define a constant for the maximum stack size.
• struct Stack {...}: Declare a structure to represent the stack, including an array and a top index.
• createStack: Allocate memory for a new stack and initialize the top index.
• isFull: Check if the stack is full.
• isEmpty: Check if the stack is empty.
• push: Add an element to the stack if it is not full.
• pop: Remove and return the top element of the stack if it is not empty.
• display: Print all elements in the stack.
• main: Create a stack, push some elements, display them, and pop an element.

Implementing a Queue in C

Queues can also be implemented using arrays or linked lists. Here, we'll implement a queue using an array.

#include 
#include 

#define MAX 100

struct Queue {
    int items[MAX];
    int front, rear;
};

struct Queue* createQueue() {
    struct Queue* queue = (struct Queue*)malloc(sizeof(struct Queue));
    queue->front = -1;
    queue->rear = -1;
    return queue;
}

int isFull(struct Queue* queue) {
    return (queue->rear + 1) % MAX == queue->front;
}

int isEmpty(struct Queue* queue) {
    return queue->front == -1;
}

void enqueue(struct Queue* queue, int item) {
    if (isFull(queue)) {
        printf("Queue is full!\n");
        return;
    }
    if (isEmpty(queue)) {
        queue->front = 0;
    }
    queue->rear = (queue->rear + 1) % MAX;
    queue->items[queue->rear] = item;
}

int dequeue(struct Queue* queue) {
    if (isEmpty(queue)) {
        printf("Queue is empty!\n");
        return -1;
    }
    int item = queue->items[queue->front];
    if (queue->front == queue->rear) {
        queue->front = queue->rear = -1;
    } else {
        queue->front = (queue->front + 1) % MAX;
    }
    return item;
}

void display(struct Queue* queue) {
    if (isEmpty(queue)) {
        printf("Queue is empty!\n");
        return;
    }
    for (int i = queue->front; i != queue->rear; i = (i + 1) % MAX) {
        printf("%d \n", queue->items[i]);
    }
    printf("%d \n", queue->items[queue->rear]);
}

int main() {
    struct Queue* queue = createQueue();
    enqueue(queue, 10);
    enqueue(queue, 20);
    enqueue(queue, 30);
    printf("Elements in queue:\n");
    display(queue);
    printf("Dequeued element: %d\n", dequeue(queue));
    return 0;
}

This code implements a queue using an array. Here’s a detailed explanation:

• struct Queue {...}: Define a structure to represent the queue, including an array and front/rear indices.
• createQueue: Allocate memory for a new queue and initialize front and rear indices.
• isFull: Determine if the queue is full using circular logic.
• isEmpty: Check if the queue is empty.
• enqueue: Add an element to the queue if it is not full, updating the rear index.
• dequeue: Remove and return the front element of the queue if it is not empty, updating the front index.
• display: Print all elements from front to rear in the queue.
• main: Create a queue, enqueue some elements, display them, and dequeue an element.

Applications of Stacks and Queues

Stacks and queues are widely used in various applications:

• Stacks: Used in function calling, expression parsing, backtracking algorithms, and undo mechanisms in applications.
• Queues: Used in scheduling, breadth-first search algorithms, print spooling, and handling requests in servers.

Best Practices and Common Mistakes

When working with stacks and queues, consider the following best practices:

• Always check for overflow and underflow conditions when pushing or popping from stacks or enqueueing/dequeueing from queues.
• Use dynamic memory allocation judiciously to avoid memory leaks.
• Prefer using linked lists for stacks and queues when the maximum size is not known upfront.
• Keep operations O(1) for both stacks and queues to maintain efficiency.

Conclusion

In this article, we explored stacks and queues, two fundamental data structures in C programming. We learned how to implement them using arrays and their practical applications. Understanding these structures will help you enhance your problem-solving skills and improve your programming efficiency. Remember to apply best practices to avoid common pitfalls when using these data structures.