The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist who works with traditional aesthetic and literary forms as
well as mathematical concepts, to communicate the way that an algorithm works and to convince a reader that the results will be correct. Donald E. Knuth

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

Back | Next

All problems on Stacks and Queues
* Implement a stack using an array
* Implement a queue using an array
* Implement a circular queue using an array
* Design and implement an extended stack using linked list which permits push, pop & maxElement (gets maximum element in the stack) in O(1) time complexity
* Implement a circular queue using linked list
* Implement a Queue data structure using two stacks
* Sort a Queue using two stacks
* Convert infix expression to the postfix notation
* Implement an algorithm to evaluate a postfix expression
* Given a stack with only 0s & 1s, find the majority element in the stack
* Implement an inplace algorithm to sort a stack