Introduction to Programming in C

📘 Stacks and Queues Using Arrays and Linked Lists in C

In this chapter, we explore two fundamental linear data structures: Stacks and Queues. You will learn how they work and how to implement them using both arrays and linked lists in C.

🔹 What is a Stack?

A Stack follows LIFO (Last In First Out) principle. The last element inserted is the first one to be removed.

✅ Operations:

• push() – Add element
• pop() – Remove element
• peek() – View top element
• isEmpty() – Check if empty

🔧 Stack Using Array

#define MAX 100
int stack[MAX];
int top = -1;

void push(int val) {
  if (top == MAX - 1) {
    printf("Stack Overflow\n");
    return;
  }
  stack[++top] = val;
}

int pop() {
  if (top == -1) {
    printf("Stack Underflow\n");
    return -1;
  }
  return stack[top--];
}

🔧 Stack Using Linked List

struct Node {
  int data;
  struct Node* next;
};

struct Node* top = NULL;

void push(int val) {
  struct Node* newNode = malloc(sizeof(struct Node));
  newNode->data = val;
  newNode->next = top;
  top = newNode;
}

int pop() {
  if (top == NULL) return -1;
  int val = top->data;
  struct Node* temp = top;
  top = top->next;
  free(temp);
  return val;
}

🔸 What is a Queue?

A Queue follows FIFO (First In First Out) principle. The first element inserted is the first to be removed.

✅ Operations:

• enqueue() – Add element
• dequeue() – Remove element
• isEmpty() – Check if empty

🔧 Queue Using Array

#define MAX 100
int queue[MAX];
int front = -1, rear = -1;

void enqueue(int val) {
  if (rear == MAX - 1) {
    printf("Queue Full\n");
    return;
  }
  if (front == -1) front = 0;
  queue[++rear] = val;
}

int dequeue() {
  if (front == -1 || front > rear) {
    printf("Queue Empty\n");
    return -1;
  }
  return queue[front++];
}

🔧 Queue Using Linked List

struct Node {
  int data;
  struct Node* next;
};

struct Node* front = NULL;
struct Node* rear = NULL;

void enqueue(int val) {
  struct Node* newNode = malloc(sizeof(struct Node));
  newNode->data = val;
  newNode->next = NULL;

  if (rear == NULL) {
    front = rear = newNode;
  } else {
    rear->next = newNode;
    rear = newNode;
  }
}

int dequeue() {
  if (front == NULL) return -1;
  int val = front->data;
  struct Node* temp = front;
  front = front->next;
  if (front == NULL) rear = NULL;
  free(temp);
  return val;
}

📚 Real-Life Example (UdaanPath)

Imagine handling support requests at UdaanPath — a queue is used to process them in the order received (FIFO). For backtracking or undo operations, a stack (LIFO) is more appropriate.

📝 Practice Tasks

1. Implement stack push/pop using array and print stack status
2. Write enqueue/dequeue operations using linked list
3. Implement peek() and isEmpty() for both structures
4. Simulate undo-redo logic using two stacks

✅ Summary

• Stack: LIFO | Operations: push, pop, peek
• Queue: FIFO | Operations: enqueue, dequeue
• Implemented via arrays (fixed size) or linked lists (dynamic)
• Essential for memory management, recursion, scheduling, and more

🚀 Coming Next

Up next: Trees and Basic Tree Traversals — we’ll explore binary trees and how to traverse them using pre-order, in-order, and post-order logic.