6
\$\begingroup\$

One of the questions that is presented in Chapter 3 for Cracking the Coding Interview is this:

Describe how you could use a single array to implement 3 stacks

I've implemented a solution to this problem in C++. My assumption is that the array is a static array that is not growable (unlike a dynamic array).

I would like the focus be not only on the answer's correctness, but also other stuff pertaining to proper design of a generic C++ container. Including but not limited to exception guarantees, proper implementation of Rule of Five, space/time efficiency, handling all possible types for T (including if T has no default constructor), coding style and whatever else you think an interviewer may look for when asking this question.

Code

#pragma once

template <typename T>
class ArrayStack
{
public:
    ArrayStack(int size = 100);
    ArrayStack(const ArrayStack& other);
    ArrayStack(ArrayStack&& other);
    ~ArrayStack();

    ArrayStack<T>& operator= (const ArrayStack& other);
    ArrayStack<T>& operator= (ArrayStack&& other);

    friend void swap(ArrayStack& A, ArrayStack& B)
    {
        using std::swap;

        swap(A.arr, B.arr);
        swap(A.arrSize, B.arrSize);
        swap(A.stack1Index, B.stack1Index);
        swap(A.stack2Index, B.stack2Index);
        swap(A.stack3Index, B.stack3Index);
    }

    void push(T item, int stackNum);
    void pop(int stackNum);
    T& top(int stackNum);

private:
    T* arr;
    size_t stack1Index;
    size_t stack2Index;
    size_t stack3Index;
    size_t arrSize;
};

template <typename T>
ArrayStack<T>::ArrayStack(int size)
    :arr(static_cast<T*>(::operator new(sizeof(T)*size)))
    , arrSize(size)
    , stack1Index(0)
    , stack2Index(size / 3)
    , stack3Index(2 * size / 3)
{}

template <typename T>
ArrayStack<T>::ArrayStack(const ArrayStack& other)
    :arr(static_cast<T*>(::operator new(sizeof(T)*other.arrSize)))
    , arrSize(other.arrSize)
    , stack1Index(other.stack1Index)
    , stack2Index(other.stack2Index)
    , stack3Index(other.stack3Index)
{
    try
    {
        for (std::size_t i = 0; i < other.arrSize; i++)
            new (arr + i) T(std::move(other.arr[i]));

    }
    catch (...)
    {
        for (std::size_t i = arrSize; i < 0; i--)
            arr[i - 1].~T();

        ::operator delete(arr);
        throw;
    }
}

template <typename T>
ArrayStack<T>::ArrayStack(ArrayStack<T>&& other)
{
    swap(*this, other);
}

template <typename T>
ArrayStack<T>::~ArrayStack()
{
    for (std::size_t i = arrSize; i > 0; i--)
        arr[i - 1].~T();

    ::operator delete(arr);
}

template <typename T>
ArrayStack<T>& ArrayStack<T>::operator =(const ArrayStack<T>& other)
{
    ArrayStack tmp(other);
    swap(*this, tmp);
    return *this;
}

template <typename T>
ArrayStack<T>& ArrayStack<T>::operator =(ArrayStack<T>&& other)
{
    swap(*this, other);
    return *this;
}

template <typename T>
void ArrayStack<T>::push(T item, int stack)
{
    if (stack <= 0 || stack >= 4)
        throw new std::runtime_error("No such stack");

    if (stack == 1)
    {
        if (stack1Index > arrSize / 3 - 1)
            throw new std::runtime_error("No room left in Stack 1");

        new (arr + stack1Index) T(std::move(item));
        stack1Index++;
    }
    else if (stack == 2)
    {
        if (stack2Index > 2 * arrSize / 3 - 1)
            throw new std::runtime_error("No room left in Stack 2");

        new (arr + stack2Index) T(std::move(item));
        stack2Index++;
    }
    else
    {
        if (stack3Index > arrSize - 1)
            throw new std::runtime_error("No room left in Stack 3");

        new (arr + stack3Index) T(std::move(item));
        stack3Index++;
    }
}

template <typename T>
void ArrayStack<T>::pop(int stack)
{
    if (stack <= 0 || stack >= 4)
        throw new std::runtime_error("No such stack");

    if (stack == 1)
    {
        if (stack1Index == 0)
            throw new std::runtime_error("Nothing in Stack 1 to pop");

        arr[stack1Index - 1].~T();
        stack1Index--;
    }
    else if (stack == 2)
    {
        if (stack2Index < arrSize/3)
            throw new std::runtime_error("Nothing in Stack 2 to pop");

        arr[stack2Index - 1].~T();
        stack2Index--;
    }
    else
    {
        if (stack3Index < 2* arrSize /3)
            throw new std::runtime_error("Nothing in Stack 3 to pop");

        arr[stack3Index - 1].~T();
        stack3Index--;
    }
}

template <typename T>
T& ArrayStack<T>::top(int stack)
{
    if (stack <= 0 || stack >= 4)
        throw new std::runtime_error("No such stack");

    if (stack == 1)
    {
        if (stack1Index == 0)
            throw new std::runtime_error("Nothing in Stack 1 to return");

        return arr[stack1Index - 1];
    }
    else if (stack == 2)
    {
        if (stack2Index < arrSize / 3)
            throw new std::runtime_error("Nothing in Stack 2 to return");

        return arr[stack2Index - 1];
    }
    else
    {
        if (stack3Index < 2 * arrSize / 3)
            throw new std::runtime_error("Nothing in Stack 3 to return");

        return arr[stack3Index - 1];
    }
}

Generic Test Object

#pragma once

class TestObject
{
    int testVal;

    public:
        TestObject(int i)
            :testVal(i)
        {}

        int getTestVal();

};

int TestObject::getTestVal()
{
    return testVal;
}

Test Code

#include "stdafx.h"
#include "ArrayStack.h"
#include "TestObject.h"
#include <iostream>

void testArrayStack();

int main()
{
    testArrayStack();

    system("pause");
    return 0;
}


void testArrayStack()
{
    ArrayStack<char> test1;
    test1.push('A', 1);
    test1.push('B', 2);
    test1.push('C', 3);

    std::cout << test1.top(1) << "\n";
    std::cout << test1.top(2) << "\n";
    std::cout << test1.top(3) << "\n";

    ArrayStack<char> test2(test1);

    std::cout << test2.top(1) << "\n";
    std::cout << test2.top(2) << "\n";
    std::cout << test2.top(3) << "\n";

    test2.push('A', 1);
    test2.push('M', 1);
    test2.push('A', 1);

    test2.push('B', 2);
    test2.push('M', 2);
    test2.push('B', 2);

    test2.push('C', 3);
    test2.push('M', 3);
    test2.push('C', 3);

    test2.pop(1);
    test2.pop(2);
    test2.pop(3);

    std::cout << test2.top(1) << "\n";
    std::cout << test2.top(2) << "\n";
    std::cout << test2.top(3) << "\n";

    ArrayStack<TestObject> dummy;
    dummy.push(TestObject(5), 1);
    dummy.push(TestObject(7), 2);
    dummy.push(TestObject(8), 2);

    ArrayStack<TestObject> test3;
    test3 = dummy;

    test3.pop(2);

    std::cout << test3.top(1).getTestVal() << "\n";
    std::cout << test3.top(2).getTestVal() << "\n";
}

Test Output

Test output

\$\endgroup\$
  • \$\begingroup\$ >= 4 should be >= 3? \$\endgroup\$ – Joop Eggen Aug 2 '16 at 9:05
  • \$\begingroup\$ @JoopEggen no because if (stack <= 0 || stack >= 4) limits stack to be 1,2 or 3, which are the 3 stacks allowed to be passed in \$\endgroup\$ – Mantracker Aug 2 '16 at 9:12
  • \$\begingroup\$ I would suggest to use the "valid" values for easier reading (and making those some constants), so if (stack < 1 || 3 < stack) invalid_stack.... Most of the time the valid value can be used for all the test, together with < or <=. Although sometimes +-1 is inevitable, then having if (stack < STACK_MIN-1) ... still feels easier to read for me. \$\endgroup\$ – Ped7g Aug 5 '16 at 21:14
4
\$\begingroup\$

Don't use system("pause")

system("pause") doesn't work on Linux (although I don't think it matters, the console stays open), and so your code is not cross-platform. Please see this for additional details.

Don't catch every exception, ignoring the type

It's not good practice to catch every exception that can happen (i.e. catch (...)). Rather, use a const& to the type of the exception that should be handled:

//Catches exceptions thrown by new
catch(const std::bad_array_new_length&)
//...

Don't use new when throwing exceptions

There is no need to create every exception on the heap when throwing them. This results in memory leak if the you forget to delete the exception in the catch clause, and should be avoided, just like you would avoid using int* a = new int(); every time you want an integer :) Here is some further reading

//throw a regular object, not a pointer
throw std::runtime_error("No such stack");

Provide a const top() function

If I have a const ArrayStack<char>, I can't do anything with it, not even get the top element. This is probably not intended, so consider making a const version of top().

If you don't want to implement the logic twice, there is an "elegant" solution to this.

Copy constructor doesn't allow the parameter to be move constructed

Because your copy constructor is taking by const&, the compiler can't optimize and move construct tmp when appropriate, instead it will call the constructor, possibly creating a new object, which is unnecessary overhead. Passing by value fixes this problem.

template <typename T>
ArrayStack<T>& ArrayStack<T>::operator =(ArrayStack<T> other);

Hope that helps! :)

\$\endgroup\$
  • \$\begingroup\$ With the introduction of move constructors in c++11, is it always better to pass by value for the copy assignment operator in every case? \$\endgroup\$ – Mantracker Aug 2 '16 at 19:11
  • \$\begingroup\$ @Mantracker Jup :) \$\endgroup\$ – Rakete1111 Aug 2 '16 at 22:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.