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 stackstack.Push(6)stack.Push(3)stack.Push(2)stack.Push(5)//Retrieve top element from the stackfmt.Println("Top() of the stack is: ",stack.Top())//Pop elements from the stackfmt.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 |