Problem

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

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 don’t pop out the element but peek and see.

Solutions

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.

Here’s a step-by-step approach to solve the problem:

  1. Pop an element from the input stack.
  2. While the auxiliary stack is not empty and the top element of the auxiliary stack is greater than the popped element, pop elements from the auxiliary stack and push them back to the input stack.
  3. Push the popped element onto the auxiliary stack.
  4. Repeat steps 1-3 until the input stack is empty.
  5. Once all elements are sorted in the auxiliary stack, transfer them back to the input stack in the correct order.

Code

Java
public Stack<Integer> sortStack(Stack<Integer> stack) {
	Stack<Integer> auxStk = new Stack<>();

	while (!stack.isEmpty()) {
		int value = stack.pop();

		while (!auxStk.isEmpty() && value < auxStk.peek()) {
			stack.push(auxStk.pop());
		}

		auxStk.push(value);
	}

	return auxStk;
}

Complexity

  • ⏰ Time complexity: O(n^2) where n is number of elements in stack
  • 🧺 Space complexity: O(n) for using aux stack.

Dry Run

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.

So, the logic is:

  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

Code

Java
public class StackSort {

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

		int x = 0;

		if (!s.isEmpty()) {
			x = s.pop();
			sortStack(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);
		}

	}

}

Complexity

  • ⏰ Time complexity: O(n^2)
  • 🧺 Space complexity: O(n) assuming recursion stack
Understanding time complexity
  • The sortStack function pops each element off the stack and calls itself recursively. Thus, it performs O(n) calls where n is the total number of elements in the stack.
  • For each element popped by sortStack, the insert function is called to insert it back in sorted order. In the worst case, insert might have to pop all the remaining elements from the stack, leading to a chain of recursive calls. To derive the time complexity, follow the flow of operations:
  1. sortStack is called once for each element in the stack. This results in O(n) calls in total. During these calls, elements are popped off the stack, taking O(1) time per pop.
  2. insert is called once for each element. In the worst case, inserting the n-th element may require popping and reinserting up to n-1 elements, making it O(n) work for an individual call to insert.

Therefore:

  • First call to sortStack: O(n), and it triggers insert for the first element.
  • Second call to sortStack after popping one element: O(n-1) calls to insert.
  • Third call to sortStack: O(n-2) calls to insert.
  • And so on…
Summing up these operations

The total time complexity of the recursive sort will be the sum of the series:

T(n) = T(n-1) + T(n-2) + ... + T(1)
 = O(n) + O(n-1) + O(n-2) + ... + O(1) 
 = O(n * (n+1)/2) = O(n^2)

Method 4 - Mimic-ing Quicksort

Can we improve this? By imitating quicksort, we start by selecting a pivot from the stack using pop. Next, we perform a partition by pushing all elements less than the pivot into one stack and those greater into another. Afterward, we recursively sort the two sub-stacks and merge them with the pivot in the middle. Given that we are limited to stack operations, I use pop to select the pivot. Merging can be complex, and alternative suggestions for this are welcome. This approach typically requires O(n log n) comparisons to sort n items but can take up to O(n^2) comparisons in the worst-case scenario, which occurs infrequently.

Here is the logic: Let’s break down the operations step-by-step to understand the time complexity:

  1. Base Case: If the stack s is empty, it is immediately returned. This has a constant time complexity of O(1).
  2. Pivot Selection: The pivot element is selected by popping the top element of the stack. This operation has O(1) time complexity.
  3. Partitioning: The elements in the stack s are partitioned into left and right depending on whether they are less than or greater than (or equal to) the pivot, respectively. Partitioning involves iterating through all elements in the stack once, so this step has O(n) time complexity for a stack of size n.
  4. Recursive Sort: The sortStack function is called recursively on the left and right stacks.
  5. Merging: Finally, the left stack (sorted) is merged together with the sorted right stack and the pivot into the original stack s. This involves emptying the right stack into a temporary stack tmp, pushing the pivot, emptying the left stack into tmp, and then reconstructing s by popping tmp. The merge step iterates through all elements again, so it has O(n) time complexity.

Code

Java
public Stack<Integer> sortStack(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);
		}
	}

	sortStack(left);
	sortStack(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;
}

Complexity

  • ⏰ Time complexity: O(n log n) in average case, and O(n^2) in worst case
  • 🧺 Space complexity: O(n) assuming recursion stack as well and left and right stacks.