Sorting a stack

[amr200]

im trying to sort a stack that has been input by the user. I'm still not very familiar with the sort topic so i don't know what do to at this point. I slowly started with stacks then started to include to void function for sort. the only errors so far are in the void function bubblesortstck everything else works fine on its own. from what ive searched so far is that i need to make another stack that is empty and that's how the sort process occurs. Im using the bubble sort method that's included in my module.

ps. im aware that the system() isn't really ideal but this is just a program for school and i want to learn more about how sorts work from my code:)

#include<iostream>
#include<stack>
#include<cstdlib>
using namespace std;
// STACK CONTENTS
class STACKS
{
const int Size {10};
int stck [10];
int tops =-1;
public:

bool full(){
    if ((tops++ )== Size)
        return true;
    else
        return false;
}
bool emptyS(){
    return tops ==-1;
}
void pushS(){
    int stcke;
    if (full())
        cout<<"\nStack overflow!\n";
    else {
        if (tops ==-1)
            tops = 0;
        cout<<"\nEnter an element : ";
        cin>>stcke;
        cout<<"\n";
        tops = tops +1;
        stck[tops]= stcke;
    }
}
void popS(){
    if(emptyS())
   cout<<"\nStack Underflow\n"<<endl;
   else {
      cout<<"\nThe popped element is "<< stck[tops] <<endl;
      tops--;
   }
}
void displays() {
   if(tops>=0) {
      cout<<"\nStack elements are:";
      for(int i=tops; i>=0; i--)
      cout<<stck[i]<<" ";
      cout<<endl;
   } else
   cout<<"\nStack is empty";
}
void topS(){
    cout<<"\nThe top element is : "<<stck[tops]<<"\n";
}

void bubblesortstck(){
    stack<int> s;
    int n =
    for (int i = 0 ; i < Size; i++ ){
        s.push(stck[tops]);
    }

    stack<int> ss;
    for (int i = 0; i< Size; i++){
        if (i%2 == 0){
            while (!s.empty()){
                int t = s.top();
                s.pop();

                if (ss.empty()){
                    ss.push(t);
                }

                else {
                    //swapping
                    if (ss.top() > t){
                        int temp = ss.top();
                        ss.pop();
                        ss.push(t);
                        ss.pop(temp);
                    }
                    else {
                        ss.push(t);
                    }
                }
            }

            stck[Size - 1 - i] = ss.top();
            ss.pop();
        }
        else {
            while(!ss.empty()){
                int t = ss.top();
                ss.pop();

                if (s.empty()){
                    s.push(t);
                }
                else {
                    if (s.top() > t){
                        int temp = s.top();
                        s.pop();

                        s.push(t);
                        s.push(temp);
                    }
                }
            }

            s[Size - 1 - i] = s.top();
            s.pop();
        }
    }
    cout<< "[";
    for (int i = 0 ; i< Size ; i ++){
        cout<<stck[i]<<" , ";
    }
    cout<<"]";
}
};


int main()
{
    menu_screen:
        cout<<"Menu\n";
        //will add contents later
        goto stack_screen;

  stack_screen:
            system("pause");
            system("cls");
            STACKS st;
        cout<<" 1. add\n";
        cout<<" 2. delete\n";
        cout<<" 3. sort\n";
        cout<<" 4. top\n";
        cout<<" 5. display\n";
        cout<<" 6. search\n";
        cout<<" 7. exit\n";
        int ans_s;
        do {
            cout<<"\nEnter your choice : ";
            cin>>ans_s;
        switch (ans_s){
        case 1: st.pushS(); break;
        case 2: st.popS(); break;
        case 3: st.bubblesortstck(); break;
        case 4: st.topS(); break;
        case 5: st.displays(); break;
        //case 6:
        case 7: goto menu_screen; break;
        default : cout<<"you have entered the wrong number please pick again\n\n";
        system("pause");
        system("cls");
        goto stack_screen;
        break;
        }
        }while(ans_s !=8);
return 0;
}

the errors are :

in member function 'void STACKS::bubblesortstck()':
line 58 invalid conversion from 'int' to 'int' [-fpremissive]
line 80 no matching function for call to 'std::stack<int>::pop(int&)'
line 110 no match for 'operator[]' (operand types are 'std::stack<int>' and 'int')

