Stacks and Queues

Introduction to the Stack ADT

Stack: A data structure that follows LIFO (Last In, First Out) principle.
- Examples:
- Plates stacked in a cafeteria.
- Function call addresses in programming.

Stack Basics

Implementation:
- Usually as a list with operations at one end (top of the stack).
Types of Stack:
- Static Stack: Fixed size, typically uses an array.
- Dynamic Stack: Size can vary, generally implemented with a linked list.

Key Stack Operations

push: Add an element to the top of the stack.
pop: Remove and return the top element from the stack.
isEmpty: Check if the stack contains any elements (returns true if empty).

Static Stack Implementation

Uses an array of a predefined size.
- Example: const int STACK_SIZE = 3; char s[STACK_SIZE];
- Variable top is used to track the current top of the stack.
Initial State:
- top = 0 when stack is empty.

Example of Array Stack Operations

Push Operations:
- Push 'E': top=1
- Push 'K': top=2
- Push 'G': top=3
Pop Operations:
- After popping three times, the stack is empty and top=0.

Class Implementation Using an Array

class STACK {
private:
    char *s; // array storage
    int capacity, top;
public:
    void push(char x);
    void pop(char &x);
    bool isEmpty();
    STACK(int stackSize);
    ~STACK();
};

Exception Handling in Stack Operations

Uses exception classes to manage overflow and underflow.
- Overflow Exception: Thrown when attempting to push onto a full stack.
- Underflow Exception: Thrown when attempting to pop from an empty stack.
Always encapsulate push/pop logic in a try block, followed by corresponding catch blocks for error handling.

Dynamic Stacks

Implemented using a linked list:
- No predetermined size; grows/shrinks as needed.
- Can't overflow, but underflow checks are necessary.

Linked Stack Implementation

Class definition with a private member for dynamic nodes:
Example of Push:

void push(char num) {
    StackNode *newNode = new StackNode;
    newNode->value = num;
    if (isEmpty()) {
        top = newNode;
        newNode->next = nullptr;
    } else {
        newNode->next = top;
        top = newNode;
    }
}

The STL Stack Container

The stack template can be implemented using vector, list, or deque:
- Member Functions:
- push: Add to stack.
- pop: Remove from stack.
- size: Number of elements.
- top: Reference to the top element.

Introduction to the Queue ADT

Queue: A data structure that follows FIFO (First In, First Out) rule.
- Examples:
- People waiting at an ATM.
- Cars in line to exit a parking lot.
Types:
- Static Queue: Fixed-size implementations using arrays.
- Dynamic Queue: Variable-size implementations using linked lists.

Queue Operations

enqueue: Add an element to the rear of the queue.
dequeue: Remove an element from the front of the queue.

Array Implementation for Queue

Example: Create an empty queue for chars with operations.
Issue: Front remains constant, causing inefficiencies as the queue size increases.
- Potential solution: Use a circular array.

Queue Class Implementation: Important Functions

isEmpty Function:

bool isEmpty() {
    return number <= 0;
}

isFull Function:

bool isFull() {
    return number >= qSize;
}

Enqueue Function:

if (!isFull()) {
    rear = (rear + 1) % qSize;
    q[rear] = x;
    number++;
}

Dequeue Function:

if (!isEmpty()) {
    front = (front + 1) % qSize;
    x = q[front];
    number--;
}

Exception Handling in Static Queues

Implement to manage conditions for enqueueing into a full queue or dequeueing from an empty queue.

Dynamic Queues

Implemented using linked lists to manage dynamic sizing:
Function implementations follow similar logic to stacks, ensuring efficient operations as items are added/removed.

The STL deque and queue Containers

deque: Double-ended queue. Can enqueue and dequeue efficiently.
queue: Provides basic queue functionalities, allows implementation with different underlying containers (vector, list, deque).

Defining a Queue in C++

Based on usage of different STL containers:

deque<char> cQueue;
queue<char> cQueue;
queue<char, list<char>> cQueue;

#include <iostream>
#include <exception>

class OverflowException : public std::exception {
    const char* what() const noexcept {
        return "Stack Overflow";
    }
};

class UnderflowException : public std::exception {
    const char* what() const noexcept {
        return "Stack Underflow";
    }
};

class STACK {
private:
    char *s;
    int capacity, top;
public:
    STACK(int stackSize) : capacity(stackSize), top(0) {
        s = new char[capacity];
    }
    ~STACK() {
        delete[] s;
    }
    void push(char x) {
        if (top >= capacity) throw OverflowException();
        s[top++] = x;
    }
    void pop(char &x) {
        if (top <= 0) throw UnderflowException();
        x = s[--top];
    }
    bool isEmpty() { return top == 0; }
};

int main() {
    STACK stack(3);
    try {
        stack.push('A');
        stack.push('B');
        stack.push('C');
        char popped;
        stack.pop(popped);
        std::cout << "Popped element: " << popped << std::endl;
    } catch (const std::exception &e) {
        std::cerr << e.what() << std::endl;
    }
    return 0;
}

Example of Color Coordinated Complete Code Using Queues

#include <iostream>
#include <exception>

class QueueOverflowException : public std::exception {
    const char* what() const noexcept {
        return "Queue Overflow";
    }
};

class QueueUnderflowException : public std::exception {
    const char* what() const noexcept {
        return "Queue Underflow";
    }
};

class Queue {
private:
    int front, rear, number, qSize;
    char *q;
public:
    Queue(int size) : front(0), rear(-1), number(0), qSize(size) {
        q = new char[qSize];
    }
    ~Queue() {
        delete[] q;
    }
    bool isEmpty() { return number == 0; }
    bool isFull() { return number == qSize; }
    void enqueue(char x) {
        if (isFull()) throw QueueOverflowException();
        rear = (rear + 1) % qSize;
        q[rear] = x;
        number++;
    }
    void dequeue(char &x) {
        if (isEmpty()) throw QueueUnderflowException();
        front = (front + 1) % qSize;
        x = q[front];
        number--;
    }
};

int main() {
    Queue queue(3);
    try {
        queue.enqueue('A');
        queue.enqueue('B');
        char dequeued;
        queue.dequeue(dequeued);
        std::cout << "Dequeued element: " << dequeued << std::endl;
    } catch (const std::exception &e) {
        std::cerr << e.what() << std::endl;
    }
    return 0;
}