This post is completed by 1 user

  • 0
 Add to List
Medium

388. Sort a given stack - Using Temporary Stack

Objective: Given a stack of integers, write an algorithm to sort the stack using a temporary stack. 

Example:

Given Stack: [14, 9, 67, 91, 101, 25]

Sorted Stack: [9, 14, 25, 67, 91, 101]

Approach:

  1. Use another stack, let's call it a temporary stack.
  2. While given original is not empty
    1. Pop the element from the original stack, let's call it x.
    2. while the temporary stack is not empty and top of the temporary stack is greater than the popped element x - pop the element from the temporary stack and push it back to the original stack.
    3. At this point either temporary stack is empty or top of the temporary stack is <= x so push x in the temporary stack.
  3. Return the temporary stack, it is sorted.

Walk Through:

Original Stack: [67, 91, 101, 25]
------------------------------------------------
Popped Element from the original stack: 25
Push 25 in the temporary stack
Original Stack: [67, 91, 101]
Temporary Stack: [25]
------------------------------------------------
Popped Element from the original stack: 101
Push 101 in the temporary stack
Original Stack: [67, 91]
Temporary Stack: [25, 101]
------------------------------------------------
Popped Element from the original stack: 91
top of temporary stack 101 is greater than popped element 91
101 pop from the temporary stack and push it to the original stack.
Original Stack: [67, 101]
Temporary Stack: [25]
Push 91 in the temporary stack
Original Stack: [67, 101]
Temporary Stack: [25, 91]
------------------------------------------------
Popped Element from the original stack: 101
Push 101 in the temporary stack
Original Stack: [67]
Temporary Stack: [25, 91, 101]
------------------------------------------------
Popped Element from the original stack: 67
top of temporary stack 101 is greater than popped element 67
101 pop from the temporary stack and push it to the original stack.
Original Stack: [101]
Temporary Stack: [25, 91]
top of temporary stack 91 is greater than popped element 67
91 pop from the temporary stack and push it to the original stack.
Original Stack: [101, 91]
Temporary Stack: [25]
Push 67 in the temporary stack
Original Stack: [101, 91]
Temporary Stack: [25, 67]
------------------------------------------------
Popped Element from the original stack: 91
Push 91 in the temporary stack
Original Stack: [101]
Temporary Stack: [25, 67, 91]
------------------------------------------------
Popped Element from the original stack: 101
Push 101 in the temporary stack
Original Stack: []
Temporary Stack: [25, 67, 91, 101]
Sorted Stack is:[25, 67, 91, 101]

Output:

Original Stack: [14, 9, 67, 91, 101, 25]
Sorted Stack is:[9, 14, 25, 67, 91, 101]

Related Problems: