Блог

Я новичок в C и не очень хорошо разбираюсь в стеках. Я попытался следовать некоторым учебным пособиям по сортировке Stack1 с использованием рекурсии, но ничего не работало или было сосредоточено исключительно на массивах, содержащих целые числа. Я также попытался отсортировать Names массив напрямую, но это не работает. Как мне выполнить сортировку Names массива для моего Stack1 so несложным способом (поскольку я новичок и не очень хорошо его понимаю)?

Вот мой код:

 //Necessary libraries
#include <iomanip>
#include <iostream>
#include <stack>
#include <algorithm>
using namespace std;

//Main CPP Function
int main() {
    //Name and Surname 
    std::string Names[] = { "Sam", "John", "Simon", "Sarah", "Mat", "Nick", "Isaac", "Anna", "Daniel", "Aaron", "Jack", "Kathrine " };std::sort(std::begin(Names), std::end(Names));
    std::string Surnames[] = { "Williams", "Phoenix", "Johnson", "Khosa", "Jackon", "Roberts", "Wayne", "Mishima", "Rose", "Black", "Mohamed", "Bruckner" };
    //Score Array
    int Score[] = { 60, 85, 75, 81, 38, 26, 74, 34, 64, 83, 27, 42 };
    //Variable decleration needed for if statements
    int l;
    int k;
    //Calculates array size
    l = sizeof(Names) / sizeof(Names[0]);
    k = sizeof(Surnames) / sizeof(Surnames[0]);

    //------------------------------- Stack One --------------------------------------//
    //var declaration
    stack <string> Stack1;
    stack <int> Score1;     
    cout << "Stack One" << endl;
    //sort stack one alphabetically by name

    //whilst our Names array is not empty, we will push it into the stack
    for (int i = 0; i < l; i  )  {
        //pushes Names, Surnames and Scores to first stack
        Stack1.push(Names[i]);
        Stack1.push(Surnames[i]);
        Score1.push(Score[i]);   
            //prints Names, Surnames and Scores for the first stack
            while (!Stack1.empty()){
                cout << "t" << setw(20) << Stack1.top() << "t" << Score1.top() << endl;
                //stops the printing from printing in an endless loop
                Stack1.pop();
                Score1.pop();
        }
    }
return 0;
}
 

Как упоминалось в комментариях, по заданию требуется, чтобы я сортировал свои стопки. Вот текст задания для более глубокого понимания:

Если в базовом контейнере для стека данные хранятся в последовательной памяти, что верно для a std::vector или a std::deque , сортировка очень проста.

Вы можете просто отсортировать базовый контейнер. Это действительно просто.

std::deque Это базовый контейнер по умолчанию. Таким образом, этот подход будет работать в большинстве случаев.

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

 #include <iostream>
#include <stack>
#include <deque>
#include <algorithm>
#include <functional>

int main() {
    
    // Define a stack and initialize it with some values
    std::stack<int> myStack(std::deque<int>{2,1,4,3,10,20,32,25});

    // Get iterator to begin end end of tsakcs underlying container
    int* endOfStack = amp;myStack.top()   1;
    int* beginOfStack = endOfStack - myStack.size(); 
    
    // Sort it
    std::sort(beginOfStack, endOfStack, std::greater<int>());
    
    // Output stack content
    for (; not myStack.empty(); myStack.pop()) std::cout << myStack.top() << 'n';

    return 0;    
}
 

Я предполагаю, что вам нужно какое-то рекурсивное решение, потому что вы упомянули что-то подобное.

С помощью сортируемого или уже отсортированного вспомогательного контейнера возможно также рекурсивное решение.

 #include <iostream>
#include <stack>
#include <deque>
#include <algorithm>
#include <functional>
#include <set>

// Recursive sort function using a helper container
void sortStackRecursive(std::stack<int>amp; myStack, std::multiset<int> data) {

    // Check for end of recursion
    if (myStack.empty()) {
        
        // All elements have been popped of the stacked, sorted and put in the multiset
        // Now push them on the stack again in sorted order 
        for (const int value : data) myStack.push(value);
        return;
    }
    else {
        // Add top of stack element into multiset
        data.insert(myStack.top());
        myStack.pop();
        // Self call
        sortStackRecursive(myStack,data);
    }
}

void sortStack(std::stack<int>amp; myStack) {
    std::multiset<int> data{};
    sortStackRecursive(myStack,data);
}

