ALGORITHM SERIES | How To Inverse Order A Stack Using Only Recursive Functions And Stack

calendar Jun 5, 2022 · 2 min read · algorithm English  ·
Share on: linkedin copy

Overview

Requirements

A stack is pressed into 1, 2, 3, 4, 5, then from the top of the stack to the bottom of the stack is 5, 4, 3, 2, 1. After transposing this stack, from the top of the stack to the bottom of the stack is 1, 2, 3, 4, 5, that is, to achieve the reverse order of the stack elements, but only with recursive functions to achieve, can not use other data structures.

Solution

  1. a function to implement the return of the data on the stack, used to return the bottom element of the stack, stop when the stack is empty

  2. another function accepts the bottom element of the stack and represses the data of each one onto the stack to achieve reverse order

Golang Implementation

 1package main
 2
 3import "fmt"
 4
 5func getAndRemoveLastElement(stack *Stack) int {
 6	result := stack.Pop()
 7	if stack.Len() == 0 {
 8		return result.(int)
 9	} else {
10		last := getAndRemoveLastElement(stack)
11		stack.Push(result)
12		return last
13	}
14}
15
16func reverse(stack *Stack) {
17	if stack.Len() == 0 {
18		return
19	} else {
20		garFuncReturn := getAndRemoveLastElement(stack)
21		reverse(stack)
22		stack.Push(garFuncReturn)
23	}
24}

Test Cases

 1package main
 2
 3import (
 4	"testing"
 5
 6	"github.com/stretchr/testify/assert"
 7)
 8
 9func TestReverseStack(t *testing.T) {
10	// define a getmin stack
11	tests := []struct {
12		name string
13
14		val func(stk *Stack)
15
16		wantRes []any
17	}{
18		{
19			name: "push",
20			val:  push,
21			// transpose once, then return to the original order of last-in first-out
22			wantRes: []any{1, 2, 3, 4, 5},
23		},
24	}
25	for _, tt := range tests {
26		// new TwoStackQueue
27		stk := NewStack()
28		t.Run(tt.name, func(t *testing.T) {
29			tt.val(stk)
30			reverse(stk)
31			res := popall(stk)
32			assert.Equal(t, tt.wantRes, res)
33		})
34	}
35}
36
37func push(stk *Stack) {
38	for i := 1; i <= 5; i++ {
39		stk.Push(i)
40	}
41}
42
43func popall(stk *Stack) (resultList []any) {
44	for {
45		if stk.length == 0 {
46			break
47		}
48		resultList = append(resultList, stk.Pop())
49	}
50	return resultList
51}

Result:

1$ go test -run ^TestReverseStack$ . -v 
2=== RUN   TestReverseStack
3=== RUN   TestReverseStack/push
4--- PASS: TestReverseStack (0.00s)
5    --- PASS: TestReverseStack/push (0.00s)
6PASS
7ok      starkreverse    0.008s

Implementation is relatively simple, the focus is the need to draw the call-stack diagram, each layer of the variable is what value sorted out, when to pop up, this is much easier to use a pen to draw.