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

1. Push Operations:

   • Push 'E': top=1

   • Push 'K': top=2

   • Push 'G': top=3

2. 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

1. isEmpty Function:

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

2. isFull Function:

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

3. Enqueue Function:

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

4. 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;
}