int main() {
    
    // Define a stack and initialize it with some values
    std::stack<int> myStack(std::deque<int>{2,1,4,3,10,20,32,25});

    // Sort it
    sortStack(myStack);
    
    // Output stack content
    for (; not myStack.empty(); myStack.pop()) std::cout << myStack.top() << 'n';

    return 0;    
}
 

Но, согласно моему окончательному предположению, инструктор действительно хочет, чтобы вы просто использовали стеки без какого-либо вспомогательного контейнера.

Это также может быть достигнуто с помощью одного временного стека. Пожалуйста, посмотрите:

 #include <iostream>
#include <stack>
#include <deque>
#include <algorithm>


// Sort a stack, with the help of one temporary stack
void sortStack(std::stack<int>amp; myStack) {
    
    // Define a temporary stack
    std::stack<int> tempStack;
    
    // As long as there are values on the original stack
    while (not myStack.empty()) {
        
        // Get the top of the stack value and remember it
        int value = myStack.top();
        myStack.pop();
        
        // And now. As long as there are values on our temporary stack
        // and the top value of the temporary stack is smaller than the value 
        // on the original stack
        while(not tempStack.empty() and tempStack.top() < value) {
            
            // Then exchange the current top elements
            myStack.push(tempStack.top());
            tempStack.pop();
        }
        // And put the original greater value back on the top of the stack
        tempStack.push(value);
    }
    // If there are still bigger values on the temporary stack
    while (not tempStack.empty()) {
        
        // the push them back on the original stack
        myStack.push(tempStack.top());
        tempStack.pop();
    }
}

int main() {
    
    // Define a stack and initialize it with some values
    std::stack<int> myStack(std::deque<int>{2,1,4,3,10,20,32,25});

    // Sort it
    sortStack(myStack);
    
    // Output stack content
    for (; not myStack.empty(); myStack.pop()) std::cout << myStack.top() << 'n';

    return 0;    
}

 

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

Но это уже нарушает идею стека, поэтому нам нужно что-то большее, например, еще 2 или 3 стека.

Можно начать с одного несортированного стека и двух пустых стеков, удаляя по одному элементу из несортированного стека за раз и сравнивая, меньше или больше элемент, чем верхний элемент временного стека A. Если он больше, поместите его в стопку A, в противном случае поместите его в стопку B. В конце концов, самый большой элемент находится в верхней части стека A, а исходный стек случайных элементов пуст. Теперь мы можем переместить верхний элемент из стека А в верхнюю часть исходного стека, который начинает собирать все элементы в порядке убывания.

Затем переместите все элементы из стеков A и B в исходный стек и выполните предыдущий шаг, за исключением последнего элемента, который сортируется.

Если нам не разрешено знать размер стеков (т. Е. количество итераций), то нам нужно четыре стека: несортированные, пока не максимальные, пока не максимальные и отсортированные.

Этот алгоритм будет имитировать сортировку пузырьков, однако, поскольку мы знаем, что временный стек A частично отсортирован, мы, вероятно, могли бы использовать этот факт для реализации, например, сортировки слиянием.

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

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

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

Шаги, которые необходимо выполнить:

1. Сначала вы создаете 2 временных стека и основной стек. Таким образом, наши временные стеки будут называться «tempStack1» и «tempStack2«, в то время как наш основной стек будет называться «Основной стек«.
2. Перенесите все свои первоначальные данные в mainStack. Теперь откройте и переместите верхний элемент mainStack в tempStack1.
3. Теперь проверьте, больше ли верхний элемент стека, чем верхний элемент tempStack1. Если он больше, то извлеките элемент из стека и переместите его в tempStack1. Если он меньше, то переместите верхний элемент из mainStack в tempStack2.
4. Если в tempStack2 присутствует элемент, мы сравним его с верхним значением tempStack1. Если верхнее значение в tempStack2 меньше, чем верхнее значение tempStack1, то мы просто переносим верхнее значение tempStack1 в mainStack. Однако, если верхнее значение tempStack2 больше верхнего значения tempStack1 ИЛИ если tempStack1 пуст, мы переместим верхнее значение tempStack2 в tempStack1.
5. Мы продолжаем повторять шаги, и в конечном итоге у нас будет стек в порядке возрастания в tempStack1. Теперь все, что мы делаем, это открываем и нажимаем каждый элемент в tempStack1 в mainStack, таким образом, он изменит его, и у нас будет порядок убывания.

Вы можете применить аналогичную логику к другим своим случаям.