손 으로 golang 기본 데이터 구조 와 알고리즘 스 택 을 훑 습 니 다.

7694 단어 알고리즘 데이터 구조 golang 스 택
손 으로 golang 기본 데이터 구조 와 알고리즘 스 택 을 훑 습 니 다.
발단
최근 에 < > ([일] 석 다 보 휘, 미 야자 키 수 일) 시 리 즈 를 읽 고 골 랑 으로 연습 할 예정 입 니 다.
창고.
 (    )                ，
        ，
             。

       ，
                  ，
                。

                ，
 “    ”   ，
    Last In First Out，  LIFO。

   <>(【 】    ；    )

목표.
  • 배열 을 바탕 으로 하나의 LIFO 스 택
    • 을 실현 한다.
  • 배열 의 초기 용량 크기 를 지정 할 수 있 습 니 다
  • 원소 의 수량 이 용량 을 초과 할 때 자동 으로 2 배율 속도 로 용량 을 확대 한다
  • 복사 면제 교체 기 를 제공 하여 스 택 을 옮 겨 다 니 며 교체 버 전 오류 (Concurrent Modification Error)
    • 를 감지 할 수 있 습 니 다.
    설계 하 다.
  • IStack: 스 택 인터페이스
  • ISTackIterator: 스 택 교체 기의 인터페이스
  • tArray Stack: 자체 확장 배열 의 스 택 을 바탕 으로 ISTack 인터페이스
    • 를 실현 합 니 다.
  • tStackIterator: 복사 면제 스 택 교체 기, ISTackIterator 인터페이스 실현
    • 유닛 테스트
    stack_test.go 
    package data_structure

import (
    st "learning/gooop/data_structure/stack"
    "testing"
)

func Test_Stack(t *testing.T) {
    fnAssertTrue := func(b bool, msg string) {
        if !b {
            panic(msg)
        }
    }

    stack := st.NewArrayStack(2)
    state := stack.String()
    t.Log(state)
    fnAssertTrue(state == "c=2,t=-1,v=0,items:", "state error")

    stack.Push(0)
    state = stack.String()
    t.Log(state)
    fnAssertTrue(state == "c=2,t=0,v=1,items:0", "state error")

    stack.Push(1)
    state = stack.String()
    t.Log(state)
    fnAssertTrue(state == "c=2,t=1,v=2,items:0,1", "state error")

    stack.Push(2)
    state = stack.String()
    t.Log(state)
    fnAssertTrue(state == "c=4,t=2,v=3,items:0,1,2", "state error")

    e,v := stack.Peek()
    fnAssertTrue(e == nil, "expecting e == nil")
    fnAssertTrue(v == 2, "expecting value 2")

    e,v = stack.Pop()
    state = stack.String()
    t.Log(state)
    fnAssertTrue(e == nil, "expecting e == nil")
    fnAssertTrue(v == 2, "expecting value 2")
    fnAssertTrue(state == "c=4,t=1,v=4,items:0,1", "state error")

    e,v = stack.Pop()
    state = stack.String()
    t.Log(state)
    fnAssertTrue(e == nil, "expecting e == nil")
    fnAssertTrue(v == 1, "expecting value 1")
    fnAssertTrue(state == "c=4,t=0,v=5,items:0", "state error")

    e,v = stack.Pop()
    state = stack.String()
    t.Log(state)
    fnAssertTrue(e == nil, "expecting e == nil")
    fnAssertTrue(v == 0, "expecting value 0")
    fnAssertTrue(state == "c=4,t=-1,v=6,items:", "state error")

    e,v = stack.Pop()
    fnAssertTrue(e != nil, "expecting e != nil")

    iter := stack.Iterator()
    fnAssertTrue(iter.More() == false, "expecting More() == false")
    e,v = iter.Next()
    fnAssertTrue(e != nil, "expecting e != nil")

    stack.Push(0)
    state = stack.String()
    t.Log(state)
    fnAssertTrue(state == "c=4,t=0,v=7,items:0", "state error")
    fnAssertTrue(iter.More() == false, "expecting More() == false")
    e,v = iter.Next()
    fnAssertTrue(e != nil, "expecting e != nil")

    stack.Push(1)
    state = stack.String()
    t.Log(state)
    fnAssertTrue(state == "c=4,t=1,v=8,items:0,1", "state error")
    iter = stack.Iterator()
    fnAssertTrue(iter.More() == true, "expecting More() == true")
    e,v = iter.Next()
    fnAssertTrue(e == nil && v  == 0, "expecting v == 0")
    e,v = iter.Next()
    fnAssertTrue(e == nil && v  == 1, "expecting v == 1")
}

    테스트 출력
    $ go test -v stack_test.go 
