динамический стек с использованием массивов C ++

Question

Я студент, и мой учитель дал мне эту «домашнюю работу». Я должен построить динамический стек, тривиальная часть заключается в том, что я не должен использовать структуру списка (например, связанные списки). Я думал, что реализация массива - это самое лучшее, но во время разработки я остановился на том моменте, когда мне пришлось увеличивать размер массива. Я не могу понять, как увеличить размер без потери данных. Кто-нибудь может мне помочь?

Answer 1

Я предполагаю, что вы не можете использовать std::vector и что вы должны использовать динамическое выделение памяти.

В том случае, если в текущем выделенном массиве вам не хватает места, вам нужно будет сделать что-то вроде:

• создать массив больше, чем текущий размер массива

• скопировать текущий массив в новый массив

• сделать новый массив текущим

• удалить старый массив

Вот простой и неполный класс, чтобы проиллюстрировать идею.

#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;
}

Выход:

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 

Остальное я оставлю вам для практики (например, деструктор для удаления выделенной памяти, верх для чтения данных, всплывающее окно для удаления элементов и т. Д.) Возможно, вы также захотите превратить его в шаблон, чтобы вы могли обрабатывать другие типы данных, отличные от int с тем же кодом.

Примечание: этот простой класс просто увеличивает вместимость на 5 при необходимости. Более распространенный подход заключается в удвоении емкости, когда требуется увеличение. Я оставлю это и вам, чтобы вы могли практиковаться.

Answer 2

Одна вещь, которую вы можете сделать, это создать новый массив с новым размером и затем скопировать в него старый. Что-то вроде этого - то, что вы ищете?

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