ALGORITHM SERIES | Designing A Stack With 'getMin' Function

 1package main
 2
 3import "sync"
 4
 5type (
 6	Stack struct {
 7		top    *node
 8		length int
 9		lock   *sync.RWMutex
10	}
11	node struct {
12		value interface{}
13		prev  *node
14	}
15)
16
17// NewStack Create a new stack
18func NewStack() *Stack {
19	return &Stack{nil, 0, &sync.RWMutex{}}
20}
21
22// Len Return the number of items in the stack
23func (s *Stack) Len() int {
24	return s.length
25}
26
27// Peek View the top item on the stack
28func (s *Stack) Peek() interface{} {
29	if s.length == 0 {
30		return nil
31	}
32	return s.top.value
33}
34
35// Pop the top item of the stack and return it
36func (s *Stack) Pop() interface{} {
37	s.lock.Lock()
38	defer s.lock.Unlock()
39	if s.length == 0 {
40		return nil
41	}
42	n := s.top
43	s.top = n.prev
44	s.length--
45	return n.value
46}
47
48// Push a value onto the top of the stack
49func (s *Stack) Push(value interface{}) {
50	s.lock.Lock()
51	defer s.lock.Unlock()
52	n := &node{value, s.top}
53	s.top = n
54	s.length++
55}

 1package main
 2
 3import (
 4	"fmt"
 5)
 6
 7type GetMinStack struct {
 8	stackData *Stack
 9	stackMin  *Stack
10}
11
12func NewGetMinStack() *GetMinStack {
13	return &GetMinStack{
14		stackData: NewStack(),
15		stackMin:  NewStack(),
16	}
17}
18
19func (gms *GetMinStack) Push(newNumber int) {
20	if gms.stackMin.length == 0 {
21		gms.stackMin.Push(newNumber)
22	} else if newNumber <= gms.GetMin().(int) {
23		gms.stackMin.Push(newNumber)
24	}
25	gms.stackData.Push(newNumber)
26}
27
28func (gms *GetMinStack) Pop() int {
29	if gms.stackMin.length == 0 {
30		_ = fmt.Errorf("your stack is empty")
31		return 0
32	}
33	value := gms.stackData.Pop()
34	if value == gms.GetMin() {
35		gms.stackMin.Pop()
36	}
37	return value.(int)
38}
39
40func (gms *GetMinStack) GetMin() interface{} {
41	if gms.stackMin.length == 0 {
42		_ = fmt.Errorf("your stack is empty")
43		return 0
44	} else {
45		return gms.stackMin.Peek()
46	}
47}

 1package main
 2
 3import (
 4	"testing"
 5
 6	"github.com/stretchr/testify/assert"
 7)
 8
 9// TDD
10func TestGetMinStack_GetMin(t *testing.T) {
11	// define a getmin stack
12	tests := []struct {
13		// name
14		name string
15
16		// input section
17		val func(gms *GetMinStack)
18
19		// output section
20		wantRes interface{}
21	}{
22		{
23			name:    "getmin after push",
24			val:     push,
25			wantRes: 1,
26		},
27		{
28			name:    "getmin after push and pop",
29			val:     pushpop,
30			wantRes: 3,
31		},
32		{
33			name: "getmin for empty GetMinStack",
34			val:  empty,
35			// default return 0
36			wantRes: 0,
37		},
38	}
39	for _, tt := range tests {
40		gms := NewGetMinStack()
41		t.Run(tt.name, func(t *testing.T) {
42			tt.val(gms)
43			res := gms.GetMin()
44			assert.Equal(t, tt.wantRes, res)
45		})
46	}
47}
48
49func push(gms *GetMinStack) {
50	gms.Push(5)
51	gms.Push(3)
52	gms.Push(1)
53	gms.Push(8)
54}
55
56func pushpop(gms *GetMinStack) {
57	gms.Push(5)
58	gms.Push(3)
59	gms.Push(1)
60	gms.Push(8)
61	gms.Pop()
62	gms.Pop()
63}
64
65func empty(gms *GetMinStack) {
66}

 1$ go test -run ^TestGetMinStack_GetMin$ -v .
 2=== RUN   TestGetMinStack_GetMin
 3=== RUN   TestGetMinStack_GetMin/getmin_after_push
 4=== RUN   TestGetMinStack_GetMin/getmin_after_push_and_pop
 5=== RUN   TestGetMinStack_GetMin/getmin_for_empty_GetMinStack
 62022/08/30 15:14:48 your stack is empty
 7--- PASS: TestGetMinStack_GetMin (0.00s)
 8    --- PASS: TestGetMinStack_GetMin/getmin_after_push (0.00s)
 9    --- PASS: TestGetMinStack_GetMin/getmin_after_push_and_pop (0.00s)
10    --- PASS: TestGetMinStack_GetMin/getmin_for_empty_GetMinStack (0.00s)
11PASS
12ok      command-line-arguments  0.008s