골랭 스택 구현-Golang-php.cn

골랭 스택 구현

王林

풀어 주다： 2023-05-16 11:06:37

원래의

764명이 탐색했습니다.

Golang은 인터넷 업계에서 널리 사용되고 존경받는 효율적이고 확장 가능한 동시 프로그래밍 언어입니다. Golang 개발자에게 데이터 구조와 알고리즘은 기본 기술 중 하나이며, 스택 구현은 필수적인 부분입니다. 이 기사에서는 Golang에서 스택을 구현하는 방법에 대해 자세히 살펴보겠습니다.

스택이란 무엇인가요?

스택은 한쪽 끝에서만 작동할 수 있는 특수한 선형 구조입니다. 즉, 스택 상단에서만 요소를 삽입하고 삭제할 수 있습니다. 따라서 스택의 데이터 액세스 방법은 "First in, last out"입니다. 캐싱, 표현식 평가, 함수 호출 등과 같은 다양한 경우에 적합한 데이터 구조입니다.

일반적으로 사용되는 스택 작업에는 푸시와 팝이 포함됩니다. 푸시할 때 새 요소는 항상 스택의 맨 위에 배치되며, 맨 위의 요소는 항상 삭제되므로 스택 길이는 계속 변경됩니다.

스택 구현 방법

Golang에서 스택을 구현하는 방법에는 두 가지 방법이 있습니다. 하나는 Slice를 사용하는 것이고, 다른 하나는 Linked List를 사용하는 것입니다.

2.1 슬라이스 구현

슬라이스를 사용하여 스택을 구현할 때 스택 구조에는 슬라이스 하나만 포함하면 됩니다. 다음은 슬라이스 구현 스택의 간단한 예입니다.

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
}

로그인 후 복사

구현에서 먼저 data 슬라이스를 포함하는 Stack 구조를 정의합니다. Push() 함수는 요소를 스택의 맨 위로 밀어넣고 슬라이스의 끝에 요소를 추가합니다. Pop() 함수는 스택의 맨 위에서 요소를 팝합니다. 슬라이스의 마지막 요소를 가져와서 스택을 삭제합니다. 그런 다음 IsEmpty() 함수는 스택이 비어 있는지 확인합니다. Stack，它包含一个切片data。Push()函数将元素压入栈顶，依次将元素添加到切片末尾；Pop()函数将元素从栈顶弹出，通过获取切片中的最后一个元素，然后将该元素从切片中删除；IsEmpty()函数判断栈是否为空。

2.2 链表实现

链表实现栈的基本逻辑是使用链表的头部作为栈顶，每插入一个元素，就将其放在头部，每弹出一个元素就将头部的元素删除。下面是链表实现栈的示例：

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
}

로그인 후 복사

在实现中，我们首先定义一个结构体node表示链表的每一个节点。每个节点都包含一个元素val，和一个指向下一个节点的指针next。然后我们定义结构体Stack表示栈，其中head指针指向栈顶元素；Push()函数依次将元素插入到链表头部；Pop()函数通过先获取头部节点中的值，然后再将头部指针指向下一个节点实现弹出操作；IsEmpty()

2.2 연결 목록 구현

연결 목록 구현 스택의 기본 논리는 연결 목록의 헤드를 스택의 최상위로 사용하는 것입니다. 요소가 삽입될 때마다 해당 요소가 맨 위에 배치됩니다. 요소가 팝업되면 헤드의 요소가 삭제됩니다. 다음은 연결 목록 구현 스택의 예입니다.

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
}

로그인 후 복사

node

val

next

Stack

head

Push()

Pop()

IsEmpty()

스택 사용