Data Structures & Algorithms In Go/

...

/

Solution Review: Reverse Stack

Solution Review: Reverse Stack

Let's discuss in detail the implementation of the reverse stack problem.

We'll cover the following...

Solution #1: Using bottomInsert() function

In this approach, we use recursion to pop elements from the stack and use the bottomInsert() function to add them at the bottom. Eventually the whole stack is reversed.

Solution code

Press + to interact
main.go
stack.go
package main
import "fmt"
func bottomInsert(stk *Stack, element int) {
    var temp int
    if (stk.Length() == 0) {
        stk.Push(element)
    } else {
        temp = stk.Pop()
        bottomInsert(stk, element)
        stk.Push(temp)
    }
}
func reverseStack(stk *Stack) {
    if stk.IsEmpty() {
    return
    }
    value := stk.Pop()
    reverseStack(stk)
    bottomInsert(stk, value)
}
// Testing code
func main() {
    stk := new(Stack)
    stk.Push(1)
    stk.Push(2)
    stk.Push(3)
    fmt.Print("Stack before reversal : ")
    stk.Print()
    reverseStack(stk)
    fmt.Print("Stack after reversal : ")
    stk.Print()
}

Time complexity

The time complexity of this solution is ...