Sorting a Stack using push,pop,isEmpty and peek

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/sorting-a-stack-using-push-pop-isempty-and-peek/.

Problem Definition: Sort a Stack using standard operations  push,pop,isEmpty and peek.

This question is asked in cracking the coding interview. 

Other ways of asking the question
Write a program to sort a stack in ascending order You should not make any assumptions about how the stack is implemented The following are the only functions that
should be used to write this program: push | pop | peek | isEmpty 

Note - peek is equivalent to top() function in java, where you dont pop out the element but peek and see.

Solutions

1. Use an additional array of size n, insert into array (Time Complexity O(n)). Use Counting Sort (Complexity O(n)). Memory overhead of O(m+n). OR O(n log n) if stack doesnt contains integer.
2. Using the extra stack with time complexity of O(n^2)
3. Use recursion with no additional space. The time complexity is O(n) and O(1) space complexity. 
4. Using quicksort in O(n logn)

 Method 1 - using the array and sort

1.  Pop out all the elements from the stack and put in array- O(n)
2. Sort the array - O(n) in case of counting sort for integer OR O(n log n) in case of other element. 
3. Push the elements in stack again (O (n)

Method 2 - Using extra stack

Here we are using 1 aux stack. Then we pop items from the original stack and push into the auxiliary stack into the correct position.

Code :  (credits)

public static Stack<Integer> sort(Stack<Integer> stack) {
 Stack<Integer> auxiliary = new Stack<Integer>();
 while (!stack.isEmpty()) {
  Integer value = stack.pop();
  while (!auxiliary.isEmpty() && value < auxiliary.peek())
   stack.push(auxiliary.pop());
  auxiliary.push(value);
 }
 return auxiliary;
}

Time complexity : O(n²) , Space complexity - O(n)

Example:
Suppose, elements are pushed in the following order: 7 3 5 8 9 1 2

original_stack      :      2   1   9    8     5      3    7                                
                           |
                          top                    

Popping out 2

 original_stack      :     1   9    8     5      3    7                                
                           |
                          top

 aux_stack           :          2
                                |
                               top

Pop out 1 from original stack, and put it in right position. First we compare if elements in original stack is less than element at top of aux stack. If so we push the data in original stack from aux stack, and push the current top of original stack in aux stack.

value = original stack.pop = 1
 original_stack      :          9    8     5      3    7                                
                                |
                               top

 aux_stack           :          2
                                |
                               top
value < auxStack.top() i.e.1 <, 2 => , push value in aux stack.

 original_stack      :          2    9    8     5      3    7                                
                                |
                               top

 aux_stack           :          1
                                |
                               top

And so on. Now we will insert 1,2,9,...and again 8 pops up, which pushes out 9 and inserts itself in aux stack. Finally we will get the proper stack. Here is the code on github in java, regarding the same.


Method 3 - Using recursion and internal stack
Here insert function does a trick, which inserts the element smaller than its top, below the top and larger element than the top at the top of the stack.

package com.vaani.ds.stack.application;
package com.vaani.ds.stack.application;

import java.util.Stack;

/**
 * Sorts a stack using operations push,pop,peek and isEmpty
 *
 */
public class StackSort {

 public static void sort(Stack<integer> s){

  int x=0;
  if (!s.isEmpty()){
   x=s.pop();
   sort(s);
   insert(s,x);
  }

 }

 //At each step check if stack.peek > x, and insert below top recursively
 public void insert(Stack<integer> s,int x){
//peek function returns the value of the top element without removing it
  if (!s.isEmpty() && s.peek()>= x){

   int y=s.pop();
   insert(s, x);
   s.push(y);

  }else {
   s.push(x);
  }

 }

 public static void main(String[] a){

  StackSort ss=new StackSort();

  //initiate the stack of integers
  Stack<Integer> stack=new Stack<Integer>();
  //push the elements
  stack.push(3);stack.push(4);stack.push(1);stack.push(2);

  //sort the stack
  ss.sort(stack);
  for(int val: stack){
   System.out.print(val+" ");
  }

 }

}

You can refer to the code in github here.

Time complexity - O(n)
Space complexity - O(1) [if we are not considering the stack used while recursion]

Understanding the logic

1.  Pop out the current element x
2. Again call the sort recursively
3. After popping out, insert it if current top is more than x

Method 4 - Mimic-ing quicksort (credit)
Can we do better? We can mimic the way of quicksort by picking a pivot from the stack (using pop) first. Then we conduct the partition operation by pushing all elements in the stack with values less than the pivot into one stack, while all elements with values greater than the pivot into the other. After that, we recursively sort two sub-stacks and merge two at last with the pivot in the middle.
Because we can only use the stack structure, I pick the pivot using pop. The merge operation is tricky and I am not sure if we can have a better way to combine two stacks. So if you have any idea, please let me know.
On average, this algorithm makes O(n log n) comparisons to sort n items. In the worst case, it makes O(n²) comparisons, though this behavior is rare.

public static Stack<Integer> sort(Stack<Integer> s) {
  if (s.isEmpty()) {
    return s;
  }
  int pivot = s.pop();
   
  // partition
  Stack<Integer> left  = new Stack<Integer>();
  Stack<Integer> right = new Stack<Integer>();
  while(!s.isEmpty()) {
    int y = s.pop();
    if (y < pivot) {
      left.push(y);
    } else {
      right.push(y);
    }
  }
  sort(left);
  sort(right);
    
  // merge
  Stack<Integer> tmp = new Stack<Integer>();
  while(!right.isEmpty()) {
    tmp.push(right.pop());
  }
  tmp.push(pivot);
  while(!left.isEmpty()) {
    tmp.push(left.pop());
  }
  while(!tmp.isEmpty()) {
    s.push(tmp.pop());
  }
  return s;
}

Thanks