Implement 3 stacks using a single array in C++

Question

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

• Joop Eggen: >= 4 should be >= 3?
• Mantracker: @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
• Ped7g: 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.

Answer 1

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! :)

• Mantracker: 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?
• Rakete1111: @Mantracker Jup :)

Answer 2

Don't use three separate named variables for the three stack tops. You should be able to have a single indexable piece of code when doing the pushing/popping rather than a switch statement.

I think the point of having three stacks in one array is to allow the sum of all three to use the full capacity, in any permutation. The way you did it is identical to simply using three independent stack array objects that happen to be located in adjacent memory, and you ought to just do that if that's really the goal.