=== RUN   Test_Stack
    stack_test.go:17: c=2,t=-1,v=0,items:
    stack_test.go:22: c=2,t=0,v=1,items:0
    stack_test.go:27: c=2,t=1,v=2,items:0,1
    stack_test.go:32: c=4,t=2,v=3,items:0,1,2
    stack_test.go:41: c=4,t=1,v=4,items:0,1
    stack_test.go:48: c=4,t=0,v=5,items:0
    stack_test.go:55: c=4,t=-1,v=6,items:
    stack_test.go:70: c=4,t=0,v=7,items:0
    stack_test.go:78: c=4,t=1,v=8,items:0,1
--- PASS: Test_Stack (0.00s)
PASS
ok      command-line-arguments  0.003s

    IStack.go
    스 택 인터페이스
    package stack

type IStack interface {
    Size() int
    IsEmpty() bool
    IsNotEmpty() bool

    Push(value interface{})
    Pop() (error, interface{})
    Peek() (error, interface{})

    Iterator() IStackIterator
    String() string
}

    IStackIterator.go
    스 택 교체 기 인터페이스
    package stack

type IStackIterator interface {
    More() bool
    Next() (error,interface{})
}

    tArrayStack.go
    자체 확장 배열 의 스 택 을 기반 으로 IStack 인 터 페 이 스 를 실현 합 니 다.
    package stack

import (
    "errors"
    "fmt"
    "strings"
)

type tArrayStack struct {
    items []interface{}
    capacity int
    top int
    version int64
}

var gEmptyStackError = errors.New("empty stack")

func NewArrayStack(capacity int) IStack {
    if capacity < 0 {
        capacity = 0
    }

    return &tArrayStack{
        items: make([]interface{}, capacity),
        capacity: capacity,
        top: -1,
    }
}

func (me *tArrayStack) Size() int {
    return me.top + 1
}

func (me *tArrayStack) IsEmpty() bool {
    return me.Size() <= 0
}

func (me *tArrayStack) IsNotEmpty() bool {
    return !me.IsEmpty()
}

func (me *tArrayStack) Push(value interface{}) {
    me.ensureCapacity(me.Size() + 1)
    me.top++
    me.items[me.top] = value
    me.version++
}

func (me *tArrayStack) ensureCapacity(size int) {
    if me.capacity >= size {
        return
    }

    for ;me.capacity= y {
        return x
    }
    return y
}

func (me *tArrayStack) Pop() (error, interface{}) {
    if me.IsEmpty() {
        return gEmptyStackError, nil
    }

    i := me.top
    me.top--
    me.version++
    return nil, me.items[i]
}

func (me *tArrayStack) Peek() (error, interface{}) {
    if me.IsEmpty() {
        return gEmptyStackError, nil
    }

    return nil, me.items[me.top]
}

func (me *tArrayStack) Iterator() IStackIterator {
    return newStackIterator(me)
}

func (me *tArrayStack) String() string {
    itemStrings := make([]string, me.Size())
    for i:=0;i

    tStackIterator.go
    복사 면제 스 택 교체 기, ISTackIterator 인터페이스 구현
    package stack

import "errors"

type tStackIterator struct {
    stack *tArrayStack
    pos int
    version int64
}

var gNullStackError = errors.New("stack is null")
var gNoMoreElementError = errors.New("no more element")
var gConcurrentModificationError = errors.New("concurrent modification error")

func newStackIterator(stack *tArrayStack) IStackIterator {
    return &tStackIterator{
        stack: stack,
        pos: -1,
        version: stack.version,
    }
}

func (me *tStackIterator) More() bool {
    if me.stack == nil {
        return false
    }
    if me.version != me.stack.version {
        return false
    }
    return me.pos < me.stack.top
}

func (me *tStackIterator) Next() (error, interface{}) {
    if me.stack == nil {
        return gNullStackError, nil
    }
    if me.version != me.stack.version {
        return gConcurrentModificationError, nil
    }
    if me.pos >= me.stack.top {
        return gNoMoreElementError, nil
    }

    me.pos++
    return nil, me.stack.items[me.pos]
}

    (end)
    Typescript 기본타입 연습해보기
    【 2 】 데이터 구조의 목록, 목록 함수

    좋은 웹페이지 즐겨찾기

    개발자 우수 사이트 수집

    개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
    best100-homepage