Как реализовать массив стеков в c ++?

Question

Представьте себе стопку тарелок. Если стопка станет слишком высокой, она может опрокинуться. Поэтому в реальной жизни мы, скорее всего, запустим новый стек, когда предыдущий стек превысит некоторый порог. Реализуйте структуру данных SetOfStacks , которая имитирует это. SetOfStacks должен состоять из нескольких стеков и должен создавать новый стек, как только предыдущий превышает емкость. SetOfStacks.pu sh () и SetOfStacks.pop () должны вести себя идентично одному стеку (то есть pop () должен возвращать те же значения, что и если бы там были просто одной стопкой). Реализуйте функцию popAt (int index), которая выполняет операцию pop на указанном субстеке c.

Answer 1

Есть несколько требований. Сначала мы создадим структуру данных, содержащую несколько других стеков. Для этого мы определим класс.

Мы будем использовать std::vector, который будет содержать столько std::stack, сколько необходимо. Мы также добавляем переменную, которая будет определять максимальный размер стека для всех std::stack в std::vector из std::stack s.

Затем мы реализуем 3 функции. Начнем с функции push. Это довольно просто.

Сначала мы проверяем, достаточно ли вложенных пакетов. Если подстека нет вообще (std::vector это empty) или, если последний существующий std::stack заполнен (size больше, чем наш внутренний определенный maxStackSize), мы добавляем полностью новый std::stack на наш std::vector. После этого, независимо от того, добавили ли мы новый std::stack раньше или нет, мы просто push запрошенное значение на последнем std::stack в нашем std::vector.

Остальные 2 функции - это pop функций. Есть общая функция pop и popAt, которая должна извлекаться из определенного подстека c. Если мы подумаем об этом, то сможем обнаружить, что общая функция является частным случаем функции popAt с индексом последнего стека. Затем мы просто вызовем popAt(stacks.size() - 1).

Хорошо, затем сконцентрируемся на функции popAt.

Сначала мы выполняем граничный стек. Это приведет к появлению сообщения об ошибке, если индекс отрицательный (может произойти при вызове pop для пустого std:vector или, если индекс больше, чем количество существующих std::stack s.

Затем мы проверяем, содержит ли требуемый подстек данные или пуст. Если он пуст, мы удалим его из std::vector и уменьшим индекс.

Независимо от предыдущего действия, мы снова проверяем, если данные доступны. Сейчас индекс может быть отрицательным, потому что мы, возможно, удалили std::stack. Но также std::vector может быть сейчас пустым. Или также адрес stack, может быть, empty. Во всех этих случаях мы отображаем сообщение об ошибке.

В противном случае мы возвращаем значение из std::stack с текущим индексом.

В main Я добавил тестовый код драйвера.

#include <iostream>
#include <vector>
#include <stack>

using MyType = int;
constexpr size_t DefaultMaxStackSize = 3;

class SetOfStacks {
    // The class data
    // The maximum size of one stack
    size_t maxStackSize{ DefaultMaxStackSize };

    // And a vector of stacks
    std::vector<std::stack<MyType>> stacks{};

public:

    // Constructor
    SetOfStacks() {}

    // 2nd Constructor for setting the stack size.
    explicit SetOfStacks(const size_t mss) : maxStackSize(mss) {};

    // ----------------------------------------------------------------------
    // Simple push function
    void push(MyType mt) {

        // If there are no stacks at all, or the last stack is full
        if (stacks.empty() || stacks.back().size() >= maxStackSize) {

            // At a new stack
            stacks.emplace_back(std::stack<MyType>{});
        }

        // Add a value to the last stack
        stacks.back().push(mt);
    }

    // ----------------------------------------------------------------------
    // Pop functions
    // STandard pop will call popAt with the index being the last avaliable stack
    MyType pop() { return popAt(stacks.size() - 1); }

    // Main working functions with error checking
    MyType popAt(int index) {

        // Here we will retrun the result
        MyType result{};

        // Sanity check. Is the index in the correct range
        if (index >= stacks.size()) {

            // Index is out of bounds. Inform user
            std::cerr << "\n*** Error:Wrong index. No data\n";
        }
        else {
            // So, now, index is in bounds. Check, if the stack at the specified index is empty
            if (stacks[index].empty()) {
                
                // Stack at specified index was empty. Remove it and decrement index
                stacks.pop_back();
                --index;
            }
            // Sanity check. There must be data available
            if (stacks.empty() || index < 0 || stacks[index].empty()) {
                // If not, inform the user
                std::cerr << "\n*** Error: Not data available\n";
            }
            else {
                // Return value from stack
                result = stacks[index].top();
                stacks[index].pop();
            }
            return result;
        }
    }
};

int main() {
    // Create a Ste of stacks
    SetOfStacks sos;

    // Populate it
    for (int i = 1; i < 12; ++i)
        sos.push(i);

    // Get all values from stack
    for (int i = 1; i < 12; ++i)
        std::cout << sos.pop() << '\n';

    // Get an additional value. Will of course not work
    std::cout << '\n' << sos.pop() << "\n\n";

    // Populate stack again
    for (int i = 1; i < 12; ++i)
        sos.push(i);

    // Get data from a specified stack
    std::cout << '\n' << sos.popAt(1) << "\n\n";

    // Get all values from stack. Will result in error for last 
    // element, becuase we already removed 1 element
    for (int i = 1; i < 12; ++i)
        std::cout << sos.pop() << '\n';
    return 0;
}