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

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"
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)
``````
``````

Updated: