Complete Notes on Stacks and Queues

With Code Examples, Structures, Diagrams & Applications

Complete Notes on Stacks and Queues

With Code Examples, Structures, Diagrams & Applications

Complete Notes on Stacks and Queues

With Code Examples, Structures, Diagrams & Applications

1. STACK

Definition

LIFO (Last In, First Out)
The last element added is the first one to be removed.

Analogy

A stack of plates: You push a plate on top, and pop from the top.

    [Plate 3] ← Top
    [Plate 2]
    [Plate 1]

Basic Operations

Operation Description Time Complexity
push(x) Insert element, x at top O(1)
pop() Remove and return top O(1)
peek() / top() View top element O(1)
isEmpty() Check if stack is empty O(1)
size() Return number of elements O(1)

Implementation 1: Array-Based Stack

#include <stdio.h>
#define MAX 100

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

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

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

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

void push(Stack* s, int data) {
    if(isFull(s)) {
        printf("Stack Overflow!\n");
        return;
    }
    s->arr[++(s->top)] = data;
}

int pop(Stack* s) {
    if(isEmpty(s)) {
        printf("Stack Underflow!\n");
        return -1;
    }
    return s->arr[(s->top)--];
}

int peek(Stack* s) {
    if(isEmpty(s)) return -1;
    return s->arr[s->top];
}

// Example Usage
int main() {
    Stack s;
    initStack(&s);
    push(&s, 10);
    push(&s, 20);
    push(&s, 30);
    printf("Top: %d\n", peek(&s));  // 30
    printf("Pop: %d\n", pop(&s));   // 30
    printf("Pop: %d\n", pop(&s));   // 20
    return 0;
}

Implementation 2: Linked List-Based Stack

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

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

typedef struct {
    Node* top;
} Stack;

void initStack(Stack* s) {
    s->top = NULL;
}

void push(Stack* s, int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = s->top;
    s->top = newNode;
}

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

int peek(Stack* s) {
    return (s->top != NULL) ? s->top->data : -1;
}

Structure Diagram (Array Stack)

Index:     0    1    2    3
         +----+----+----+----+
Array:   | 10 | 20 | 30 |    |
         +----+----+----+----+
               ↑
              top = 2

Applications of Stack

Application Use
Function Call Call stack in recursion
Expression Evaluation Infix → Postfix → Evaluate
Parentheses Matching Check balanced (), {}, []
Undo Operation In editors
Backtracking Maze, N-Queen

Example: Parentheses Matching

int isBalanced(char* exp) {
    Stack s;
    initStack(&s);

    for(int i = 0; exp[i] != '\0'; i++) {
        if(exp[i] == '(' || exp[i] == '{' || exp[i] == '[')
            push(&s, exp[i]);
        else if(exp[i] == ')' || exp[i] == '}' || exp[i] == ']') {
            if(isEmpty(&s)) return 0;
            char top = peek(&s);
            if((exp[i] == ')' && top != '(') ||
               (exp[i] == '}' && top != '{') ||
               (exp[i] == ']' && top != '['))
                return 0;
            pop(&s);
        }
    }
    return isEmpty(&s);
}

2. QUEUE

Definition

FIFO (First In, First Out)
First element added is the first one to be removed.

Analogy

A line at a ticket counter: First come, first served.

Front → [A] → [B] → [C] → [D] ← Rear

Basic Operations

Operation Description Time Complexity
enqueue(x) Add x at rear O(1)
dequeue() Remove from front O(1)
front() View front element O(1)
rear() View rear element O(1)
isEmpty() Check if empty O(1)

Implementation 1: Simple Array Queue (Fixed Size)

#define MAX 100

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

void initQueue(Queue* q) {
    q->front = q->rear = -1;
}

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

int isFull(Queue* q) {
    return q->rear == MAX - 1;
}

void enqueue(Queue* q, int data) {
    if(isFull(q)) {
        printf("Queue Full!\n");
        return;
    }
    if(isEmpty(q))
        q->front = 0;
    q->arr[++(q->rear)] = data;
}

int dequeue(Queue* q) {
    if(isEmpty(q)) {
        printf("Queue Empty!\n");
        return -1;
    }
    int data = q->arr[q->front];
    if(q->front == q->rear)
        q->front = q->rear = -1;
    else
        q->front++;
    return data;
}

Problem: Space wastage after dequeue → Use Circular Queue

Implementation 2: Circular Queue

#define MAX 5

typedef struct {
    int arr[MAX];
    int front, rear;
} CQueue;

void init(CQueue* q) {
    q->front = q->rear = -1;
}

int isFull(CQueue* q) {
    return (q->rear + 1) % MAX == q->front;
}

int isEmpty(CQueue* q) {
    return q->front == -1;
}

