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!