Stack and Queue Implementation

# CHAPTER 23

Stack and Queue Implementation #

1. Introduction #

2. Learning Objectives #

• Explain the LIFO principle of a Stack.

• Implement Stack operations: push, pop, peek.

• Explain the FIFO principle of a Queue.

• Implement Queue operations: enqueue, dequeue.

• Understand Overflow and Underflow conditions.

3. Stack (LIFO - Last In, First Out) #

• Push: Add an item to the top.

• Pop: Remove an item from the top.

• Peek/Top: Look at the top item without removing it.

#include <stdio.h>
#define MAX 5

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

// Add item to stack
void push(int value) {
    if (top == MAX - 1) {
        printf("Stack Overflow! Cannot push %d\n", value);
    } else {
        top++; // Move top up
        stack[top] = value;
        printf("Pushed %d\n", value);
    }
}

// Remove item from stack
void pop() {
    if (top == -1) {
        printf("Stack Underflow! Stack is empty.\n");
    } else {
        printf("Popped %d\n", stack[top]);
        top--; // Move top down
    }
}

int main() {
    push(10);
    push(20);
    push(30);
    pop(); // Removes 30
    pop(); // Removes 20
    return 0;
}

4. Visualizing a Stack #

push(10)   push(20)   push(30)     pop()

           |      |   |  30  | <-top
|      |   |  20  |   |  20  |   |  20  | <-top
|  10  |   |  10  |   |  10  |   |  10  |
+------+   +------+   +------+   +------+

5. Queue (FIFO - First In, First Out) #

• Enqueue: Add an item to the rear (back).

• Dequeue: Remove an item from the front.

#include <stdio.h>
#define MAX 5

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

void enqueue(int value) {
    if (rear == MAX - 1) {
        printf("Queue is Full!\n");
    } else {
        if (front == -1) front = 0; // Set front on first insert
        rear++;
        queue[rear] = value;
        printf("Enqueued %d\n", value);
    }
}

void dequeue() {
    if (front == -1 || front > rear) {
        printf("Queue is Empty!\n");
    } else {
        printf("Dequeued %d\n", queue[front]);
        front++; // Move front forward
    }
}

int main() {
    enqueue(10);
    enqueue(20);
    enqueue(30);
    dequeue(); // Removes 10
    dequeue(); // Removes 20
    return 0;
}

6. Visualizing a Queue #

enqueue(10, 20, 30)

Front             Rear
  |                 |
  v                 v
[ 10 ][ 20 ][ 30 ][  ][  ]

dequeue() -> Removes 10, Front moves to 20.

*(Note: A basic array queue wastes space as front moves forward. A "Circular Queue" solves this by wrapping around).*

7. Real-World Applications #

• Stacks: The Call Stack (functions), Undo features in text editors, Browser back buttons, balancing parentheses in compilers.

• Queues: Printer job scheduling, CPU task scheduling, waiting lines in web servers, BFS (Breadth-First Search) algorithms.

8. Common Mistakes #

• Stack Overflow: Trying to push when top == MAX - 1.

• Stack Underflow: Trying to pop when top == -1.

• Queue Memory Waste: In a linear array queue, dequeuing doesn't shift elements, so the front spaces become unusable. (Fix: Use a Circular Queue or Linked List).

9. Exercises #

1. 1. Add a peek() function to the Stack code that returns the top element without popping it.

1. 2. Add a display() function to the Queue code that prints all current elements from front to rear.

10. MCQ Quiz with Answers #

11. Interview Questions #

• Q: How would you implement a Queue using two Stacks?

• Q: What is a Circular Queue, and how does it solve the memory waste problem of a linear array queue?

• Q: Explain how the OS uses a Stack for function calls.

12. Summary #

13. Next Chapter Recommendation #