C Stacks and Queues

A stack and a queue are two fundamental data structures in programming. Both store collections of elements, but they differ in how elements are added and removed. Understanding these structures is essential for solving real-world problems like browser history, task scheduling, and expression evaluation.

Stack — Last In, First Out (LIFO)

A stack works like a pile of plates. You place plates on top and also take them from the top. The last plate you placed is the first one you pick up. This principle is called LIFO — Last In, First Out.

Visual Diagram

Push 10, then 20, then 30:

      +----+
TOP-> | 30 |  <-- Last pushed, first to come out
      +----+
      | 20 |
      +----+
      | 10 |  <-- First pushed, last to come out
      +----+

Pop: removes 30 first, then 20, then 10

Stack Operations

Stack Implementation Using Array

#include <stdio.h>

#define MAX 100

int stack[MAX];
int top = -1;   // -1 means stack is empty

// Check if stack is full
int isFull()  { return top == MAX - 1; }

// Check if stack is empty
int isEmpty() { return top == -1; }

// Push — add to top
void push(int value)
{
    if (isFull()) {
        printf("Stack Overflow! Cannot push %d\n", value);
        return;
    }
    stack[++top] = value;
    printf("Pushed: %d\n", value);
}

// Pop — remove from top
int pop()
{
    if (isEmpty()) {
        printf("Stack Underflow! Stack is empty.\n");
        return -1;
    }
    return stack[top--];
}

// Peek — view top without removing
int peek()
{
    if (isEmpty()) return -1;
    return stack[top];
}

int main()
{
    push(10);   // Pushed: 10
    push(20);   // Pushed: 20
    push(30);   // Pushed: 30

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

    printf("Popped: %d\n", pop());   // Popped: 30
    printf("Popped: %d\n", pop());   // Popped: 20

    printf("Top element: %d\n", peek());   // Top element: 10

    return 0;
}

Real-World Uses of Stack

• Browser back button: Each visited page is pushed. Clicking Back pops the last page.
• Undo feature: Every action is pushed. Ctrl+Z pops the last action.
• Function call management: The CPU uses a call stack to track function calls and returns.
• Bracket matching: Checking if every opening bracket has a closing one.

Queue — First In, First Out (FIFO)

A queue works like a line at a ticket counter. The first person who joins the line is the first one served. This principle is called FIFO — First In, First Out.

Visual Diagram

Enqueue 10, then 20, then 30:

FRONT                          REAR
  |                              |
  v                              v
+----+    +----+    +----+
| 10 | -> | 20 | -> | 30 |
+----+    +----+    +----+

Dequeue: removes 10 first (FRONT), then 20, then 30
New elements join at REAR.

Queue Operations

Queue Implementation Using Array

#include <stdio.h>

#define MAX 100

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

int isEmpty() { return front == -1; }
int isFull()  { return rear == MAX - 1; }

// Enqueue — add to rear
void enqueue(int value)
{
    if (isFull()) {
        printf("Queue is full! Cannot enqueue %d\n", value);
        return;
    }
    if (isEmpty()) front = 0;   // first element
    queue[++rear] = value;
    printf("Enqueued: %d\n", value);
}

// Dequeue — remove from front
int dequeue()
{
    if (isEmpty()) {
        printf("Queue is empty!\n");
        return -1;
    }
    int value = queue[front];
    if (front == rear) {
        front = rear = -1;   // queue is now empty
    } else {
        front++;
    }
    return value;
}

// Peek — view front element
int peekFront()
{
    if (isEmpty()) return -1;
    return queue[front];
}

int main()
{
    enqueue(10);   // Enqueued: 10
    enqueue(20);   // Enqueued: 20
    enqueue(30);   // Enqueued: 30

    printf("Front: %d\n", peekFront());       // Front: 10

    printf("Dequeued: %d\n", dequeue());   // Dequeued: 10
    printf("Dequeued: %d\n", dequeue());   // Dequeued: 20

    printf("Front: %d\n", peekFront());       // Front: 30

    return 0;
}

Real-World Uses of Queue

• Printer queue: Documents print in the order they were sent.
• CPU scheduling: Processes waiting for the CPU are managed in a queue.
• Customer service: Call centers handle customers in the order they called.
• Breadth-First Search (BFS): A graph traversal algorithm uses a queue.

Stack vs Queue — Side-by-Side Comparison

STACK                          QUEUE
(LIFO)                         (FIFO)

  Push -> TOP                  Enqueue -> REAR
  Pop  <- TOP                  Dequeue <- FRONT

  [30]  <-- TOP                FRONT --> [10] [20] [30] <-- REAR
  [20]
  [10]  <-- BOTTOM

New items added at top.        New items added at rear.
Items removed from top.        Items removed from front.

Stack Using Linked List

A linked-list-based stack removes the size limitation of array-based stacks.

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

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

struct Node *top = NULL;

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

int pop() {
    if (!top) { printf("Empty\n"); return -1; }
    int val = top->data;
    struct Node *temp = top;
    top = top->next;
    free(temp);
    return val;
}

int main() {
    push(5);
    push(10);
    push(15);
    printf("Pop: %d\n", pop());   // Pop: 15
    printf("Pop: %d\n", pop());   // Pop: 10
    return 0;
}

Summary

A stack follows the LIFO (Last In, First Out) principle — the last element added is the first to be removed. Its key operations are push (add to top) and pop (remove from top). A queue follows the FIFO (First In, First Out) principle — the first element added is the first to be removed. Its key operations are enqueue (add to rear) and dequeue (remove from front). Both can be implemented using arrays or linked lists. Stacks power undo systems, browser back buttons, and function call tracking. Queues power print spooling, CPU scheduling, and network request handling. These two structures appear constantly in algorithms and real-world software systems.