如何在 C++ 中按字母顺序对堆栈进行排序？

Question

我是 C++ 的新手，我不太了解堆栈。我尝试按照一些教程使用递归对 Stack1 进行排序，但没有任何效果，或者它只专注于包含整数的数组。我也尝试直接对 Names 数组进行排序，但它不起作用。我如何以一种不复杂的方式为我的 Stack1 排序我的 Names 数组（因为我是新手并且不太了解它）？

这是我的代码：

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

如评论中所述，作业要求我对堆栈进行排序。这是作业文本以供更多理解：

Answer 1

要有效地对堆栈进行排序，需要查看堆栈中的随机位置，最好是将堆栈底部与堆栈中最大的元素交换。

但这已经违背了堆栈的概念，因此我们需要更多的东西，比如多2或3个堆栈。

可以从一个未排序栈和两个空栈开始，一次从未排序栈中取出一个元素，比较该元素是小于还是大于临时栈A的栈顶元素。如果比较大，就放在A栈，否则就放在B栈。最后最大的元素在A栈顶，原来的随机元素栈为空。我们现在可以将栈顶元素从栈A移动到原栈顶，原栈开始按降序收集所有元素。

然后将A栈和B栈中的所有元素移到原栈中，除最后一个元素外，已排序。

如果不允许我们知道堆栈的大小（即迭代计数的次数），那么我们需要四个堆栈：未排序、到目前为止最大、到目前为止不是最大和已排序。

这个算法会模拟冒泡排序，但是，因为我们知道临时堆栈 A 是部分排序的，我们可能会利用这个事实来实现，例如合并排序。

Answer 2

首先，使用堆栈进行重新排序是非常不切实际的，但这可能是您在 school/college 获得的作业之一，可以提高您解决问题的能力。

无论如何，如果您被迫使用堆栈，您应该首先创建 1-2 个临时堆栈，这是您的代码中缺少的。

我可以给你降序的基本逻辑，你可以进一步将其用于其他情况。

要遵循的步骤：

首先，您创建 2 个临时堆栈和一个主堆栈。所以我们的临时堆栈将被称为“tempStack1”和“tempStack2”，而我们的主堆栈将被称为“mainStack".
将所有初始输入推送到 mainStack。现在弹出并移动 mainStack 的顶部元素到 tempStack1.
现在检查 Stack 的顶部元素是否大于 tempStack1 的顶部元素。如果它更大，则从 Stack 中弹出该元素并将其推入 tempStack1。如果较小，则将顶部元素从 mainStack 推到 tempStack2.
如果 tempStack2 中存在元素，我们会将其与 tempStack1 的最高值进行比较。如果 tempStack2 的最高值小于 tempStack1 的最高值，那么我们简单地推入 tempStack1[= 的最高值51=] 到 mainStack。但是，如果 tempStack2 的最高值大于 tempStack1 的最高值，或者如果 tempStack1空，我们将把 tempStack2 的最高值推入 tempStack1.

我们不断重复这些步骤，最终我们将在 tempStack1 中以升序排列堆栈。现在我们所做的就是将 tempStack1 中的每个元素弹出并压入 mainStack 中，这样它将反转它，我们将获得降序。

您可以将类似的逻辑应用于您的其他案例。

Answer 3

如果堆栈的底层容器将其数据存储在连续内存中，这对于 std::vector 或 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 = &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>& 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>& 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>& 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;    
}

如何在 C++ 中按字母顺序对堆栈进行排序？

How Do I Sort A Stack Alphabetically in C++?

c++

arrays

sorting

stack