Solution Review: Stack Using Linked List
This review provides a detailed analysis of stack implementation using linked lists.
We'll cover the following...
Solution
As mentioned in a previous lesson, a typical stack must contain the following functions:
Push(value)
Pop()
IsEmpty()
Peek()
Size()
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 Node struct {value intnext *Node}type StackLinkedList struct {head *Nodesize int}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() {}
Solution code
Press + to interact
package mainimport "fmt"type Node struct {value intnext *Node}type StackLinkedList struct {head *Nodesize int}//Size() function will return the size of the linked list.func (s *StackLinkedList) Size() int {return s.size}/* IsEmpty() function will return true if size of the linked list isequal to zero or false in all other cases. */func (s *StackLinkedList) IsEmpty() bool {return s.size == 0}/*First, the Peek() function will check if the stack is empty.If not, it will return the peek value of the stack, i.e., it will returnthe head value of the linked list. */func (s *StackLinkedList) Peek() (int, bool) {if s.IsEmpty() {fmt.Println("StackEmptyException")return 0, false}return s.head.value, true}//Push() function will append the value to the linked list.func (s *StackLinkedList) Push(value int) {s.head = &Node{value, s.head}s.size++}/*In the pop() function, first it will check that the stack is not empty.Then it will pop the value from the linked list and return it. */func (s *StackLinkedList) Pop() (int, bool) {if s.IsEmpty() {fmt.Println("StackEmptyException")return 0, false}value := s.head.values.head = s.head.nexts.size--return value, true}/* Print() function will print the elements of the linked list. */func (s *StackLinkedList) Print() {temp := s.headfmt.Print("Value stored in stock are :: ")for temp != nil {fmt.Print(temp.value, " ")temp = temp.next}fmt.Println()}// Testing codefunc main() {s := new(StackLinkedList)s.Push(1)s.Push(2)s.Push(3)val, _ := s.Peek()fmt.Println("Peek() of a stack is:",val)fmt.Print("Stack consist following elements: ")for s.IsEmpty() == false {val, _ = s.Pop()fmt.Print( val, " ")}}
Time complexities
Letās look at the time complexity of each stack operation.
Operation | Time Complexity |
---|---|
IsEmpty |