[coder777]

Line 59: What is this supposed to be? I suggest to remove it.
Line 81: You probably mean push() not pop().
line 111: you cannot use a stack like a vector. If you want so just use a vector.

[amr200]

line 59 was supposed to be a variable connected to the size of the stack, i wasn't sure if it is needed so i kept it as is. Forgot to make it as a comment instead, my bad. also will search on how to use vectors thanks!

[coder777]

For vector see this:

http://www.cplusplus.com/reference/vector/vector/?kw=vector

It's similar to stack, but you need to use push_back()/pop_back() and back() instead of push()/pop() and top().

[seeplus]

Please don't use goto statements. It's very bad coding practice and aren't needed. Use an appropriate loop construct. Forget that you know about them!

full() shouldn't change member variables as it's only a condition function. There's no need to set tops to 0 if it's -1 as adding 0 to -1 gives 0 for the first insertion position.

The concept of a stack is last-in, first-out (LIFO) - ie the ordering of the stack is determined by the order of insertion - not by any other criteria. Therefore it's not appropriate to sort a stack, or search it, or access any element other than the top element if present.

Without the sort, consider:

#include <iostream>
using namespace std;

// STACK CONTENTS
class STACKS
{
	static const int Size {10};
	int stck[Size] {};
	int tops {-1};

public:
	bool full() const { return tops == Size - 1; }
	bool emptyS() const { return tops == -1; }

	void pushS() {
		if (full())
			cout << "\nStack overflow!\n";
		else {
			int stcke {};

			cout << "\nEnter an element : ";
			cin >> stcke;
			cout << "\n";

			stck[++tops] = stcke;
		}
	}

	void popS() {
		if (emptyS())
			cout << "\nStack Underflow\n" << endl;
		else
			cout << "\nThe popped element is " << stck[tops--] << '\n';
	}

	void displays() const {
		if (!emptyS()) {
			cout << "\nStack elements are: ";
			for (int i = tops; i >= 0; --i)
				cout << stck[i] << " ";

			cout << '\n';
		} else
			cout << "\nStack is empty\n";
	}

	void topS() const {
		if (emptyS())
			cout << "\nStack Underflow\n" << endl;
		else
			cout << "\nThe top element is " << stck[tops] << '\n';
	}

};

int main() {
	STACKS st;
	int ans_s {};

	do {
		cout << "Menu\n";
		cout << " 1. add\n";
		cout << " 2. delete\n";
		cout << " 3. sort\n";
		cout << " 4. top\n";
		cout << " 5. display\n";
		cout << " 6. search\n";
		cout << " 7. exit\n";

		cout << "\nEnter your choice : ";
		cin >> ans_s;

		switch (ans_s) {
			case 1: st.pushS(); break;
			case 2: st.popS(); break;
			//case 3: st.bubblesortstck(); break;
			case 4: st.topS(); break;
			case 5: st.displays(); break;
			//case 6:
			case 7: break;

			default:
				cout << "you have entered the wrong number please pick again\n\n";
				break;
		}
	} while (ans_s != 7);
}

[amr200]

thanks for the advice will keep those in mind for future programs. but sadly, i have to sort it for my school project requirement haha so i have to make all stacks, search and sort work together somehow.

[seeplus]

Ok. For a simple sort of the stack, consider:

#include <iostream>
#include <utility>
using namespace std;

// STACK CONTENTS
class STACKS
{
	static const int Size {10};
	int stck[Size] {};
	int tops {-1};

public:
	bool full() const { return tops == Size - 1; }
	bool emptyS() const { return tops == -1; }

	void pushS() {
		if (full())
			cout << "\nStack overflow!\n";
		else {
			int stcke {};

			cout << "\nEnter an element : ";
			cin >> stcke;
			cout << "\n";

			stck[++tops] = stcke;
		}
	}

	void popS() {
		if (emptyS())
			cout << "\nStack Underflow\n" << endl;
		else
			cout << "\nThe popped element is " << stck[tops--] << '\n';
	}

	void displays() const {
		if (!emptyS()) {
			cout << "\nStack elements are: ";
			for (int i = tops; i >= 0; --i)
				cout << stck[i] << " ";

			cout << '\n';
		} else
			cout << "\nStack is empty\n";
	}

