LEARNING OUTCOME 5

Stack: A Last-In-First-Out (LIFO) Data Structure

A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle. This means that the last element added to the stack is the first one to be removed. A stack is like a pile of books.

• Adding a book: You place it on the top of the pile (push).
• Taking a book: You always take the topmost book (pop).

So, the last book you added is the first one you take. This is the Last-In-First-Out (LIFO) principle.

Key Operations on a Stack:

1. Push: Adds an element to the top of the stack.
2. Pop: Removes the top element from the stack.
3. Peek: Returns the value of the top element without removing it.
4. IsEmpty: Checks if the stack is empty.

Implementation of a Stack

We can implement a stack using an array or a linked list. Here's a simple implementation using an array in C++:

Code Example

// Stack implementation using an array

#include <iostream>
#include <vector> // For dynamic array resizing (optional, but good practice)

class StackArray {
private:
    int top;
    std::vector<int> arr; // Dynamic array (more flexible)
    int maxSize; // Maximum size of the stack

public:
    StackArray(int size = 100) : top(-1), maxSize(size) {}

    bool isEmpty() const {
        return top == -1;
    }

    bool isFull() const {
        return top == maxSize - 1;
    }

    void push(int value) {
        if (isFull()) {
            std::cerr << "Stack Overflow!" << std::endl;
            return;
        }
        arr.push_back(value);
        top++;
        std::cout << value << " pushed onto the stack" << std::endl;
    }

    int pop() {
        if (isEmpty()) {
            std::cerr << "Stack Underflow!" << std::endl;
            return -1;
        }
        int poppedValue = arr[top];
        arr.pop_back();
        top--;
        return poppedValue;
    }

    int peek() const {
        if (isEmpty()) {
            std::cerr << "Stack is Empty!" << std::endl;
            return -1;
        }
        return arr[top];
    }

    int size() const {
        return top + 1;
    }
};

// Stack implementation using a linked list

class Node {
public:
    int data;
    Node* next;

    Node(int value) : data(value), next(nullptr) {}
};

class StackLinkedList {
private:
    Node* head;

public:
    StackLinkedList() : head(nullptr) {}

    bool isEmpty() const {
        return head == nullptr;
    }

    void push(int value) {
        Node* newNode = new Node(value);
        newNode->next = head;
        head = newNode;
        std::cout << value << " pushed onto the stack" << std::endl;
    }

    int pop() {
        if (isEmpty()) {
            std::cerr << "Stack Underflow!" << std::endl;
            return -1;
        }
        int poppedValue = head->data;
        Node* temp = head;
        head = head->next;
        delete temp;
        return poppedValue;
    }

    int peek() const {
        if (isEmpty()) {
            std::cerr << "Stack is Empty!" << std::endl;
            return -1;
        }
        return head->data;
    }

    int size() const {
        int count = 0;
        Node* current = head;
        while(current != nullptr) {
            count++;
            current = current->next;
        }
        return count;
    }
};

int main() {
    StackArray stackArr;
    stackArr.push(10);
    stackArr.push(20);
    std::cout << "Top element: " << stackArr.peek() << std::endl;
    std::cout << "Popped element: " << stackArr.pop() << std::endl;
    std::cout << "Stack size: " << stackArr.size() << std::endl;

    StackLinkedList stackList;
    stackList.push(100);
    stackList.push(200);
    std::cout << "Top element: " << stackList.peek() << std::endl;
    std::cout << "Popped element: " << stackList.pop() << std::endl;
    std::cout << "Stack size: " << stackList.size() << std::endl;

    return 0;
}

• Dynamic Array: Uses std::vector instead of a fixed-size array. This is much more flexible. You don't need to predefine a maximum size, and the vector will grow as needed. I've left the fixed-size array version commented out in case you want to see the difference.
• Constructor: Added a constructor to initialize top and (optionally) resize the vector.
• Error Handling: Uses std::cerr for error messages (better than std::cout for errors).
• Clearer push and pop: The push and pop operations are now more concise and use the vector's methods directly.
• size() method: Added a size() method to get the current number of elements in the stack.

StackLinkedList

• Node Class: Clearly defined Node class to represent elements in the linked list.
• Head Pointer: Uses head to point to the top of the stack.
• Push: Inserts new nodes at the beginning of the list (which is the top of the stack).
• Pop: Removes and returns the element at the top of the stack, and importantly, deletes the node to prevent memory leaks.
• Peek: Returns the element at the top of the stack without removing it.
• Error Handling: Uses std::cerr for error messages.
• size() method: Added a size() method to get the current number of elements in the stack.

