.. include:: ../global.rst

.. index::
    pair: C++; Stacks and Queues

Stacks and Queues
==========================

.. _stacksAndQueues:

- 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

.. code-block:: cpp

    #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;
    }