손 으로 golang 기본 데이터 구조 와 알고리즘 스 택 을 훑 습 니 다.
7694 단어 알고리즘 데이터 구조 golang 스 택
발단
최근 에 < > ([일] 석 다 보 휘, 미 야자 키 수 일) 시 리 즈 를 읽 고 골 랑 으로 연습 할 예정 입 니 다.
창고.
( ) ,
,
。
,
,
。
,
“ ” ,
Last In First Out, LIFO。
<>(【 】 ; )
목표.
설계 하 다.
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)