golang stack implementation

Golang is an efficient, scalable and concurrency-rich programming language that is widely used and respected in the Internet industry. For Golang developers, data structures and algorithms are one of the basic skills, and the implementation of the stack is an essential part. In this article, we will take a deep dive into how to implement a stack in Golang.

1. What is a stack?

The stack is a special linear structure that can only be operated on one end, that is, elements can only be inserted and deleted at the top of the stack. Therefore, the data access method of the stack is "first in, last out". It is a data structure suitable for many occasions, such as caching, expression evaluation, function calling, etc.

Commonly used stack operations include push and pop. When pushing, new elements are always placed on the top of the stack; when popping, the top of the stack is always deleted. elements, so the length of the stack will continue to change.

2. How to implement the stack

There are two ways to implement the stack in Golang: one is to use slices, and the other is to use linked lists. ).

2.1 Slice implementation

When using slices to implement a stack, our stack structure only needs to contain one slice. The following is a simple example of a slice implementation stack:

type Stack struct {
  data []interface{}
}

func (s *Stack) Push(val interface{}) {
    s.data = append(s.data, val)
}

func (s *Stack) Pop() interface{} {
    if s.IsEmpty() {
        return nil
    }
    last := s.data[len(s.data)-1]
    s.data = s.data[:len(s.data)-1]
    return last
}

func (s *Stack) IsEmpty() bool {
    return len(s.data) == 0
}

In the implementation, we first define a structure Stack, which contains a slice data. Push()The function pushes elements onto the top of the stack and adds elements to the end of the slice in turn; Pop()The function pops elements from the top of the stack by getting the last element in the slice , and then delete the element from the slice; IsEmpty() function determines whether the stack is empty.

2.2 Linked list implementation

The basic logic of linked list implementation stack is to use the head of the linked list as the top of the stack. Every time an element is inserted, it is placed at the head, and every time an element is popped out, it is placed at the head. The header element is deleted. The following is an example of a linked list implementation stack:

type node struct {
  val  interface{}
  next *node
}

type Stack struct {
  head *node
}

func (s *Stack) Push(val interface{}) {
  s.head = &node{val, s.head}
}

func (s *Stack) Pop() interface{} {
  if s.head == nil {
    return nil
  }
  val := s.head.val
  s.head = s.head.next
  return val
}

func (s *Stack) IsEmpty() bool {
  return s.head == nil
}

In the implementation, we first define a structure node to represent each node of the linked list. Each node contains an element val, and a pointer to the next node next. Then we define the structure Stack to represent the stack, where the head pointer points to the top element of the stack; Push() The function inserts elements into the head of the linked list in sequence; Pop()The function realizes the pop operation by first obtaining the value in the head node, and then pointing the head pointer to the next node; the IsEmpty() function determines whether the stack is empty.

3. Using the Stack

The functions provided by the stack are a way to enhance the processing of complex problems. Problems such as expression evaluation and bracket matching can be well solved using the stack. The following is an example of expression evaluation code implemented using slicing:

func EvaluateExpression(expression string) (float64, error) {
  stack := Stack{}
  tokens := strings.Split(expression, " ")
  for _, token := range tokens {
    switch token {
      case "+", "-", "*", "/":
        if stack.IsEmpty() {
          return 0, errors.New("Invalid expression")
        }
        b, err := stack.Pop().(float64)
        if !err {
          return 0, errors.New("Invalid expression")
        }
        if stack.IsEmpty() {
          return 0, errors.New("Invalid expression")
        }
        a, err := stack.Pop().(float64)
        if !err {
          return 0, errors.New("Invalid expression")
        }
        var result float64
        switch token {
          case "+":
            result = a + b
          case "-":
            result = a - b
          case "*":
            result = a * b
          case "/":
            result = a / b
        }
        stack.Push(result)
      default:
        num, err := strconv.ParseFloat(token, 64)
        if err != nil {
          return 0, errors.New("Invalid expression")
        }
        stack.Push(num)
    }
  }
  if stack.IsEmpty() {
    return 0, errors.New("Invalid expression")
  }
  result, err := stack.Pop().(float64)
  if !err || !stack.IsEmpty() {
    return 0, errors.New("Invalid expression")
  }
  return result, nil
}

In expression evaluation, we use the idea of ​​​​the stack to process reverse Polish expressions. First split the expression by spaces, and then process each part. If it is an operator (- * /), the two elements at the top of the stack are taken out, the corresponding operation is performed, and the result is pushed onto the stack; if it is an operand, it is pushed onto the stack directly. Finally, if the stack is not empty, the value at the top of the stack is returned as the result of the operation.

4. Summary

The stack is a very practical data structure that is widely used in many situations. There are many ways to implement stacks using Golang. This article mainly introduces two implementation methods: slices and linked lists. The implementation of slicing is simple and easy to understand, but when the elements reach a large size, the efficiency of memory allocation will decrease; the implementation of linked list memory allocation is more flexible, but the complexity of the code also increases. Reasonable selection of implementation methods can avoid unnecessary waste of resources in practical applications and improve program execution efficiency.

The above is the detailed content of golang stack implementation. For more information, please follow other related articles on the PHP Chinese website!