Stacks and Queues

3.1 Three in One: Describe how you could use a single array to implement three stacks.

• Brain storm:

  • We can divide the array into 3 equal parts, and then define methods on each individual stack.

#include <iostream>
#include <stdlib.h>
#include <math.h>
#include <utility>

using namespace std;

class stackArray3 {

public:
    stackArray3(int length) {

        if (length < 3) {
            cout << "size too small" << endl;
            return;
        }
        len = length;
        // create array
        stackArray = new int[length];

        // round down to ensure safe increments
        s1.first = ceil(length / 3) * 0;
        s2.first = ceil(length / 3) * 1;
        s3.first = ceil(length / 3) * 2;

        s1.second = s2.second = s3.second = 0;
    }

    void insert_top(int stackNum, int num) {
        switch (stackNum) {
        case 1:
            if (isFull(s1)) { cout << "stack is full" << endl; break; };
            stackArray[s1.first] = num;
            s1.first++; s1.second++;
            break;

        case 2:
            if (isFull(s2)) { cout << "stack is full" << endl; break; }
            stackArray[s2.first] = num;
            s2.first++; s2.second++;
            break;

        case 3:
            if (isFull(s3)) { cout << "stack is full" << endl; break; }
            stackArray[s3.first] = num;
            s3.first++; s3.second++;
            break;

        default: 
            cout << "invalid stack number" << endl;
            break;
        }
    }


    int top(int stackNum) {
        switch (stackNum) {
        case 1:
            if (isEmpty(s1)) { cout << "empty stack" << endl; return 0; }
            return stackArray[s1.first - 1];
            break;

        case 2:
            if (isEmpty(s2)) { cout << "empty stack" << endl; return 0; }
            return stackArray[s2.first - 1];
            break;

        case 3:
            if (isEmpty(s3)) { cout << "empty stack" << endl; return 0; }
            return stackArray[s3.first - 1];
            break;

        default:
            cout << "invalid stack number" << endl;
            break;
        }
    }

    int top_and_pop(int stackNum) {
        int ret;

        switch (stackNum) {
        case 1:
            if (isEmpty(s1)) { cout << "empty stack" << endl; return 0; }
            ret = stackArray[s1.first - 1];
            s1.first--; s1.second--;
            return ret;
            break;

        case 2:
            if (isEmpty(s2)) { cout << "empty stack" << endl; return 0; }
            return stackArray[s2.first - 1];
            ret = stackArray[s2.first - 1];
            s2.first--; s2.second--;
            return ret;
            break;

        case 3:
            if (isEmpty(s3)) { cout << "empty stack" << endl; return 0; }
            return stackArray[s3.first - 1];
            ret = stackArray[s2.first - 1];
            s2.first--; s2.second--;
            return ret;
            break;

        default:
            cout << "invalid stack number" << endl;
            break;
        }
    }

private:
    int *stackArray;
    int len;
    // index <-> count
    // current index in the stack <-> stack capacity
    std::pair<int, int> s1, s2, s3;

    bool isFull(pair<int, int> stackNum) {
        int num = ceil(len / 3);
        return stackNum.second >= ceil(len / 3);
    }

    bool isEmpty(pair<int, int> stackNum) {
        return stackNum.second == 0;
    }

};


int main()
{
    // even stack lengths -> cap = 2
    stackArray3 stackAr(6);

    stackAr.insert_top(1, 4);
    stackAr.insert_top(2, 5);
    stackAr.insert_top(3, 6);

    cout << stackAr.top(1) << endl;
    cout << stackAr.top(2) << endl;
    cout << stackAr.top(3) << endl;

    stackAr.insert_top(1, 7);
    stackAr.insert_top(2, 8);
    stackAr.insert_top(3, 9);

    cout << stackAr.top(1) << endl;
    cout << stackAr.top(2) << endl;
    cout << stackAr.top(3) << endl;

    // must be full
    stackAr.insert_top(1, 7);

    cout << endl << endl;


    // uneven stack lengths -> cap = 1
    stackArray3 stackAr2(4);

    stackAr2.insert_top(1, 4);
    stackAr2.insert_top(2, 5);
    stackAr2.insert_top(3, 6);

    cout << stackAr2.top(1) << endl;
    cout << stackAr2.top(2) << endl;
    cout << stackAr2.top(3) << endl;

    // must be full
    stackAr2.insert_top(1, 7);

}

3.2 Stack Min: How would you design a stack which, in addition to push and pop, has a function min which returns the minimum element? Push, pop and min should all operate in 0(1) time.

• Brain storm:

  • Build a stack that contains stackNodes. Every time an a element is push onto the the stack, the minimum value will be assessed. The minimum will always be contained onto top of the stack and will always be the minimum of its substack. We will maintain order of the min values as we add or remove more elements into the stack.

using namespace std;

class stackNode {
public:
    stackNode() {}
    stackNode(int val, int mini) : min(mini), value(val) {}

    int min;
    int value;

};

class minStack {
public:
    minStack(int len) {
        myArray = new stackNode[len];
        cur_index = 0;
        length = len;
    }

    void push(int num) {
        stackNode* temp;
        if (isFull()) { cout << "full" << endl; return; }

        // new stack
        else if (isEmpty()) {
            temp = new stackNode(num, num);
            myArray[cur_index] = *temp;
            cur_index++;
        }

        // input is smaller than min, so use it as the new min
        else if (myArray[cur_index - 1].min > num) {
            temp = new stackNode(num, num);
            myArray[cur_index] = *temp;
            cur_index++;
        }

        // input is larger than min, so set previous min
        else {
            temp = new stackNode(num, myArray[cur_index - 1].min);
            myArray[cur_index] = *temp;
            cur_index++;
        }
    }

    void pop() {
        if (isEmpty()) { cout << "empty" << endl; return; }
        --cur_index;
    }

    int min() {
        if (isEmpty()) { cout << "empty" << endl; return 0; }
        return top();
    }



private:
    stackNode *myArray;
    int cur_index;
    int length;

    bool isFull() {
        return cur_index > length;
    }

    bool isEmpty() {
        return cur_index == 0;
    }

    int top() {
        return myArray[cur_index-1].min;
    }
};


int main()
{
    cout << "cascading down" << endl;
    minStack stack(10);
    stack.push(5);
    stack.push(4);
    stack.push(3);
    stack.push(2);

    cout << stack.min() << endl;
    cout << endl << endl;

    cout << "cascading up" << endl;
    minStack stack2(10);
    stack2.push(2);
    stack2.push(3);
    stack2.push(4);
    stack2.push(5);

    cout << stack2.min() << endl;
    cout << endl << endl;

    cout << "mixed" << endl;
    minStack stack3(10);
    stack3.push(1);
    stack3.push(5);
    stack3.push(3);
    stack3.push(10);
    stack3.push(4);

    cout << stack3.min() << endl;
    cout << endl << endl;


    cout << "pop operations" << endl;
    stack3.pop(); // remove 4
    stack3.pop(); // remove 10
    stack3.pop(); // remove 3

    cout << stack3.min() << endl;
    cout << endl << endl;


    cout << "pop operations with min removed // cascading up" << endl;
    stack2.pop(); // remove 2
    stack2.pop(); // remove 3
    stack2.pop(); // remove 4

    cout << stack2.min() << endl;
    cout << endl << endl;


    cout << "pop operations with min removed // cascading down" << endl;
    stack.pop(); // remove 2
    stack.pop(); // remove 3
    stack.pop(); // remove 4

    cout << stack.min() << endl;
    cout << endl << endl;
}

3.3 Stack of Plates: Imagine a (literal) stack of plates. If the stack gets too high, it might topple. Therefore, in real life, we would likely start a new stack when the previous stack exceeds some threshold. Implement a data structure SetOfStacks that mimics this. SetOfStacks should be composed of several stacks and should create a new stack once the previous one exceeds capacity. SetOfStacks. push () and SetOfStacks. pop () should behave identically to a single stack (that is, pop ( ) should return the same values as it would if there were just a single stack).

FOLLOW UP Implement a function popAt (int index) which performs a pop operation on a specific sub-stack.

template <class T>
class Stack {
public:
    Stack(int capacity) {
        cap_s = capacity;
        iter_s = 0;

        data = new T[capacity];
    }

    ~Stack() {
        delete[]data;
    }

    bool push_s(T thing) {
        if (full()) {
            return false;
        }
        else {
            data[iter_s] = thing;
            iter_s++;
            return true;
        }

    }

    bool pop_s() {
        if (empty_s()) {
            return false;
        }
        else {
            iter_s--;
            return true;
        }
    }

    T top_s() {
        if (empty_s()) {
            return INT_MAX;
        }
        return data[iter_s - 1];
    }

    bool empty_s() {
        return iter_s == 0;
    }
private:
    // array
    T *data;

    int cap_s;
    int iter_s;

    bool full() {
        return iter_s == cap_s;
    }
};


template <class T>
class setOfStacks {
public:
    setOfStacks(const int capacity) {
        Stack<T> *s = new Stack<T>(capacity);
        stacks.push_back(s);
        cap = capacity;
        iter = 0;
    }

    void push(T thing) {
        // current stack is full
        if (stacks.at(iter)->push_s(thing) == false) {
            Stack<T> *s = new Stack<T>(cap);
            stacks.push_back(s);
            iter++;
            stacks.at(iter)->push_s(thing);
        }
    }

