How Do I Sort A Stack Alphabetically in C ?-CodePudding

I'm new to C , and I do not understand stacks that well. I tried following some tutorials to sort Stack1 using recursion, but nothing has been working or it is solely focused on arrays containing integers. I also tried sorting the Names array directly, but it does not work. How do I go about sorting my Names array for my Stack1 so in a non-complex manner (since I am new and do not understand it that well)?

Here's my code:

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

As mentioned in the comments, it is required by an assignment that I sort my stacks. Here is the assignment text for more understanding:

CodePudding user response：

If the underlying container for the stack has its data stored in consecutive memory, which is true for a std::vector or a std::deque, the sorting is ultra simple.

You can simply sort the underlying container. That is really easy.

The std::deque is the default underlying container. So, this approach will work in most cases.

Please see the below small example:

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

My guess is that you wanted some recursive solution, because you mentioned something like that.

With a sortable or already sorted helper container, also a recursive solution is possible.

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

But, as per my final guess, what the instructor really wants is that you just use stacks, without any helper container.

This can also be achieved by using one temporary stack. Please see:

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

CodePudding user response：

To efficiently sort a stack, one would need to peek at random positions on the stack, preferably swapping the bottom of the stack with the largest element in the stack.

But this already violates the idea of the stack, thus we need something more, such as 2 or 3 more stacks.

One can start with one unsorted stack and two empty stacks, removing one item from the unsorted stack at a time and comparing if the element is smaller or larger than the top element of temporary stack A. If it's larger, place it on stack A, otherwise place it on stack B. In the end the largest element is at the top of stack A, and the original stack of random elements is empty. We can now move the top element from stack A to the top of the original stack, which starts to collect all the elements in descending order.

Then move all the elements from stacks A and B to the original stack and follow the previous step, except for last element, which is sorted.

If we are not allowed to know the size of the stacks (i.e. the number of iteration counts), then we need four stacks: unsorted, max so far, not max so far and sorted.

This algorithm would simulate bubble sort, however, since we know that the temporary stack A is partially sorted, we could probably utilise this fact to implement e.g. merge sort.

CodePudding user response：

First off, it is very unpractical to use stacks for reordering, but its probably one of those assignments you get at school/college that enhances your problem solving skills.

Anyways if you are forced to use a stack, you should first of all create 1-2 temporary stacks, which is missing in your code.

I can give you the basic logic for the descending ordering, which you can further use for your other cases.

Steps to follow:

Firstly you create 2 temporary stacks and a main stack. So our temporary stacks will be called "tempStack1" and "tempStack2", while our main stack will be called "mainStack".
Push all your initial input into mainStack. Now pop and move the top element of mainStack to tempStack1.
Now check if the top element of Stack is greater than the top element of tempStack1. If it is greater, then pop the element from Stack and push it to tempStack1. If it is lesser, then push the top element from mainStack to tempStack2.
If there is an element present in tempStack2, we will compare it to the top value of tempStack1. If the top value in tempStack2 is lesser than top value of tempStack1, then we simply push the top value of tempStack1 to mainStack. However, if the top value of tempStack2 is greater than the top value of tempStack1 OR if tempStack1 is empty, we will push the top value of tempStack2 into tempStack1.
We keep repeating the steps and eventually we'll have the stack in an ascending order in tempStack1. Now all we do is pop and push every element in tempStack1 in mainStack, this way it will reverse it and we'll have the descending order.

You can apply a similar logic to your other cases.