3-stack implementation with a single array

Question

I'm teaching myself data structures and would really appreciate some feedback on my stack implementation.

A couple of things I'm not sure if I should be doing:

• creation of the array and pointer using new
• style

// Implement 3 stacks with one array 
#include <iostream>


class SingleArrayStacks{
    private:
        int stack_size;
        int *array;
        int *pointers;
        int get_top_position(int stack_num){
            return (stack_num * stack_num)  + pointers[stack_num]; 
        }

    public:
        SingleArrayStacks (int array_size = 100, int num_stacks = 3) {
            array = new int[array_size];    
            pointers = new int[num_stacks]; 
            stack_size =  array_size / num_stacks;
            std::fill_n(pointers, num_stacks, -1);
        }

        ~SingleArrayStacks (){
            delete[] array;
            delete[] pointers;
        }

        void print_stack (int stack_num) const {
            std::cout << "Current stack state: ";
            for (int i = 0; i < sizeof(array); i++) {
                std::cout << array[i];
            }
            std::cout << std::endl;
        }

        bool is_empty(int stack_num) const {
            return pointer[stack_num] == -1; 
        }

        void push (int stack_num, int val) {
            if (pointers[stack_num] > stack_size) {
                throw std::runtime_error("Stack is full");
            } else {
                array[get_top_position(stack_num) + 1] = val;
                pointers[stack_num]++;
            }
        }

        int pop(int stack_num){
            if (is_empty(stack_num) {
                throw std::runtime_error("Stack is empty");
            } else {
                int val = array[get_top_position(stack_num)];
                array[get_top_position(stack_num)] = NULL;
                pointers[stack_num]--;
                return val;
            }
        }

        int top(int stack_num){
            if (is_empty(stack_num) {
                throw std::runtime_error("Stack is empty");
            } else {
                return array[get_top_position(stack_num)];
            }
        }
};

Answer 1

Compiler errors:

You code did not compile under Clang! It would not compiler anywhere for that matter, as it has a few syntax errors:

• In method is_empty(), pointer is not declared. It should be pointers (plural).

• In both pop() and top() methods, this line is broken:

  if (is_empty(stack_num) {
  //                    ^-------- Missing a `)` here!
  

Compiler warnings:

Always compile with warnings turned on and set them to the highest level practical. If you have the habit of ignoring warnings, try compiling with "warnings as errors" (-Werror for Clang and GCC) to force yourself into fixing them.

That said, your code only produced one warning, after the errors above where fixed:

array[get_top_position(stack_num)] = NULL;
//                                   ^^^^--------- implicit conversion of NULL constant to 'int'

NULL is not the same as int. In fact, an implementation is free to define NULL to whatever, so don't assume it will be convertible to an integer on all compilers/platforms.

Code review:

Now if I get the idea behind your code, you intend to have a single array with several stack sharing this array. Your implementation doesn't seem to be doing that correctly. I could not test it thoroughly, but the helper array pointers, which doesn't store pointers by the way, seems questionable. The method get_top_position() also seems a bit contrived to me. print_stack() is broken, so I couldn't print the stacks to validate the state of the structure.

I would suggest that you attempt to simplify this by storing actual pointers (or indexes) to the sub-array inside the main array. Then you won't need any additional offset calculation once pushing/poping. You also have the advantage that all stacks share the same size.

               main array of ints:
    +--+--+--+--+--+--+--+--+--+--+--+--+----
    |  |  |  |  |  |  |  |  |  |  |  |  | ...
    +--+--+--+--+--+--+--+--+--+--+--+--+----
    |           |           |           |
    V           V           V           V
    +-----------+-----------+-----------+----
    |  stack 0  |  stack 1  |  stack 2  | ...
    +-----------+-----------+-----------+----
    |           |           |           |
    V           V           V           V
pointer[0]  pointer[1]  pointer[2]  pointer[N] ...

Overall code improvements:

• sizeof misuse: This is not doing what you expect:

  for (int i = 0; i < sizeof(array); i++) {
  

  sizeof is a compile-time operator, so it cannot infer the size of dynamically allocated arrays, only arrays in which the size is known at compile-time (e.g.: char buf[128]) can have the size inferred with sizeof. You must keep a member variable with the size of the stacks and another with the main array's.

• top() only inspect data, so it should also be a const method.

• Simplify if-else logic where it is not needed. Example:

  if (is_empty(stack_num)) {
      throw std::runtime_error("Stack is empty");
  } else {
      return array[get_top_position(stack_num)];
  }
  

  No need to keep the if-else when both paths will exit the function.

  if (is_empty(stack_num)) {
      throw std::runtime_error("Stack is empty");
  }
  return array[get_top_position(stack_num)];
  

• Instead of hardcoding cout in print_stack(), you could take the output parameter as an std::ostream &. However, such function is asking to become an output stream operator.

• Manual memory management (with new/delete) is a dated practiced in C++. Even for custom containers, the use of smart pointers is strongly advised. I would replace the raw pointers by at least a std::unique_ptr or even better a std::vector.