链表专题(Golang)
中小厂手写题中最常见的是链表
LRU
用链表实现栈
package mainimport ("fmt"
)type Node struct {Value intNext *Node
}type Stack struct {top *Node
}// Push adds a new element to the top of the stack.
func (s *Stack) Push(value int) {newNode := &Node{Value: value, Next: s.top}s.top = newNode
}// Pop removes the top element from the stack and returns its value.
// If the stack is empty, it returns -1 as an indicator.
func (s *Stack) Pop() int {if s.IsEmpty() {return -1 // Or any other sentinel value or error handling}value := s.top.Values.top = s.top.Nextreturn value
}// Peek returns the value of the top element without removing it.
func (s *Stack) Peek() int {if s.IsEmpty() {return -1 // Or any other sentinel value or error handling}return s.top.Value
}// IsEmpty checks if the stack is empty.
func (s *Stack) IsEmpty() bool {return s.top == nil
}// Test function to verify the correctness of the stack implementation.
func testStack() {stack := &Stack{}// Test pushing elementsstack.Push(10)stack.Push(20)stack.Push(30)// Test peeking the top elementif stack.Peek() != 30 {fmt.Println("Peek failed")}// Test popping elementsif stack.Pop() != 30 {fmt.Println("Pop failed for value 30")}if stack.Pop() != 20 {fmt.Println("Pop failed for value 20")}// Test popping from an empty stack should return -1if stack.Pop() != 10 {fmt.Println("Pop failed for value 10")}if stack.Pop() != -1 {fmt.Println("Pop from empty stack failed")}fmt.Println("All tests passed!")
}