골랭 스택 구현

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

1. 스택이란 무엇인가요?

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

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

2. 스택 구현 방법

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 연결 목록 구현

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

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() 함수는 스택이 비어 있는지 여부를 결정합니다.

스택 사용

4. 스택에서 제공하는 기능은 복잡한 문제의 처리 능력을 향상시키는 방법입니다. 표현식 평가, 대괄호 일치 등의 문제는 스택을 사용하여 잘 해결할 수 있습니다. 다음은 슬라이싱을 이용하여 구현한 표현식 평가 코드의 예입니다.
rrreee

표현식 평가에서는 ​​​​스택 개념을 활용하여 역 폴란드식 표현식을 처리합니다. 먼저 표현식을 공백으로 분할한 다음 각 부분을 처리합니다. 연산자(+ - */)인 경우 스택 맨 위에 있는 두 요소를 제거하고 해당 연산을 수행하며 결과가 피연산자인 경우 스택에 푸시됩니다. 스택을 직접. 마지막으로 스택이 비어 있지 않으면 스택 상단의 값이 작업 결과로 반환됩니다.

🎜요약🎜🎜🎜Stack은 다양한 상황에서 폭넓게 응용할 수 있는 매우 실용적인 데이터 구조입니다. Golang을 사용하여 스택을 구현하는 방법에는 여러 가지가 있습니다. 이 기사에서는 주로 슬라이스와 연결 목록이라는 두 가지 구현 방법을 소개합니다. 슬라이싱의 구현은 간단하고 이해하기 쉽지만 요소의 크기가 커지면 메모리 할당의 효율성이 감소합니다. 연결 목록 메모리 할당의 구현은 더 유연하지만 코드의 복잡성도 증가합니다. 구현 방법을 합리적으로 선택하면 실제 적용 시 불필요한 자원 낭비를 방지하고 프로그램 실행 효율성을 높일 수 있습니다. 🎜

위 내용은 골랭 스택 구현의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!