void enqueue(CQueue* q, int data) {
    if(isFull(q)) {
        printf("Queue Full!\n");
        return;
    }
    if(isEmpty(q))
        q->front = 0;
    q->rear = (q->rear + 1) % MAX;
    q->arr[q->rear] = data;
}

int dequeue(CQueue* q) {
    if(isEmpty(q)) return -1;
    int data = q->arr[q->front];
    if(q->front == q->rear)
        q->front = q->rear = -1;
    else
        q->front = (q->front + 1) % MAX;
    return data;
}

Circular Queue Diagram

Index:  0   1   2   3   4
      +---+---+---+---+---+
      | D |   | A | B | C |
      +---+---+---+---+---+
          ↑           ↑
        front       rear

Implementation 3: Queue using Linked List

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

typedef struct {
    Node *front, *rear;
} Queue;

void initQueue(Queue* q) {
    q->front = q->rear = NULL;
}

void enqueue(Queue* q, int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;

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

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

Applications of Queue

Application Use
CPU Scheduling Round Robin
Breadth-First Search (BFS) Graph traversal
Printer Spooling Print jobs
Message Queues Inter-process communication
Simulation Bank queue, traffic lights

Comparison: Stack vs Queue

Feature Stack Queue
Principle LIFO FIFO
Insertion Top (push) Rear (enqueue)
Deletion Top (pop) Front (dequeue)
Access Only top Front & Rear
Use Case Recursion, Undo BFS, Scheduling

Special Types

1. Deque (Double-Ended Queue)

  • Insert/delete from both ends
  • Can act as Stack or Queue
// Operations: pushFront, pushBack, popFront, popBack

2. Priority Queue

  • Elements have priority
  • Highest priority removed first
  • Implemented using Heap

Summary Table

Data Structure Order Insertion Deletion Use Case
Stack LIFO O(1) O(1) Function calls
Simple Queue FIFO O(1) O(1) Limited space
Circular Queue FIFO O(1) O(1) Efficient space
Linked Queue FIFO O(1) O(1) Dynamic size

Practice Problems

  1. Reverse a string using stack
  2. Implement queue using two stacks
  3. Check palindrome using stack
  4. Implement stack using two queues
  5. Evaluate postfix expression

Key Takeaway:

Stack → For depth and recursion
Queue → For breadth and order preservation

End of Notes

Last updated: Nov 12, 2025

Complete Notes on Stacks and Queues

With Code Examples, Structures, Diagrams & Applications

Complete Notes on Stacks and Queues

With Code Examples, Structures, Diagrams & Applications

Complete Notes on Stacks and Queues

With Code Examples, Structures, Diagrams & Applications

1. STACK

Definition

LIFO (Last In, First Out)
The last element added is the first one to be removed.

Analogy

A stack of plates: You push a plate on top, and pop from the top.

    [Plate 3] ← Top
    [Plate 2]
    [Plate 1]

Basic Operations

Operation Description Time Complexity
push(x) Insert element, x at top O(1)
pop() Remove and return top O(1)
peek() / top() View top element O(1)
isEmpty() Check if stack is empty O(1)
size() Return number of elements O(1)

Implementation 1: Array-Based Stack

#include <stdio.h>
#define MAX 100

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

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

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

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

void push(Stack* s, int data) {
    if(isFull(s)) {
        printf("Stack Overflow!\n");
        return;
    }
    s->arr[++(s->top)] = data;
}

int pop(Stack* s) {
    if(isEmpty(s)) {
        printf("Stack Underflow!\n");
        return -1;
    }
    return s->arr[(s->top)--];
}

int peek(Stack* s) {
    if(isEmpty(s)) return -1;
    return s->arr[s->top];
}

// Example Usage
int main() {
    Stack s;
    initStack(&s);
    push(&s, 10);
    push(&s, 20);
    push(&s, 30);
    printf("Top: %d\n", peek(&s));  // 30
    printf("Pop: %d\n", pop(&s));   // 30
    printf("Pop: %d\n", pop(&s));   // 20
    return 0;
}

Implementation 2: Linked List-Based Stack

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

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

typedef struct {
    Node* top;
} Stack;

void initStack(Stack* s) {
    s->top = NULL;
}

void push(Stack* s, int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = s->top;
    s->top = newNode;
}

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

int peek(Stack* s) {
    return (s->top != NULL) ? s->top->data : -1;
}

Structure Diagram (Array Stack)

Index:     0    1    2    3
         +----+----+----+----+
Array:   | 10 | 20 | 30 |    |
         +----+----+----+----+
               ↑
              top = 2

Applications of Stack

Application Use
Function Call Call stack in recursion
Expression Evaluation Infix → Postfix → Evaluate
Parentheses Matching Check balanced (), {}, []
Undo Operation In editors
Backtracking Maze, N-Queen

Example: Parentheses Matching

int isBalanced(char* exp) {
    Stack s;
    initStack(&s);

    for(int i = 0; exp[i] != '\0'; i++) {
        if(exp[i] == '(' || exp[i] == '{' || exp[i] == '[')
            push(&s, exp[i]);
        else if(exp[i] == ')' || exp[i] == '}' || exp[i] == ']') {
            if(isEmpty(&s)) return 0;
            char top = peek(&s);
            if((exp[i] == ')' && top != '(') ||
               (exp[i] == '}' && top != '{') ||
               (exp[i] == ']' && top != '['))
                return 0;
            pop(&s);
        }
    }
    return isEmpty(&s);
}

2. QUEUE

Definition

FIFO (First In, First Out)
First element added is the first one to be removed.

Analogy

A line at a ticket counter: First come, first served.

Front → [A] → [B] → [C] → [D] ← Rear

Basic Operations

Operation Description Time Complexity
enqueue(x) Add x at rear O(1)
dequeue() Remove from front O(1)
front() View front element O(1)
rear() View rear element O(1)
isEmpty() Check if empty O(1)

Implementation 1: Simple Array Queue (Fixed Size)

#define MAX 100

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

void initQueue(Queue* q) {
    q->front = q->rear = -1;
}

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

int isFull(Queue* q) {
    return q->rear == MAX - 1;
}

void enqueue(Queue* q, int data) {
    if(isFull(q)) {
        printf("Queue Full!\n");
        return;
    }
    if(isEmpty(q))
        q->front = 0;
    q->arr[++(q->rear)] = data;
}

int dequeue(Queue* q) {
    if(isEmpty(q)) {
        printf("Queue Empty!\n");
        return -1;
    }
    int data = q->arr[q->front];
    if(q->front == q->rear)
        q->front = q->rear = -1;
    else
        q->front++;
    return data;
}

Problem: Space wastage after dequeue → Use Circular Queue

Implementation 2: Circular Queue

#define MAX 5

typedef struct {
    int arr[MAX];
    int front, rear;
} CQueue;

void init(CQueue* q) {
    q->front = q->rear = -1;
}

int isFull(CQueue* q) {
    return (q->rear + 1) % MAX == q->front;
}

int isEmpty(CQueue* q) {
    return q->front == -1;
}

void enqueue(CQueue* q, int data) {
    if(isFull(q)) {
        printf("Queue Full!\n");
        return;
    }
    if(isEmpty(q))
        q->front = 0;
    q->rear = (q->rear + 1) % MAX;
    q->arr[q->rear] = data;
}

int dequeue(CQueue* q) {
    if(isEmpty(q)) return -1;
    int data = q->arr[q->front];
    if(q->front == q->rear)
        q->front = q->rear = -1;
    else
        q->front = (q->front + 1) % MAX;
    return data;
}

Circular Queue Diagram

Index:  0   1   2   3   4
      +---+---+---+---+---+
      | D |   | A | B | C |
      +---+---+---+---+---+
          ↑           ↑
        front       rear

Implementation 3: Queue using Linked List

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

typedef struct {
    Node *front, *rear;
} Queue;

void initQueue(Queue* q) {
    q->front = q->rear = NULL;
}

void enqueue(Queue* q, int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;

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

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

Applications of Queue

Application Use
CPU Scheduling Round Robin
Breadth-First Search (BFS) Graph traversal
Printer Spooling Print jobs
Message Queues Inter-process communication
Simulation Bank queue, traffic lights

Comparison: Stack vs Queue

Feature Stack Queue
Principle LIFO FIFO
Insertion Top (push) Rear (enqueue)
Deletion Top (pop) Front (dequeue)
Access Only top Front & Rear
Use Case Recursion, Undo BFS, Scheduling

Special Types

1. Deque (Double-Ended Queue)

  • Insert/delete from both ends
  • Can act as Stack or Queue
// Operations: pushFront, pushBack, popFront, popBack

2. Priority Queue

  • Elements have priority
  • Highest priority removed first
  • Implemented using Heap

Summary Table

Data Structure Order Insertion Deletion Use Case
Stack LIFO O(1) O(1) Function calls
Simple Queue FIFO O(1) O(1) Limited space
Circular Queue FIFO O(1) O(1) Efficient space
Linked Queue FIFO O(1) O(1) Dynamic size

Practice Problems

  1. Reverse a string using stack
  2. Implement queue using two stacks
  3. Check palindrome using stack
  4. Implement stack using two queues
  5. Evaluate postfix expression

Key Takeaway:

Stack → For depth and recursion
Queue → For breadth and order preservation

End of Notes

Last updated: Nov 12, 2025