Data Structures & Algorithms In Go/

...

/

Solution Review: Sort Stack

Solution Review: Sort Stack

This review will provide a detailed analysis of how to sort the elements of a stack.

We'll cover the following...

First solution: Using the sorted insert function

In this approach, we recursively call the sortStack() function. Then we call the sortedInsert() function inside the recursion to sort the stack.

Solution code

Press + to interact
main.go
stack.go
package main
func sortedInsert(stk *Stack, element int) {
    var temp int
    if (stk.Length() == 0 || element > stk.Top()) {
        stk.Push(element)
    } else {
        temp = stk.Pop()
        sortedInsert(stk, element)
        stk.Push(temp)
    }
}
func sortStack(stk *Stack) {
    var temp int
    if (stk.Length() > 0) {
        temp = stk.Pop()
        sortStack(stk)
        sortedInsert(stk, temp)
    }
}
// Testing code
func main() {
    stk := new(Stack)
    stk.Push(1)
    stk.Push(4)
    stk.Push(3)
    stk.Push(2)
    sortStack(stk)
    stk.Print()
}

Time complexity

The time complexity of this approach is O(n2)O( ...