    void pop() {
        // everything is empty
        if (empty()) {
            cout << "stack is empty" << endl;
            return;
        }
        // current stack is empty
        else if (subEmpty()) {
            // delete current stack, and move on the previous
            delete stacks.at(iter);
            iter--;
            stacks.at(iter)->pop_s();
        }
        else {
            stacks.at(iter)->pop_s();
        }
    }

    T top() {
        // everything is empty
        if (empty()) {
            cout << "stack is empty" << endl;
            return INT_MAX;
        }
        // current stack is empty
        else if (subEmpty()) {
            // pop or top can be preformed at any point so
            // the share the same three lines
            delete stacks.at(iter);
            stacks.resize(stacks.size() - 1);
            iter--;
            stacks.at(iter)->top_s();
        }
        // current stack is empty
        else {
            return stacks.at(iter)->top_s();
        }
    }

    bool empty() {
        return (stacks.size() == 1 && stacks.at(iter)->empty_s());
    }

private:
    bool subEmpty() {
        return (stacks.at(iter)->empty_s());
    }

    int cap;
    int iter;
    vector<Stack<T>*> stacks;
};




int main() {
    cout << "// testing stack" << endl;
    Stack<int> s(50);

    for (int i = 0; i <= 50; i++) {
        s.push_s(i);
    }

    // overflow
    cout << s.push_s(51);
    pause();

    while (!s.empty_s()) {
        cout << s.top_s() << " ";
        s.pop_s();
    }

    // underflow
    cout << s.pop_s();
    pause();

    cout << "// testing set of Stacks" << endl;
    setOfStacks<int> ss(5);

    for (int i = 0; i <= 100; i++) {
        ss.push(i);
        cout << ss.top() << " ";
        //pause();
    }

    // next stack
    ss.push(101);
    //pause();

    while (!ss.empty()) {
        cout << ss.top() << " ";
        ss.pop();
    }
    pause();

    // completely empty
    ss.pop();
    pause();

}

3.4 Queue via Stacks: Implement a MyQueue class which implements a queue using two stacks.

• The idea is that stack.top() pushed back into another stack consequtively reverses the stack, so it can effectively become a queue.

template <class T>
class MyQueue {
public:
    MyQueue() {
    }

    void enqueue(T thing) {
        s1.push(thing);
    }

    T front() {
        if (empty()) return INT_MAX;
        while (!s1.empty()) {
            s2.push(s1.top());
            s1.pop();
        }

        return s2.top();
    }

    void dequeue() {
        while (!s1.empty()) {
            s2.push(s1.top());
            s1.pop();
        }
        if (s2.empty()) return;
        s2.pop();
    }

    bool empty() {
        return s2.empty() && s1.empty();
    }

private:
    stack<T> s1, s2;
};

int main() {
    MyQueue<int> q;
    cout << "enqueueing..." << endl;
    for (int i = 0; i < 100; i++) {
        q.enqueue(i);
        cout << i << " ";
    }
    cout << endl;

    cout << "dequeueing..." << endl;
    while (!q.empty()) {
        cout << q.front() << " ";
        q.dequeue();
        //pause();
    }

    pause();

    cout << "enqueueing..." << endl;
    for (int i = 0; i < 10; i++) {
        q.enqueue(i);
        cout << i << " ";
    }
    cout << endl;

    q.dequeue();
    q.dequeue();
    q.dequeue();

    cout << "dequeueing..." << endl;
    while (!q.empty()) {
        cout << q.front() << " ";
        q.dequeue();
        pause();
    }

}

3.5 Sort Stack: Write a program to sort a stack such that the smallest items are on the top. You can use an additional temporary stack, but you may not copy the elements into any other data structure (such as an array). The stack supports the following operations: push, pop, peek, and isEmpty.

• The main idea is to hold a temporary variable for the current element on the top, and then continuing pushing off elements from the second stack until you find an appropriate spot for the temp var.

• O(n^2) time, O(N) space

template <typename T>
stack<T> sortStack(stack<T> s1) {
    if (s1.size() <= 1) return s1;

    // start us off
    stack<T> temp;
    int pop_count = 0;
    temp.push(s1.top());
    s1.pop();

    while (!s1.empty()) {
        // grab top element of s1
        T temp2 = s1.top();
        s1.pop();

        // find correct position in temp
        while (!temp.empty() && temp.top() < temp2) {
            s1.push(temp.top());
            temp.pop();
            pop_count++;
        }
        temp.push(temp2);

        // place back
        for (int i = 0; i < pop_count; i++) {
            temp.push(s1.top());
            s1.pop();
        }
        pop_count = 0;
    }

    return temp;
}


int main() {
    vector<int> v = { 1,5,2,10,3,3,3,3,3,100,1001,232 };
    stack<int> s;
    for (auto i : v) {
        s.push(i);
    }

    stack<int> s2 = sortStack(s);
    while (!s2.empty()) {
        cout << s2.top() << " ";
        s2.pop();
    }
    pause();
}