Stack and Queues Problems

Stack Templated Example

• Heres a Stack templated for any types

Stack (Stack.h)

#include <utility>

template <typename T>
class Stack
    {
        private:
            struct Node
            {
                Node(T &v, Node *n): value(v), next(n){}
                T value;       
                Node *next;  
            };

            Node *top;              
            size_t stackSize;       

        public:
            Stack() : top(nullptr), stackSize(0){}   // normal constructor

            ~Stack()
            {
                while (!isEmpty())
                    pop();
            }

            template <typename U>
            void push(U &&value) {       // Why the U and the &&
                auto n = new Node(value, top); // new keyword to insert a new node into our Stack
                std::cout << "n: " << n->value << std::endl;
                top = n; // pass address to top of the stack
                ++stackSize;
            }

            T &peek()
            {
                if (!top)
                    throw StackIsEmptyException();
                return top->value; // return the top value in the Stack
            }

            T pop()
            {
                if (!top)
                {   // if empty
                    throw StackIsEmptyException();
                }
                else {

                    auto value(top->value);
                    auto n = top;
                    top = n->next; // find address for next value on the top of the stack  
                    delete n;
                    --stackSize;
                    return value;
                }
            }

            bool isEmpty() const
            {
                return !top;
            }

            size_t size() const
            {
                return stackSize;
            }

            class StackIsEmptyException{};

            void print(){
                // prints "Stack"
                // Extra Function added
                Node* ptr;
                if (top == NULL){
                    std::cout << "STACk is EMpty" << std::endl;
                }
                else{
                    ptr = top;
                    std::cout << "The Elements are: ";
                    while (ptr != NULL){
                        std::cout << ptr->value << " ";
                        ptr = ptr->next;
                    }
                }
               
            }
                
};

1. Three in One

• Describe how you could use a single array to implement three stacks
• UMMMM

2. Stack Min.

• Lets use our stack function above and implement

#include <iostream>
#include "stack.h"

template<typename T>
class StackMin{

    private:
        Stack<T> stack;
        Stack<T> minStack; // hold "min values"

    public:
        template <typename U>
        void push(U&& value){
            if (minStack.isEmpty() || value <= minStack.peek()){
                minStack.push(value);
            }
            stack.push(value);
        }

        T peek(){ // Regular "Stack"
            return stack.peek();
        }

        T min(){ // Peek for minStack
            return minStack.peek();
        }
        T pop(){
            auto value = stack.pop();
            if (value == min() ){
                minStack.pop();
            }
            return value;
        }

        bool isEmpty(){
            return stack.isEmpty();
        }
};

Example Main Function to use StackMin Code

#include <iostream>
#include "stackMin.h"


int main() {

    StackMin<int> stack;
    for (auto v : {5, 10, 4, 9, 3, 3, 8, 2, 2, 7, 6})
    {
        stack.push(v);
        std::cout << "Pushed value: " << v << ", min value: " << stack.min() << std::endl;
    }
    while (!stack.isEmpty())
    {
        auto v = stack.pop();
        std::cout << "Popped value: " << v;
        if (stack.isEmpty())
            std::cout << ", stack is empty" << std::endl;
        else
            std::cout << ", min value: " << stack.min() << std::endl;
    }
}

Output:

Pushed value: 5, min value: 5
Pushed value: 10, min value: 5
Pushed value: 4, min value: 4
Pushed value: 9, min value: 4
Pushed value: 3, min value: 3
Pushed value: 3, min value: 3
Pushed value: 8, min value: 3
Pushed value: 2, min value: 2
Pushed value: 2, min value: 2
Pushed value: 7, min value: 2
Pushed value: 6, min value: 2
Popped value: 6, min value: 2
Popped value: 7, min value: 2
Popped value: 2, min value: 2
Popped value: 2, min value: 3
Popped value: 8, min value: 3
Popped value: 3, min value: 3
Popped value: 3, min value: 4
Popped value: 9, min value: 4
Popped value: 4, min value: 5
Popped value: 10, min value: 5
Popped value: 5, stack is empty

Stack of plates Questions

• Use stack data structure to above (in example one)

Queue Via Stacks

Sort Stack

Animal Shelter Question