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

Solution Review: Reverse Stack

Explore two approaches to reverse a stack in Go. Understand how to use recursion with a bottomInsert function and how to use a queue to reverse the elements. This lesson helps you implement these solutions and analyze their time complexities for effective stack manipulation.

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

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