Реализация стека с использованием Array (способы улучшения кода)

Question

Нужно реализовать стек, используя только массив, методы: push, pop, print .Сама задача: реализовать стек, используя только массив.Единственный раз, когда компилятор должен выделять память, это функция set_size .Текущая версия кода работает достаточно хорошо, но я ищу способы улучшить ее exec-time / сложность / удобочитаемость и т. Д. Есть идеи?Заранее спасибо.

#include <vector>
#include <string>

template <class T>
class Stack
{
 int size = 0;
 T* Array;
 int top = 0;

public:
 Stack(size_t Size);
 ~Stack()
 {
     delete[] Array;
 }
 void push(T element);
 void pop();
 void print();
};
template <class T>
Stack<T>::Stack(size_t Size)
{
 size = Size;
 top = -1;
 Array = new T[size];
}
template <class T>
void Stack<T>::push(T element)
{
 if (top >= (size - 1))
 {
     std::cout << "overflow" << std::endl;
 }
 else
 {
     Array[++top] = element;
 }
}
template <class T>
void Stack<T>::pop()
{
 if (top < 0)
 {
     std::cout << "underflow" << std::endl;
 }
 else
 {
     std::cout << Array[top--] << std::endl;
 }

}
template <class T>
void Stack<T>::print()
{
 if (top == -1)
 {
     std::cout << "empty" << std::endl;
 }
 int i = top;
 while (i > -1)
 {
     std::cout << Array[i--] << " ";
 }
 std::cout << std::endl;
}
template <class T>
Stack<T> set_size(int Size)
{
 return Stack<T>(Size);
}

int main()
{
 auto stack = set_size<std::string>(5);
 stack.push("hello");
 stack.push("hi");
 stack.push("hey");
 stack.push("greetings");
 stack.push("welcome");
 stack.print();
 stack.pop();
 stack.pop();
 stack.print();
 return 0;
}```

Answer 1

Вместо размещения массива в куче вы можете использовать его в стеке.Это возможно, поскольку вы можете передать размер в качестве параметра шаблона.Это было бы лучше для производительности, чем для памяти в куче.

Я бы использовал size_t (unsigned int) в качестве типа размера, чтобы размер не мог быть отрицательным;затем в вашей функции push () приведите его к int, чтобы сравнить с top.

template <typename T, size_t const Size>
class Stack
{
    private:
    T Array[Size];
    int top;

    public:
    Stack()
    {
        top = -1;
    }

    void push(T element)
    {
        if (top >= static_cast<int>(Size)-1)
        {
           std::cout << "overflow" << std::endl;
        }
        else
        {
            Array[++top] = element;
        }
    }

    void pop()
    {
         if (top < 0)
         {
             std::cout << "underflow" << std::endl;
         }
         else
         {
             std::cout << Array[top--] << std::endl;
         }
    }

    void print()
    {
        if (top < 0)
        {
           std::cout << "empty" << std::endl;
        }

        int i=top;
        while (top > -1)
        {
           std::cout << Array[i--] << " ";
        }
        std::cout << std::endl;
    }

};

Теперь нет необходимости в функции set_size, внешней по отношению к классу.Вы можете создать экземпляр как это:

Stack<std::string, 3> stack;

Answer 2

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

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

Answer 3

Ваша основная проблема связана с преобразованием типа между указателем стека top в размер стека size.

top - это int, то есть со знаком тип.size_t является целым типом без знака .

При тестировании (top >= (size - 1)), top преобразуется в unsigned int и затем рассматривается как UINT_MAX вместо -1,который всегда> = для любого другого unsigned int.

Вы можете использовать size_t в качестве указателя стека, что означает, что вы не можете использовать отрицательное значение, или преобразовать (size - 1) в значение со знаком допо сравнению с top (но это последнее решение означает, что вы должны убедиться, что размер, указанный вами как size_t, не слишком велик для преобразования в целое число со знаком).

У вашей функции печати также есть две проблемы:

• в первом тесте вы назначаете -1 на top вместо сравнения значений
• , вы изменяете указатель стека top, так что ваш стек находится внесовместимое состояние после звонка на print()