Greetings, Space Explorer! Today, we're drawing back the curtains on Stacks, a crucial data structure. Imagine a stack like a pile of dishes: you add a dish to the top (Last In) and take it from the top (First Out). This Last-In, First-Out (LIFO) principle exemplifies the stack. In Go, stacks can be implemented using slices, which offer a flexible way to store and manipulate elements. This lesson will illuminate the stack data structure, its operations, and its applications in Go. Are you ready to start?
To create a stack in Go, we can define a custom Stack struct with a slice as an internal storage. To perform the push operation, we use the append method to add an element to the slice's end. For the pop operation, we slice out the last element, simulating the removal of the "top" element in a stack. Here's how it looks:
Go1package main 2 3import ( 4 "fmt" 5) 6 7type Stack struct { 8 items []string 9} 10 11func (s *Stack) Push(item string) { 12 s.items = append(s.items, item) 13} 14 15func (s *Stack) Pop() string { 16 if len(s.items) == 0 { 17 return "" 18 } 19 item := s.items[len(s.items)-1] 20 s.items = s.items[:len(s.items)-1] 21 return item 22} 23 24func main() { 25 stack := Stack{} 26 27 // Push operations 28 stack.Push("John") 29 stack.Push("Mary") 30 stack.Push("Steve") 31 32 // Pop operation removes 'Steve' 33 stack.Pop() 34 fmt.Println(stack.items) // Outputs: [John Mary] 35}
In the example provided, we add (push) John, Mary, and Steve onto the stack and then remove (pop) Steve from the stack.
Stack operations in Go go beyond just push and pop. For example, to verify if a stack is empty, we check if the length of the items slice is 0. To peek at the top element of the stack without popping it, we access the last element of the slice.
Here's an example:
Go1package main 2 3import ( 4 "fmt" 5) 6 7type Stack struct { 8 items []string 9} 10 11func (s *Stack) Push(item string) { 12 s.items = append(s.items, item) 13} 14 15func (s *Stack) Pop() string { 16 if len(s.items) == 0 { 17 return "" 18 } 19 item := s.items[len(s.items)-1] 20 s.items = s.items[:len(s.items)-1] 21 return item 22} 23 24func (s *Stack) Peek() string { 25 if len(s.items) == 0 { 26 return "" 27 } 28 return s.items[len(s.items)-1] 29} 30 31func (s *Stack) IsEmpty() bool { 32 return len(s.items) == 0 33} 34 35func main() { 36 stack := Stack{} 37 stack.Push("Steve") 38 stack.Push("Sam") 39 40 fmt.Println(stack.Peek()) // Outputs: Sam 41 42 fmt.Println(stack.IsEmpty()) // Outputs: false 43 stack.Pop() // Remove 'Sam' 44 stack.Pop() // Remove 'Steve' 45 fmt.Println(stack.IsEmpty()) // Outputs: true 46}
In this example, Sam is added (pushed), and then the topmost stack element, which is Sam, is accessed (peeked at) without removal. Next, we verify if the stack is empty using the IsEmpty method, which checks if the stack has no elements. The output will be false because the stack is not empty at this point. We then perform two Pop operations to remove Sam and then Steve from the stack. After these Pop operations, when we check IsEmpty again, it will output true, indicating that the stack is now empty since all elements have been removed.
Practical applications of stacks in programming are plentiful. Here is one of them — reversing a string.
We will push all characters into a stack and then pop them out to get a reversed string!
Go1package main 2 3import ( 4 "fmt" 5) 6 7type Stack struct { 8 items []rune 9} 10 11func (s *Stack) Push(item rune) { 12 s.items = append(s.items, item) 13} 14 15func (s *Stack) Pop() rune { 16 if len(s.items) == 0 { 17 return 0 18 } 19 item := s.items[len(s.items)-1] 20 s.items = s.items[:len(s.items)-1] 21 return item 22} 23 24func Reverse(input string) string { 25 var stack Stack 26 27 for _, c := range input { 28 stack.Push(c) 29 } 30 31 var reversedString []rune 32 for len(stack.items) > 0 { 33 reversedString = append(reversedString, stack.Pop()) 34 } 35 36 return string(reversedString) 37} 38 39func main() { 40 fmt.Println(Reverse("HELLO")) // Outputs: OLLEH 41}
A stack can be utilized to verify if parentheses in an expression are well-matched; i.e., every bracket has a corresponding pair. For example, parentheses in the string "()[{}]" are well-matched, whereas they are not in strings "([]()", ")()[]{}", "([)]", and "[{})".
Here's how you can implement this logic in Go:
Go1package main 2 3import ( 4 "fmt" 5) 6 7type Stack struct { 8 items []rune 9} 10 11func (s *Stack) Push(item rune) { 12 s.items = append(s.items, item) 13} 14 15func (s *Stack) Pop() rune { 16 if len(s.items) == 0 { 17 return 0 18 } 19 item := s.items[len(s.items)-1] 20 s.items = s.items[:len(s.items)-1] 21 return item 22} 23 24func IsParenBalanced(parenString string) bool { 25 var stack Stack 26 openingParen := map[rune]rune{ 27 ')': '(', 28 ']': '[', 29 '}': '{', 30 } 31 32 for _, paren := range parenString { 33 if paren == '(' || paren == '[' || paren == '{' { 34 // We met an opening parenthesis, just putting it on the stack 35 stack.Push(paren) 36 } else if closing, exists := openingParen[paren]; exists { 37 // We met a closing parenthesis 38 if len(stack.items) == 0 || stack.items[len(stack.items)-1] != closing { 39 return false 40 } 41 stack.Pop() 42 } 43 } 44 45 return len(stack.items) == 0 46} 47 48func main() { 49 fmt.Println(IsParenBalanced("(())")) // Outputs: true 50 fmt.Println(IsParenBalanced("({[)}")) // Outputs: false 51}
Kudos to you! Covering the stack data structure, its operations, and their applications in Go is a commendable feat. Next up, you'll encounter practice exercises that will solidify your newly acquired knowledge. Dive into them and master Stacks in Go!