#### Stacks & Queues

Problem
Sort a Queue using two stacks.

Solution
We implement the solution with STL stack & queue.
Consider two stacks S1 & S2 which will be used to sort queue Q.
Move all the elements from Q onto S1 i.e dequeue all the elements from Q and push them into S1.
1) Move all elements from S1 into S2 except the minimum element which is enqueued into Q.
2) Now move all elements from S2 into S1 except the minimum element which is enqueued into Q.
3) Repeat steps (1) & (2) till both the stacks are empty.

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

// display the queue
void displayQueue(queue<int> q) {
cout<<"\nDisplaying Queue :-\n";
while (!q.empty()) {
cout<<q.front()<<" ";
q.pop();
}
}

// move all the elements except the minimum element
// from 'src' stack to 'dest' stack
// returns the minimum element
int moveElements(stack<int> &src, stack<int> &dest) {
int min;
if (!src.empty()) {
min = src.top();
src.pop();
}
while (!src.empty()) {
if (min > src.top()) {
// found a element smaller than
// the current min
// push the current min and
// update the minimum element
dest.push(min);
min = src.top();
}
else {
dest.push(src.top());
}
src.pop();
}
return min;
}

// sort the queue using 2 stacks
void sortQueue(queue<int> &q) {
stack<int> s1, s2;
int min;
bool flag = true;
// push all the elements of the queue into s1
while (!q.empty()) {
s1.push(q.front());
q.pop();
}

/* repeat the below steps until both the stacks
are empty.
we will keep moving the elements from s1 to s2
and vice-versa alternately and keep track of the minimum
element while moving the elements and insert
the min element in the queue.
we don't push the minimum element in each iteration
(meaning element movement) in any of the stacks.
Algorithm is based on selection sort technique
*/
while (!s1.empty() || !s2.empty()) {
// flag = true denotes we are moving elements
// from s1 to s2
if (flag == true) {
min = moveElements(s1,s2);
// push the min element in the queue
q.push(min);
flag = false;
}
// flag = false denotes we are moving elements
// from s2 to s1
else {
min = moveElements(s2,s1);
// push the minimum element into queue
q.push(min);
flag = true;
}
}
}

// main
int main() {
queue<int> q;
q.push(17);
q.push(9);
q.push(11);
q.push(19);
q.push(7);
q.push(2);
displayQueue(q);
sortQueue(q);
cout<<"\nAfter Sorting :-";
displayQueue(q);
cout<<endl;
return 0;
}```