Stacks and Queues

• Stacks are a “first in, first out” type of system

• Stacks can “push” new items onto the top, and “pop” elements from the top of the stack and return them

• Nodes can be a good way of representing a stack

• Queues are a data structure where you can enqueue (add a new item to the “back of the line” so to speak) and Dequeue, or remove an item from the front of the queue and return it.

• Nodes and link lists are usually better and more versatile than arrays

  • Along with the memory cost of storing additional pointers, the pointer assignments add a small, constant cost to both the push and pop operations. We’re no longer setting a single array value and incrementing an index. However, as with all dynamic data structures, the tradeoff is increased flexibility: a linked list can grow and shrink with the data. We no longer have to worry about filling up our array or paying the additional costs to increase the array’s size.

• Different data structures both allow the programmer to use data in different ways and strongly impact the behavior of the algorithms working with that data. Both stacks and queues store objects, both can be implemented with either arrays or linked lists, and both can handle insertions and removals efficiently. From the perspective of simply storing bits, either will suffice. However, the way they handle the data, and specifically the order in which they return their items, gives these similar data structures radically different behavior. Stacks return the newest data they’ve stored, making them ideal for prioritizing the most recent items. Queues, in contrast, always return the oldest data they’ve stored, making them ideal for cases where we need to handle items in the order in which they arrive.

• Oh, here’s an example of a stack I cloned

#include <stdio.h>
#include <iostream>
using namespace std;

// Node Structure for the Linked List

struct Node {
    int data;       // Value stored in the node
    Node* next;     // Pointer to the next node in the list

    // Constructor to initialize a node with data
    Node(int value) {
        data = value;
        next = nullptr;
    }
};


// Stack Class Using Singly Linked List


class Stack {
private:
    Node* top; // Pointer to the top element of the stack

public:

    // Constructor
    // Initializes the stack as empty by setting top to nullptr

    Stack() {
        top = nullptr;
    }


    // Destructor
    // Frees all memory by popping all elements

    ~Stack() {
        while (!isEmpty()) {
            pop(); // Automatically deletes all nodes
        }
    }


    // push(int value)
    // Adds a new element to the top of the stack

    void push(int value) {
        Node* newNode = new Node(value);  // Create a new node with the given value
        newNode->next = top;              // New node points to the current top
        top = newNode;                    // Update top to point to the new node
        cout << "Pushed: " << value << endl;
    }


    // pop()
    // Removes the top element from the stack

    void pop() {
        if (isEmpty()) {
            cout << "Stack Underflow! Nothing to pop.\n";
            return;
        }

        Node* temp = top;       // Temporary pointer to the top node
        top = top->next;        // Move top to the next node in the list
        std::cout << "Popped: " << temp->data << endl;
        delete temp;            // Free memory of the removed node
    }


    // peek()
    // Returns the top element without removing it

    int peek() {
        if (isEmpty()) {
            cout << "Stack is empty. Nothing to peek.\n";
            return -1; // Return sentinel value (could also throw exception)
        }
        return top->data; // Return value at the top
    }


    // isEmpty()
    // Checks whether the stack is empty

    bool isEmpty() {
        return top == nullptr; // True if top is null, false otherwise
    }


    // display()
    // Prints all elements in the stack from top to bottom

    void display() {
        if (isEmpty()) {
            cout << "Stack is empty.\n";
            return;
        }

        Node* temp = top; // Start from the top
        cout << "Stack elements (top to bottom): ";
        while (temp != nullptr) {
            cout << temp->data << " "; // Print current node's data
            temp = temp->next;         // Move to the next node
        }
        cout << endl;
    }
};


// Main Function: Demonstrates Stack Operations


int main() {
    Stack s; // Create a Stack instance

    // Push elements onto the stack
    s.push(10);
    s.push(20);
    s.push(30);

    // Display current elements
    s.display(); // Should show: 30 20 10

    // Peek at the top element
    cout << "Top element is: " << s.peek() << endl;

    // Pop one element
    s.pop();     // Should remove 30
    s.display(); // Should show: 20 10

    // Check if the stack is empty
    cout << "Is stack empty? " << (s.isEmpty() ? "Yes" : "No") << endl;

    return 0;
}