Write a program in C++ that uses three stacks to sort a usergiven number of random integers using a selection sort.
stack.h contains our stack implementation whichyou will modify as follows:
- The elements on the stack will be int typeinstead of char type. Make all necessary changesfor this to work properly.
- Add a function print:
void print ();
print prints the elements of the stack on oneline with a space between each pair of values. It should not printany labeling text. The stack is printed from the top element to thebottom. If the stack is empty, it should print the wordEmpty.
The application should use three stacks, let’s call themordered, temp1 andtemp2. A high level description of the sortingalgorithm is:
Ask the user for the number of values to sort
Place that many random integers in the range [1..100] on
the stack temp1
print the three stacks with labels
while (temp1 and temp2 areboth not empty)
{
if (temp2 is empty)
{
move all elements from temp1 totemp2 except the
largest one
put largest value on ordered
}
else
{
move all elements from temp2 totemp1 except the
largest one
put largest value on ordered
}
print the three stacks with labels
At this point, all elements should be sorted onordered
The random numbers should change each run.
stack.h
// implementation file for the stack class
#include <iostream>
#include <cstdlib>
using namespace std;
const int stack_size = 1000;
class stack
{
private:
char data [stack_size]; // data for the stack
int top; // index of the top of the stack
public:
stack (); // creates an empty stack
void push (char item); // puts item on the top of the stack
char pop (); // removes and returns the top of the stack
bool full (); // returns true if the stack is full
bool empty (); // returns true if the stack is empty
};
// constructor creates an empty stack
stack::stack ()
{
top = -1;
}
// push adds a new elment, item, to the top of the stack
void stack::push (char item)
{
// if the stack is full, print an error message
if (full ())
{
cout << “nnStack Error: Pushing on a full stack”;
cout << “nThe element being pushed was: ” <<item;
}
else // OK to push an element
{
top++;
data [top] = item;
}
}
// pop removes and returns the top element of the stack
char stack::pop ()
{
// if the stack is empty, print an error message
if (empty ())
{
cout << “nnStack Error: Popping an empty stack”;
cout << “nReturning ?”;
return ‘?’;
}
else // OK to pop
{
top–;
return data [top + 1];
}
}
// empty returns true if the stack is empty, else it returnsfalse
bool stack::empty ()
{
return top == -1;
}
// full returns true if the stack is full, else it returnstrue
bool stack::full ()
{
return top == stack_size – 1;
}
order.cpp
#include <cstdlib>
#include <iostream>
#include “stack.h”
using namespace std;
int main()
{
cout << “nn”;
return 0;
}
Here is a sample run of the program (user input inbold):
Enter the number of elements in the stack:8
Stacks at the start:
Ordered: Empty
Temp1: 73 30 65 77 9 84 100 22
Temp2: Empty
Ordered: 100
Temp1: Empty
Temp2: 22 84 77 9 73 65 30
Ordered: 84 100
Temp1: 30 65 73 9 77 22
Temp2: Empty
Ordered: 77 84 100
Temp1: Empty
Temp2: 22 73 9 65 30
Ordered: 73 77 84 100
Temp1: 30 65 9 22
Temp2: Empty
Ordered: 65 73 77 84 100
Temp1: Empty
Temp2: 22 9 30
Ordered: 30 65 73 77 84 100
Temp1: 22 9
Temp2: Empty
Ordered: 22 30 65 73 77 84 100
Temp1: Empty
Temp2: 9
Ordered: 9 22 30 65 73 77 84 100
Temp1: Empty
Temp2: Empty
Expert Answer
Answer to Write a program in C++ that uses three stacks to sort a user given number of random integers using a selection sort. sta…