	void topS() const {
		if (emptyS())
			cout << "\nStack Underflow\n" << endl;
		else
			cout << "\nThe top element is " << stck[tops] << '\n';
	}

	void bubbleSort()
	{
		if (tops > 0) {
			auto n {tops + 1};

			do {
				int newn {1};

				for (int i = 1; i < n; ++i)
					if (stck[i - 1] > stck[i])
						std::swap(stck[i - 1], stck[newn = i]);

				n = newn;
			} while (n > 1);
		}
	}
};

int main() {
	STACKS st;
	int ans_s {};

	do {
		cout << "Menu\n";
		cout << " 1. add\n";
		cout << " 2. delete\n";
		cout << " 3. sort\n";
		cout << " 4. top\n";
		cout << " 5. display\n";
		cout << " 6. search\n";
		cout << " 7. exit\n";

		cout << "\nEnter your choice : ";
		cin >> ans_s;

		switch (ans_s) {
			case 1: st.pushS(); break;
			case 2: st.popS(); break;
			case 3: st.bubbleSort(); break;
			case 4: st.topS(); break;
			case 5: st.displays(); break;
			//case 6:
			case 7: break;

			default:
				cout << "you have entered the wrong number please pick again\n\n";
				break;
		}
	} while (ans_s != 7);
}

[dhayden]

You are mixing the stack functionality with the user interface. That's almost always a bad idea. For example, what if you wanted to push the numbers 1 through 10? You can't really, because the code only lets you add numbers that you prompt for. And what if you wanted to add the top two numbers on the stack? You can't do that either because the only thing you can do is display the top item or remove it.

Also, there's no need to end each method with "s" or "S". We know it's a stack, so there's no need to remind us in the method name.

Building on seeplus's version:

#include <iostream>
using namespace std;

// STACK CONTENTS
class STACKS
{
    static constexpr size_t Size {10};
    int stck[Size] {};
    int tos {-1};		// points to Top Of Stack

public:
    bool full() const { return tos == Size - 1; }
    bool empty() const { return tos == -1; }

    void push(int val) {
	if (full())
	    cout << "\nStack overflow!\n";
	else {
	    stck[++tos] = val;
	}
    }

    int pop() {
	if (empty()) {
	    cout << "\nStack Underflow\n" << endl;
	    return -1;
	} else {
	    return stck[tos--];
	}
    }

    void display() const {
	if (!empty()) {
	    cout << "\nStack elements are: ";
	    for (int i = tos; i >= 0; --i)
		cout << stck[i] << " ";

	    cout << '\n';
	} else
	    cout << "\nStack is empty\n";
    }

    int top() const {
	if (empty()) {
	    cout << "\nStack Underflow\n" << endl;
	    return -1;
	} else {
	    return stck[tos];
	}
    }

};

int main() {
    STACKS st;
    int ans_s {};

    do {
	cout << "Menu\n";
	cout << " 1. add\n";
	cout << " 2. delete\n";
	cout << " 3. sort\n";
	cout << " 4. top\n";
	cout << " 5. display\n";
	cout << " 6. search\n";
	cout << " 7. exit\n";

	cout << "\nEnter your choice : ";
	cin >> ans_s;

	switch (ans_s) {
	case 1:
	    {
		int stcke {};
		cout << "\nEnter an element : ";
		cin >> stcke;
		cout << "\n";
		st.push(stcke);
		break;
	    }
	case 2:
	    cout << "\nThe popped element is " << st.pop() << '\n';
	    break;
	    //case 3: st.bubblesortstck(); break;
	case 4:
	    cout << "\nThe top element is " << st.top() << '\n';
	    break;
	case 5:
	    st.display();
	    break;
	    //case 6:
	case 7: break;

	default:
	    cout << "you have entered the wrong number please pick again\n\n";
	    break;
	}
    } while (ans_s != 7);
}

[seeplus]

The issue, of course, with returning -1 for a stack underflow is that -1 could be a valid stack value. Without using std::optional or exceptions then perhaps the least possible int value?

