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