Stack Operations

• Push: The push operation adds an element to the top of the stack. If the stack is full, it's considered a stack overflow.
• Pop: The pop operation removes the top element from the stack. If the stack is empty, it's considered a stack underflow.

Applications of Stacks

• 1. Function Call Stack: To manage function calls and return addresses.
• 2. Undo/Redo Functionality: To implement undo and redo features in text editors or other applications.
• 3. Backtracking Algorithms: To keep track of states and make backtracking decisions.
• 4. Expression Evaluation: To evaluate postfix and prefix expressions.
• 5. Browser History: To store the history of visited pages.
• 6. Recursion: To manage recursive function calls.
• 7. Balancing Parentheses: To check if parentheses in an expression are balanced.
• 8. Implementing Queues: Using two stacks, we can simulate a queue's behavior.

QUEUE

A queue is a linear data structure that follows the First-In-First-Out (FIFO) principle. This means that the first element added to the queue is the first one to be removed.

Distinction between Stack and Queue

Queue Operations

• 1. Enqueue: Adds an element to the rear of the queue.
• 2. Dequeue: Removes an element from the front of the queue.
• 3. Peek: Returns the value of the front element without removing it.
• 4. IsEmpty: Checks if the queue is empty.
• 5. IsFull: Checks if the queue is full (if implemented with a fixed-size array).

#include <iostream>
	#include <queue> // For using the standard queue (or you can implement your own)
	#include <vector> // If you want to use a vector for a fixed-size queue
	
	// Example using std::queue (dynamic size)
	void exampleStdQueue() {
		std::queue<int> q;
	
		// Enqueue
		q.push(10);
		q.push(20);
		q.push(30);
	
		// Peek
		std::cout << "Front element: " << q.front() << std::endl; // Output: 10
	
		// Dequeue
		std::cout << "Dequeued element: " << q.front() << std::endl;
		q.pop();
	
		// IsEmpty
		if (q.empty()) {
			std::cout << "Queue is empty" << std::endl;
		} else {
			std::cout << "Queue is not empty" << std::endl; // Output: Queue is not empty
		}
	
		// Size
		std::cout << "Queue size: " << q.size() << std::endl; // Output: 2
	
		// Dequeue remaining elements
		while (!q.empty()) {
			std::cout << "Dequeued element: " << q.front() << std::endl;
			q.pop();
		}
	
		if (q.empty()) {
			std::cout << "Queue is empty" << std::endl; // Output: Queue is empty
		}
	}
	
	// Example of a fixed-size queue using a vector (more complex, less common)
	void exampleFixedSizeQueue() {
		const int maxSize = 5;
		std::vector<int> q(maxSize); // Use a vector as the underlying storage
		int front = 0;
		int rear = -1;
		int size = 0;
	
		// IsFull
		auto isFull = [&]() { return size == maxSize; };
		// IsEmpty
		auto isEmpty = [&]() { return size == 0; };
		// Enqueue
		auto enqueue = [&](int value) {
			if (isFull()) {
				std::cerr << "Queue is full!" << std::endl;
				return;
			}
			rear = (rear + 1) % maxSize; // Wrap around if necessary
			q[rear] = value;
			size++;
			std::cout << value << " enqueued" << std::endl;
		};
		// Dequeue
		auto dequeue = [&]() {
			if (isEmpty()) {
				std::cerr << "Queue is empty!" << std::endl;
				return -1; // Or throw an exception
			}
			int value = q[front];
			front = (front + 1) % maxSize;
			size--;
			return value;
		};
		// Peek
		auto peek = [&]() {
			 if (isEmpty()) {
				std::cerr << "Queue is empty!" << std::endl;
				return -1;
			}
			return q[front];
		};
	
		enqueue(10);
		enqueue(20);
		enqueue(30);
	
		std::cout << "Front element: " << peek() << std::endl;
		std::cout << "Dequeued element: " << dequeue() << std::endl;
		std::cout << "Is queue full? " << isFull() << std::endl;
		std::cout << "Is queue empty? " << isEmpty() << std::endl;
		std::cout << "Dequeued element: " << dequeue() << std::endl;
		std::cout << "Is queue full? " << isFull() << std::endl;
		std::cout << "Is queue empty? " << isEmpty() << std::endl;
	}
	
	int main() {
		std::cout << "Example using std::queue:" << std::endl;
		exampleStdQueue();
	
		std::cout << "\nExample using fixed-size queue:" << std::endl;
		exampleFixedSizeQueue();
	
		return 0;
	}
	

`exampleStdQueue()` function:

• `std::queue q;`: This line declares a queue named `q` that will store integers. `std::queue` handles memory management automatically, so it can grow as needed.
• Enqueue operations: The `q.push()` method adds elements to the back (rear) of the queue. In this example, 10, 20, and 30 are added.
• Peek operation: `q.front()` returns the element at the front of the queue *without* removing it. The output will be 10 because that was the first element added.
• Dequeue operation: `q.pop()` removes the element at the front of the queue. The removed element is not returned.
• `empty()` check: `q.empty()` returns `true` if the queue is empty and `false` otherwise. This is used to check the queue's state.
• `size()` operation: `q.size()` returns the number of elements currently in the queue.
• Dequeue remaining elements: The `while` loop continues to dequeue and print elements from the queue until it becomes empty.

`exampleFixedSizeQueue()` function:

• `const int maxSize = 5;`: Defines the maximum number of elements the queue can hold.
• `std::vector q(maxSize);`: Creates a vector named `q` with the specified `maxSize`. This vector will store the queue elements.
• `int front = 0; int rear = -1; int size = 0;`: These variables are crucial for managing the queue:
  • `front`: Index of the element at the front of the queue.
  • `rear`: Index of the element at the rear of the queue.
  • `size`: Number of elements currently in the queue.
• Lambda functions for operations: The code uses lambda functions (`[&]() { ... };`) to define the queue operations (`isFull`, `isEmpty`, `enqueue`, `dequeue`, `peek`). Using lambdas helps keep the code organized. The `[&]` part is a capture clause, indicating that the lambdas capture variables from the surrounding scope (like `maxSize`, `front`, `rear`, `size`).
• `isFull()` lambda: Checks if the queue is full by comparing `size` to `maxSize`.
• `isEmpty()` lambda: Checks if the queue is empty by checking if `size` is 0.
• `enqueue()` lambda:
  • Checks if the queue is full. If it is, it prints an error message and returns.
  • Calculates the new `rear` index using the modulo operator (`%`). This is essential for implementing the wrap-around behavior of a circular queue. When `rear` reaches the end of the vector, it wraps back to the beginning.
  • Adds the new element at the calculated `rear` index in the vector.
  • Increments `size`.
• `dequeue()` lambda:
  • Checks if the queue is empty. If it is, it prints an error message and returns -1.
  • Retrieves the element at the `front` index.
  • Calculates the new `front` index using the modulo operator (`%`) for wrap-around.
  • Decrements `size`.
  • Returns the dequeued value.
• `peek()` lambda:
  • Checks if the queue is empty. If it is, it prints an error message and returns -1.
  • Returns the element at the `front` index without removing it.
• Example usage: The code then demonstrates how to use the implemented `enqueue`, `dequeue`, and `peek` operations.

`main()` function:

• The `main()` function simply calls both `exampleStdQueue()` and `exampleFixedSizeQueue()` to show how to use each type of queue.

Key Differences and When to Use Which:

• `std::queue`: Use this for most general queue needs. It's simpler, safer (it handles resizing), and usually more efficient.
• Fixed-size queue (using a vector): Only use this if you have a *strict* requirement for a fixed-size queue (e.g., if you're working with limited memory or hardware constraints). Implementing it yourself is more complex and error-prone. `std::queue` is almost always the better choice.

Enqueue and Dequeue Operations

Enqueue

The enqueue operation adds an element to the rear end of the queue. Imagine a queue of people waiting for a service. When a new person arrives, they join the queue at the end. Similarly, in a queue data structure, a new element is added to the rear.

Dequeue

The dequeue operation removes an element from the front end of the queue. Continuing the analogy of a queue of people, the person at the front of the queue is the first one to be served and leaves the queue. In a queue data structure, the element at the front is removed.

Circular Queue

A circular queue is a linear data structure that operates like a queue but with a circular array implementation. In a circular queue, the last position is connected to the first position, forming a circular structure. This allows for efficient use of space and avoids the need for frequent memory reallocations.

Priority Queue

A priority queue is a queue where each element has a priority associated with it. Elements are dequeued in order of their priority, with the highest-priority element being dequeued first. It's often implemented using a heap data structure.

Applications of Queues

• Breadth-First Search (BFS): To explore graph nodes level by level.
• Print Queue: To manage print jobs in a printer.
• Task Scheduling: To schedule tasks in operating systems.
• Simulation: To simulate real-world systems like traffic lights or bank queues.
• Keyboard Buffer: To store keystrokes temporarily.
• Call Center Queues: To manage incoming calls.
• Producer-Consumer Problem: To coordinate between processes or threads that produce and consume data.