Cracking The Coding Interview/Q 3.3

From Software Engineers Wiki
Jump to: navigation, search

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 SetOf Stacks that mimics this. SetOf Stacks should be composed of several stacks and should create a new stack once the previous one exceeds capacity. SetOf Stacks. push() and SetOf Stacks. pop() should behave identically to a single stack (that is, popO 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.

Answer

#include <stack>
#include <vector>

template <typename T> class COneStack {
private:
        const unsigned int m_threshold = 4;
        std::stack<T> m_stack;
public:
        COneStack() {}
        ~COneStack() {}

        bool isEmpty(void) { return m_stack.empty(); }
        bool isFull(void) { return m_stack.size() >= m_threshold; }
        bool push(T val) { if (isFull()) return false; m_stack.push(val); return true; }
        bool pop(T &val) { if (isEmpty()) return false; val = m_stack.top(); m_stack.pop(); return true; }
};

template <typename T> class CSetOfStack {
private:
        std::vector<COneStack<T> *> m_stacks;
        int m_numOfStacks;
        COneStack<T> *m_curStack;
        int m_curStackIndex;
public:
        CSetOfStack() : m_numOfStacks { 1 }, m_curStack { new COneStack<T> }, m_curStackIndex { 0 } { m_stacks.push_back(m_curStack); }
        ~CSetOfStack() {}

        bool push(T val) {
                if (m_curStack->isFull()) {
                        if (++m_curStackIndex == m_numOfStacks) {
                                m_curStack = new COneStack<T>;
                                m_stacks.push_back(m_curStack);
                                ++m_numOfStacks;
                        } else {
                                m_curStack = m_stacks[m_curStackIndex];
                        }
                }
                return m_curStack->push(val);
        }
        bool pop(T &val) {
                if (m_curStack->isEmpty()) {
                        if (m_curStackIndex == 0)
                                return false;
                        m_curStack = m_stacks[--m_curStackIndex];
                }
                return m_curStack->pop(val);
        }
};

Test program:

int main(void)
{
        CSetOfStack<int> my_stack;
        int i, val;

        for (i = 0; i < 50; ++i)
                my_stack.push(i);
        while (my_stack.pop(val))
                std::cout << val << " ";
        std::cout << std::endl;

        for (i = 100; i < 175; ++i)
                my_stack.push(i);
        while (my_stack.pop(val))
                std::cout << val << " ";
        std::cout << std::endl;

        for (i = 200; i < 225; ++i)
                my_stack.push(i);
        while (my_stack.pop(val))
                std::cout << val << " ";
        std::cout << std::endl;

        return 0;
}

Test result:

49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 
174 173 172 171 170 169 168 167 166 165 164 163 162 161 160 159 158 157 156 155 154 153 152 151 150 149 148 147 146 145 144 143 142 141 140 139 138 137 136 135 134 133 132 131 130 129 128 127 126 125 124 123 122 121 120 119 118 117 116 115 114 113 112 111 110 109 108 107 106 105 104 103 102 101 100 
224 223 222 221 220 219 218 217 216 215 214 213 212 211 210 209 208 207 206 205 204 203 202 201 200 
Personal tools
Namespaces

Variants
Actions
Navigation
Toolbox