#### Stacks & Queues

Problem
Implement an inplace algorithm to sort a stack.

Solution
We will use the system stack to implement the solution i.e the basic funda of recursion.
Suppose there are ‘n’ elements in the stack.
Repeat the following steps ‘n’ times.
1) Move all elements from given stack to system stack using recursion.
2) Then compare & swap the top elements in given stack and the system stack ( similar to bubble sort ) while moving all elements from system stack to the given stack.
See the implementation below.

```#include<iostream>
#include<stack>
using namespace std;

// display the stack contents
void displayStack(stack<int> s) {
cout<<"\nDisplaying the stack :-\n";
while (!s.empty()) {
cout<<s.top()<<" ";
s.pop();
}
}

void compareAndSwap(stack<int> &s) {
if (s.size() == 1) {
// boundary case
// single element stack is already sorted
return;
}
// store all the elements in the system stack
int x = s.top();
s.pop();
compareAndSwap(s);
// compare and swap (if required) the top elements
// in actual stack and the system stack
if (s.top() < x) {
int y = s.top();
s.pop();
s.push(x);
s.push(y);
}
else {
s.push(x);
}
}

// sort the stack inplace
void sortStack(stack<int> &s) {
int i;
for (i=0;i<s.size();i++) {
compareAndSwap(s);
}
}

// main
int main() {
stack<int> s;
s.push(7);
s.push(19);
s.push(11);
s.push(3);
s.push(9);
displayStack(s);
sortStack(s);
cout<<"\n\nAfter Sorting :-";
displayStack(s);
cout<<endl;
return 0;
}```