...

/

Solution Review: Stack Using Array

Solution Review: Stack Using Array

Let's discuss in detail how to implement a stack with an array.

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.

Press + to interact
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.

Press + to interact
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)
...