Implement three Stacks using one array

concept

Link : stackoverflow

my GO code

package main
import "log"

const ARRAY_SIZE = 10
const ARRAY_HALF_SIZE = int(float32(ARRAY_SIZE) * 0.5)

type StackNode struct {
    next *StackNode
    data int
}

type Stack struct {
    top *StackNode
    size int
    topIndex int // array index
}

func (stack *Stack) push(item *StackNode) {
    item.next = stack.top
    stack.top = item
    stack.size++
}

func main() {
    // initialize
    dataMap := map[int]*StackNode{}
    for i :=0; i < ARRAY_SIZE; i++ {
        dataMap[i] = nil
    }
    stack1 := &Stack{topIndex : 0}
    stack2 := &Stack{topIndex : ARRAY_SIZE-1}
    stack3 := &Stack{topIndex : ARRAY_HALF_SIZE}
    
    dynamicStackPush(dataMap, stack1, createNode(1))
    dynamicStackPush(dataMap, stack1, createNode(11))

    dynamicStackPush(dataMap, stack2, createNode(2))
    dynamicStackPush(dataMap, stack2, createNode(22))
    dynamicStackPush(dataMap, stack2, createNode(222))
    dynamicStackPush(dataMap, stack2, createNode(2222))
    
    dynamicStackPush(dataMap, stack3, createNode(3))
    dynamicStackPush(dataMap, stack3, createNode(33))
    dynamicStackPush(dataMap, stack3, createNode(333))
    
    printDataMap(dataMap)
}

func createNode(data int) *StackNode {
    return &StackNode{data : data}
}

func findNilIndexFromFront(dataMap map[int]*StackNode) int {
    for i := 0; i < ARRAY_HALF_SIZE; i++ {
        if dataMap[i] == nil {
            return i
        }
    }
    return -1
}

func findNilIndexFromMiddle(dataMap map[int]*StackNode, curIndex int) int {
    for i := curIndex; i < ARRAY_SIZE; i++ {
        if dataMap[i] == nil {
            return i
        }
    }
    return -1
}

func findNilIndexFromBack(dataMap map[int]*StackNode) int {
    for i := ARRAY_SIZE; i > ARRAY_HALF_SIZE; i-- {
        if dataMap[i] == nil {
            return i
        }
    }
    return -1
}

func moveArrayValue(dataMap map[int]*StackNode, startIndex, endIndex, moveCount int) {
    for i := startIndex; i < endIndex; i++ {
        dataMap[i-moveCount] = dataMap[i]
        dataMap[i] = nil
    }
}

func dynamicStackPush(dataMap map[int]*StackNode, stack *Stack, item *StackNode) {
    i := -1
    if stack.topIndex == 0 {
        // stack1 (using 0~array half size(max))
        i = findNilIndexFromFront(dataMap)
    } else if stack.topIndex == ARRAY_SIZE - 1 {
        // stack2 (using array size - 1 ~ array half size(max))
        i = findNilIndexFromBack(dataMap)
    } else {
        // stack3
        i = findNilIndexFromMiddle(dataMap, stack.topIndex)
    }
    if i >= 0 {
        dataMap[i] = item
        stack.push(item)
        return
    } else if stack.topIndex != 0 && stack.topIndex != ARRAY_SIZE - 1 {
        i = findNilIndexFromFront(dataMap)
        if i > 0 {
            newTopIndex := int(float32(i + stack.topIndex) * 0.5)
            moveArrayValue(dataMap, stack.topIndex, stack.topIndex + stack.size, stack.topIndex - newTopIndex )
            stack.topIndex = newTopIndex
            dataMap[stack.topIndex + stack.size] = item
            stack.push(item)
            return
        }
    }
    
    log.Printf( "Stack is Full" )
}

func printDataMap(dataMap map[int]*StackNode) {
    for i :=0; i < ARRAY_SIZE; i++ {
        if dataMap[i] != nil {
            log.Printf( "[%d] %d", i, dataMap[i].data )
        }
    }
}

result

[0] 1
[1] 11
[3] 3
[4] 33
[5] 333
[7] 2222
[8] 222
[9] 22

execution time

O(N)