Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

go

How can stacks be implemented in Go

Hassaan Waqar

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

The illustration below shows how a stack works:

How a stack works

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.

Implementation

Stacks can be implemented using an array or a linked list in Go.

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?

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:")
    fmt.Println(stack.Pop()) // Remove an item
    fmt.Println("Updated Stack:")
    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.

Using a Linked List

A stack implemented using a linked list does not have an upper bound on the number of items that can be added. An item is added to the head of the linked list using the push operation. Therefore, with each addition, the head pointer changes. Similarly, the head of the linked list is removed using the pop operation. The head pointer then points to the second node in the linked list.

The illustration below shows how a linked list-based stack works:

How does a linked list-based stack works?

A linked list basedstack implementation can be broken down into several functions. The purpose of each function is discussed below:

Function Purpose
Size 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
Peek Returns the value at the top of the linked list but does not remove it
Print Displays all elements of the stack

Function definitions

The functions used to implement an linked list based stack are defined as follows:

func (s *StackLinkedList) Size() int {}
func (s *StackLinkedList) IsEmpty() bool {}
func (s *StackLinkedList) Peek() (int, bool) {}
func (s *StackLinkedList) Push(value int) {}
func (s *StackLinkedList) Pop() (int, bool) {}
func (s *StackLinkedList) Print() {}

Example

The code below shows a linked list-based implementation of the stack in Golang:

package main
import "fmt"

type Node struct {
 value int
 next *Node
}

type StackLinkedList struct {
 head *Node
 size int
}

// Size() function 
func (s *StackLinkedList) Size() int {
    return s.size
}

// IsEmpty() function 
func (s *StackLinkedList) IsEmpty() bool {
    return s.size == 0
}

// Peek() function 
func (s *StackLinkedList) Peek() (int) {
    if s.IsEmpty() {
        fmt.Println("StackEmptyException")
        return 0
    }
    return s.head.value
}

// Push() function
func (s *StackLinkedList) Push(value int) {
    s.head = &Node{value, s.head}
    s.size++
}

// Pop() function
func (s *StackLinkedList) Pop() (int, bool) {
    if s.IsEmpty() {
        fmt.Println("StackEmptyException")
        return 0, false
    }
    value := s.head.value
    s.head = s.head.next
    s.size--
    return value, true
}

// Print() function will print the elements of the linked list. */
func (s *StackLinkedList) Print() {
    temp := s.head
    fmt.Print("Values stored in stack are: ")
    for temp != nil {
        fmt.Print(temp.value, " ")
        temp = temp.next
    }
    fmt.Println()
}

func main() {
	var stack StackLinkedList // create a stack variable of type StackLinkedList

  // Adding items to stack
	stack.Push(1)
	stack.Push(2)
	stack.Push(3)
  
  stack.Print() // Print the stack
  fmt.Println("Checking length of stack:")
  fmt.Println(stack.Size()) // Get Length
  fmt.Println("Removing an Item:")
  stack.Pop() // Remove an item
  stack.Print() 
  fmt.Println("Getting Item at Top of Linked List")
  fmt.Println(stack.Peek()) // Get Top-most item
}

Explanation

  • An object of the struct StackLinkedList is created named stack. It refers to a head node and has an int variable to keep track of the size of the stack.
  • The push function creates a new head node. It assigns it the int value that is passed in the parameter. 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 checks if the stack is empty. It raises an exception in that case. Otherwise, it makes the second node in the linked list the head node and deletes the first node. It also decrements the size variable by one.
  • The peek function returns the value of the head node of the linked list.
  • The print function iterates over each node and prints its value.

RELATED TAGS

go

CONTRIBUTOR

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

View all Courses

Keep Exploring