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

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