How to implement a stack using an array in Go

Explanation

Step 1: The stack is initially empty.

Step 2: A push operation adds an item to the top of the stack. The top shifts one place above its previous position.

Step 3: Each subsequent push adds an item to the top of the stack.

Step 4: A pop command removes an item from the top-1 position of the stack. The top shifts one place below its previous position.

Array-based Implementation

A stack can be implemented using an array.

An array is used when the stack is of a fixed size. Items are always added to the top of the stack. A variable known as top is used for this purpose.

The illustration below shows how an array-based stack works:

Implementation

An array-based stack implementation can be broken down into several functions. The purpose of each function is discussed below:

Function	Purpose
`Length`	Returns the number of items in the stack
`Push`	Adds a data item to the stack
`Pop`	Removes a data item from the stack
`IsEmpty`	Returns true if the stack is empty. Else, returns false
`Top`	Returns the last added value to the stack but does not remove it
`Print`	Displays all elements of the stack

Function definitions

The functions used to implement an array-based stack are defined as follows:

func (s *StackInt) IsEmpty() bool {}
func (s *StackInt) Length() int {}
func (s *StackInt) Print() {}
func (s *StackInt) Push(value int) {} 
func (s *StackInt) Pop() int {}
func (s *StackInt) Top() int {}

Example

The code below shows an array-based implementation of the stack in Golang:

package main
import "fmt"
type StackInt struct {
 s []int
}
// isEmpty() function 
func (s *StackInt) IsEmpty() bool {
    length := len(s.s)
    return length == 0
}
// length() function 
func (s *StackInt) Length() int {
    length := len(s.s)
    return length
}
// Print() function
func (s *StackInt) Print() {
    length := len(s.s)
    for i := 0; i < length; i++ {
        fmt.Print(s.s[i], " ")
    }
    fmt.Println()
}
// Push() function 
func (s *StackInt) Push(value int) {
    s.s = append(s.s, value)
}
// Pop() function
func (s *StackInt) Pop() int {
    length := len(s.s)
    res := s.s[length-1]
    s.s = s.s[:length-1]
    return res
}
// Top() function 
func (s *StackInt) Top() int {
    length := len(s.s)
    res := s.s[length-1]
    return res
}
func main() {
    var stack StackInt // create a stack variable of type Stack
    /* Adding items to stack */
    stack.Push(1)
    stack.Push(2)
    stack.Push(3)
    fmt.Println("Printng the stack:")    
    stack.Print() // Print the stack
    fmt.Println("Checking length of stack:")
    fmt.Println(stack.Length()) // Get Length
    fmt.Println("Removing an Item:")
    stack.Pop() // Remove an item
    stack.Print() 
    fmt.Println("Getting last Added Item in Stack")
    fmt.Println(stack.Top()) // Get last item
}

Explanation

An object of the struct StackInt is created named stack. It refers to our stack array.
The push function appends the provided value to the stack. In our case, we push three values separately into the stack.
The length function returns the number of elements in the stack.
The pop function first computes the length of the stack. It then removes the last element and returns it.
The top function first computes the length of the stack. It then returns the last element added to the stack.
The print function iterates over each element and prints it.

Time complexity

Let us examine the time complexity for each operation in an array-based stack:

Operation	Time Complexity
`IsEmpty`	$O(1)$
`Top`	$O(1)$
`Length`	$O(1)$
`Push`	$O(1)$
`Pop`	$O(1)$
`Print`	$O(n)$

Free Resources