Perhaps (based upon dhayden's code):

#include <iostream>
#include <limits>
#include <utility>
using namespace std;

// STACK CONTENTS
class STACKS
{
	static constexpr size_t Size {10};
	int stck[Size] {};
	int tos {-1};

public:
	static const int badpop {numeric_limits<int>::min()};

	bool full() const { return tos == Size - 1; }
	bool empty() const { return tos == -1; }

	bool push(int val) {
		if (full())
			return false;

		stck[++tos] = val;
		return true;
	}

	int pop() {
		return empty() ? badpop : stck[tos--];
	}

	void display() const {
		if (!empty()) {
			cout << "\nStack elements are: ";
			for (int i = tos; i >= 0; --i)
				cout << stck[i] << " ";

			cout << '\n';
		} else
			cout << "\nStack is empty\n";
	}

	int top() const {
		return empty() ? badpop : stck[tos];
	}

	void bubbleSort()
	{
		if (tos > 0) {
			auto n {tos + 1};

			do {
				int newn {1};

				for (int i = 1; i < n; ++i)
					if (stck[i - 1] > stck[i])
						std::swap(stck[i - 1], stck[newn = i]);

				n = newn;
			} while (n > 1);
		}
	}
};

int main() {
	STACKS st;
	int ans_s {};

	do {
		cout << "\nMenu\n";
		cout << " 1. add\n";
		cout << " 2. delete\n";
		cout << " 3. sort\n";
		cout << " 4. top\n";
		cout << " 5. display\n";
		cout << " 6. search\n";
		cout << " 7. exit\n";

		cout << "\nEnter your choice : ";
		cin >> ans_s;

		switch (ans_s) {
			case 1:
			{
				if (!st.full()) {
					int stcke {};

					cout << "\nEnter an element : ";
					cin >> stcke;
					cout << '\n';

					if (!st.push(stcke))
						cout << "Error - push\n";
				} else
					cout << "Stack is full\n";

				break;
			}

			case 2:
			{
				const auto p {st.pop()};

				if (p != STACKS::badpop)
					cout << "\nThe popped element is " << p << '\n';
				else
					cout << "Error - pop\n";

				break;
			}

			case 3:
				st.bubbleSort();
				break;

			case 4:
			{
				const auto p(st.top());

				if (p != STACKS::badpop)
					cout << "\nThe top element is " << p << '\n';
				else
					cout << "Error - top\n";

				break;
			}

			case 5:
				st.display();
				break;

			//case 6:

			case 7: break;

			default:
				cout << "you have entered the wrong number please pick again\n\n";
				break;
		}
	} while (ans_s != 7);
}

[JLBorges]

> from what ive searched so far is that i need to make another stack that is empty
> and that's how the sort process occurs.

Yes, you would need an auxiliary stack.

The algorithm for the bubble sort of a stack would be something like this:

#include <iostream>
#include <stack>
#include <functional>

template < typename T, typename C, typename CMP = std::less<> >
void bubble_sort( std::stack<T,C>& stk, CMP cmp = {} )
{
    std::stack<T,C> result ;

    while( !stk.empty() )
    {
        // extract the value at the top of stk
        T curr_val = std::move( stk.top() ) ;
        stk.pop() ;

        // bubble it to the right position at the top of the result
        // the sorted order depends on the binary predicate used for comparing elements
        while( !result.empty() && cmp( result.top(), curr_val ) )
        {
            stk.push( std::move( result.top() ) ) ;
            result.pop() ;
        }
       
        result.push( std::move(curr_val) ) ;
    }
    
    // now result contains the items in sorted order and original stack is empty. 
    // swap the two, to move the sorted items to the original stack   
    using std::swap ;
    swap( result, stk ) ;
}

template < typename T, typename C >
void print( std::stack<T,C> stk ) // destructive
{
    while( !stk.empty() )
    {
        std::cout << stk.top() << ' ' ;
        stk.pop() ;
    }
    std::cout << '\n' ;
}

int main()
{
    std::stack<int> stk ;
    for( int v : { 23, 11, 56, 42, 78, 18, 34, 86, 17 } ) stk.push(v) ;
    print(stk) ;

    bubble_sort(stk) ; // compare using <
    print(stk) ;

    bubble_sort( stk, std::greater<>{} ) ; // compare using >
    print(stk) ;
}

http://coliru.stacked-crooked.com/a/9cd84e3e82f9ff46