Search⌘ K
AI Features

Solution Review: Stack Using Array

Explore how to implement a stack data structure using arrays in Go. Understand the core stack operations such as push, pop, top, and isEmpty, along with their time complexities and implementation details.

We'll cover the following...

Solution

As mentioned in a previous lesson, a typical stack must contain the following functions:

  • Push(value)
  • Pop()
  • IsEmpty()
  • Top()

We’ll take a close look at these functions individually. But before we that, let’s start with constructing a Stack struct.

Go (1.6.2)
type StackInt struct {
s []int
}
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 {}

Now, let’s implement all operations of the stack ADT.

Go (1.6.2)
type StackInt struct {
s []int
}
/* Other Methods */
func (s *StackInt) IsEmpty() bool {
length := len(s.s)
return length == 0
}
func (s *StackInt) Length() int {
length := len(s.s)
return length
}
func (s *StackInt) Print() {
length := len(s.s)
for i := 0; i < length; i++ {
fmt.Print(s.s[i], " ")
}
fmt.Println()
}
func (s *StackInt) Push(value int) {
s.s = append(s.s, value)
}
func (s *StackInt) Pop() int {
if s.IsEmpty() == true{
fmt.Print("Stack is empty.")
return 0
}
length := len(s.s)
res := s.s[length-1]
s.s = s.s[:length-1]
return res
}
func (s *StackInt) Top() int {
if s.IsEmpty() == true{
fmt.Print("Stack is empty.")
return 0
}
length := len(s.s)
res := s.s[length-1]
return res
}
//Test code for stack.
func main() {
stack := new(StackInt)
//Push element to the stack
stack.Push(6)
stack.Push(3)
stack.Push(2)
stack.Push(5)
//Retrieve top element from the stack
fmt.Println("Top() of the stack is: ",stack.Top())
//Pop elements from the stack
fmt.Print("Stack consist of following elements: ")
for stack.IsEmpty() == false {
fmt.Print(stack.Pop(), " ")
}
}

Time complexities

Let’s look at the time complexity of each stack operation.

Operation Time Complexity
IsEmpty O(1)O(1)
...