Как сделать стек динамическим?

Question

Вот небольшая программа с моим классом Stack:

#include <iostream> 

using namespace std; 

#include <iomanip> 

template <typename T> 
class Stack 
{ 
private: 
    T *stackPtr; 
    int size; 
    T top; 
public: 
    Stack(int = 10); 
    ~Stack(); 
    bool push(const T ); 
    bool pop(); 
    void printStack(); 
}; 

int main() 
{ 
    Stack <int> myStack(5); 


    cout << "Push 5 elements to stack: "; 
    int ct = 0; 
    while (ct++ != 5) 
    { 
     int temp; 
     cin >> temp; 
     myStack.push(temp); 
    } 

    myStack.printStack(); 

    cout << "\nErasing two elements:\n"; 

    myStack.pop(); 
    myStack.pop(); 
    myStack.printStack(); 

    return 0; 
} 


template <typename T> 
Stack<T>::Stack(int s) 
{ 
    size = s > 0 ? s: 10; 
    stackPtr = new T[size]; 
    top = -1; 
} 


template <typename T> 
Stack<T>::~Stack() 
{ 
    delete [] stackPtr; 
} 


template <typename T> 
bool Stack<T>::push(const T value) 
{ 
    if (top == size - 1) 
     return false; 

    top++; 
    stackPtr[top] = value; 

    return true; 
} 


template <typename T> 
bool Stack<T>::pop() 
{ 
    if (top == - 1) 
     return false; 

    stackPtr[top] = 0; 
    top--; 

    return true; 
} 


template <typename T> 
void Stack<T>::printStack() 
{ 
    for (int ix = size -1; ix >= 0; ix--) 
     cout << "|" << setw(4) << stackPtr[ix] << endl; 
} 

Итак, для того, чтобы использовать такой стек, я должен объявить его размер в конструкторе перед использованием, как Stack<int> newstack(10), если мне нужен 10 элементов. Итак, что делать, если я не знаю конечный размер стека? Как заставить его расти динамично, просто нажав на него элементы? Я искал решение, но все мои идеи приходят к подсчету элементов, а затем объявляют стек для соответствия количеству элементов.

Answer 1

Прежде всего, вы знаете, что C++ имеет встроенную встраиваемость , не так ли? Для остальной части ответа я предполагаю, что у вас есть причина не использовать его (возможно, это учебное упражнение).

---

очень наивный способ добиться того, что вы хотите, будет:

1. На каждом добавлении элемента, выделить новый массив размера + 1 с new[].
2. Скопируйте все элементы старого массива и новый элемент в новый массив.
3. delete[] старый массив.
4. Марка stackPtr указывает на новый массив.

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

struct CannotUseInThisStack 
{ 
    CannotUseInThisStack(int) {} // no default constructor 
}; 

Stack<CannotUseInThisStack> s; // error 

Реальное решение: Не используйте new[] и delete[].Реализуйте свой стек с точки зрения std::vector (или в терминах std::deque, что точно соответствует std::stack!). std::vector поддерживает динамическое выращивание из коробки гораздо лучше, без непрерывного перераспределения при каждом добавлении элемента и без требования возможности построения по умолчанию T.

Конечно, это по праву приводит к вопросу о том, как std::vector может все это сделать.

Ответ заключается в том std::vector, или, вернее, его стандартная распределителем, std::allocator, является не реализуется себя с точки зрения new[] и delete[], но с точки зрения размещения нового. Разделение памяти и построение элементов разделены. См. std::allocator:allocate. Это решает проблему с отсутствующими конструкторами по умолчанию. Первоначальная память выделяется сначала, а новый элемент затем строится в этой необработанной ячейке памяти, используя конструктор копирования (в C++ 11 у вас также есть идеальная пересылка для построения T на месте, но это немного не по теме) ,

Использование места размещения также позволяет экспоненциально увеличивать емкость std::vector. Контейнеру не нужно перераспределять память каждый раз, когда вы добавляете элемент; он заранее выделяет необработанную память для большего количества элементов (подобно тому, что делает Кристоф в своем ответе). Перераспределение происходит только при превышении текущей емкости.

С new[] и delete[] такой сложный механизм был бы невозможным.

---

Вообще, если вы хотите понять, серьезный дизайн контейнера, посмотрите на то, как ваш компилятор реализует все C++ стандартных контейнеров.

Answer 2

Я предполагаю, что предполагает использование std::stack() не был бы ответ вы ожидаете ;-)

Вам просто нужно выделить больше места, когда вы достигнете предела:

template <typename T> 
bool Stack<T>::push(const T value) 
{ 
    if (top == size - 1) { 
     //return false; 
     size_t s = size + 10;  // for example increase by 10 
     T *ps = new (nothrow) T[s]; // allocate new region 
     if (ps==nullptr) 
      return false;   // out of memory 
     for (size_t i=0; i<size; i++) 
      ps[i] = stackPtr[i]; 
     delete[] stackPtr; 
     stackPtr = ps; 
     size = s;     // stack is now bigger, 
    }        // so continue as if there was no problem 

    top++; 
    stackPtr[top] = value; 

    return true; 
} 

Вопрос заключается в том, на сколько увеличить ваш стек. Вы можете использовать постоянный подход, как здесь, но лучше рассмотреть переменную-член и инициализировать ее в своем конструкторе.

Edit: Я использовал новый с nothrow, чтобы избежать выбрасывания исключения в случае нехватки памяти, потому что ваша подпись предусматривает код возврата на успех операции.

Answer 3

Вы всегда можете сделать это, используя связанный список. Если вы хотите вставить в стек, вы просто поместите узел во главе связанного списка. Чтобы поп, вы просто удалите его. Теперь вы можете подумать, как реализовать такие утверждения, как Stack S=new Stack(5);.

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