Problem statement

Given a stack, sort it in ascending order using only one additional stack.

Constraints:

• You may not use any other data structure such as arrays or linked lists.

Solution

The problem can be solved using only one additional stack. We repeatedly move values between the two stacks, comparing the top elements (the “peek” values) to build a stack sorted in ascending order such that the smallest number ends up at the top of the sorted stack.

In this post I’ll explain two approaches: the common double‑loop insertion method, and a single‑loop variation that was my first attempt.

Let’s go for the most common solution with a double loop:

Double loop solution

Introduction

We will need:

• An additional stack where we are going to store the stack sorted in ascending order.

We iterate through the original input stack:

Step 1

Pop the top of the input stack and store it in a temporary variable called current

If the sorted stack is empty, push current to the sorted stack and continue with the next element.

Step 2

While the sorted stack is not empty and current > sortedStack.top():

• Pop from the sorted stack and push that element back onto the input stack.

This moves smaller elements back to the input so the larger current sinks lower in the sorted stack. When the loop finishes we know either the sorted stack is empty or its top is ≥ current.

Step 3

Push current onto the sorted stack. All elements below are ≥ current, and smaller elements will be reprocessed later to sit above it, preserving “smallest on top” ordering.

Example

Let’s see an example with the input stack: [5, 3, 1, 4, 2]

Code

export function sortStack(stack: Stack<number>): Stack<number> {
  const sortedStack = new Stack<number>();

  while (!stack.isEmpty()) {
    const current = stack.top()!;
    stack.pop();

    while (!sortedStack.isEmpty() && current > sortedStack.top()!) {
      const temp = sortedStack.top()!;
      sortedStack.pop();
      stack.push(temp);
    }
    sortedStack.push(current);
  }

  return sortedStack;
}

Complexity analysis

Time complexity: O(n²) in the worst case (reverse‑sorted input causes many reinsertions).
Space complexity: O(n) for the auxiliary stack.

Single loop solution

This solution is similar, but instead of an inner loop that repositions all out‑of‑order elements in one pass, it performs at most one adjustment per outer iteration. Let’s examine it in more detail:

Iterate through the original input stack:

Step 1

Pop the top of the input stack and store it in a temporary variable (called current).

If the sorted stack is empty, push current to the sorted stack and continue with the next element from the input stack.

Step 2

If the sorted stack is not empty and current > sortedStack.top():

• Pop from the sorted stack and push that element back onto the input stack.

This moves one smaller element out of the way so current can sink slightly lower.

Otherwise push current onto the sorted stack.

Example

Let’s see the same example as with the double loop with the input stack: [5, 3, 1, 4, 2]

Code

export function sortStack(stack: Stack<number>): Stack<number> {
  const sortedStack = new Stack<number>();

  while (!stack.isEmpty()) {
    const current = stack.top()!;
    stack.pop();

    if (!sortedStack.isEmpty() && current > sortedStack.top()!) {
      const temp = sortedStack.top()!;
      sortedStack.pop();
      stack.push(temp);
      stack.push(current);
      continue;
    }
    sortedStack.push(current);
  }

  return sortedStack;
}

Complexity analysis

Time complexity: Still O(n²) worst‑case; the work is spread across more outer iterations instead of concentrated in inner loops.
Space complexity: O(n) for the auxiliary stack.

Conclusion

Both solutions effectively sort a stack using only one additional stack. The double loop solution is more straightforward and easier to understand, while the single loop solution is a bit more complex but achieves the same result with a slightly different approach. Depending on the specific requirements and constraints of your application, you may choose one over the other.

The single‑loop solution was my first attempt; by leveraging only stack operations (peek, pop, push) we can still reach a clean ascending ordering with the smallest element on top.