Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

go

How to implement a stack using an array in Go

Hassaan Waqar

A Stack is an abstract data type for data storage. It follows the LIFOlast-in-first-out for retrieving data. Elements that are added at the end are removed first.

The illustration below shows how a stack works:

How does a stack work?

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:

How does an array-based stack work?

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)O(1)
Top O(1)O(1)
Length O(1)O(1)
Push O(1)O(1)
Pop O(1)O(1)
Print O(n)O(n)

RELATED TAGS

go

CONTRIBUTOR

Hassaan Waqar
Copyright ©2022 Educative, Inc. All rights reserved
RELATED COURSES

View all Courses

Keep Exploring