dynamic stack using arrays C++

Question

I am a student and my teacher gave me this "homework". I have to build a dynamic stack, the trivial part is that I mustn't use a list structure (e.g. linked lists). What I thought was that an array implementation was the bets thing, but during the development I stopped at the point I had to increment the array size. I can't figure out how to increment the size without losing data. Can someone help me ?

Answer 1

One thing you can do is creating a new array with the new size and then copying the old one in it. Something like this is what you're looking for?

const int new_size = old_size + 1;
int new_array[new_size];
std::copy(old_array, old_array+old_size, new_array);

Answer 2

I assume that your not allowed to use std::vector and that you must use dynamic memory allocation.

In that case when you run out of space in the currently allocated array, you'll have to do something like:

• create an array larger than the current array size

• copy current array to the new array

• make the new array the current

• delete the old array

Here is a simple and incomplete class to illustrate the idea.

#include <iostream>
#include <algorithm>
using namespace std;

class myStack
{
    size_t capacity {0};
    size_t size {0};
    int *data {nullptr};
public: 
    void push(int n)
    {
        if (size == capacity)
        {
            cout << "Increase capacity by 5 elements" << endl;
            capacity += 5;
            int* tmp = new int[capacity];
            copy_n(data, size, tmp);
            swap(data, tmp);
            delete[] tmp;
        }

        data[size] = n;
        ++size;
    }

    void print_all()
    {
        cout << "capacity=" << capacity << endl;
        for (size_t i = 0; i < size; ++i)
            cout << data[i] << " ";
        cout << endl;
    }
};

int main(void) {
    myStack s;
    s.push(1);
    s.push(2);
    s.push(3);
    s.push(4);
    s.push(5);
    s.print_all();
    s.push(6);
    s.print_all();
    return 0;
}

Output:

Increase capacity by 5 elements
capacity=5
1 2 3 4 5 
Increase capacity by 5 elements
capacity=10
1 2 3 4 5 6 

I'll leave the rest to you for practice (e.g. destructor to delete allocated memory, top to read data, pop to remove elements etc.) Probably you would also like to turn it into a template so that you can handle other data types than int with the same code.

Notice: This simple class just grows the capacity by 5 when necessary. A more common approach is to double the capacity when an increase is needed. I'll leave that to you as well so that you can practice.