Search⌘ K
AI Features
Home
Courses
Data Structures & Algorithms In Go

Solution Review: Sort Stack

Learn to sort a stack by exploring two key solutions in Go: a recursive sorted insert method and an iterative approach using two stacks. Understand each method's implementation details and analyze their time complexity for effective stack management.

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

Go (1.6.2)
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(n^2) ...