算法：golang使用切片实现栈(切片使用技巧)

曾经终败给现在 2022-09-08 13:00 272阅读 0赞

# 注意 #

*  切片的头部插入一个元素

slice := []int{
        1, 2, 3, 4};
    
    	value := -1
    	slice = append([]int{
        value}, slice...)

*  切片的尾部插入一个元素

slice := []int{
        1, 2, 3, 4};
    
    	value := -1
    	slice = append(slice, value)

> `make([]interface{}, 0)`和`make([]interface{}, 10)`的区别，这个对`s.values = append(s.values, item)`有很大的影响

*  删除第一个元素

slice = slice[1:]

*  删除切片中某个索引的元素：

slice := []int{
        1, 2, 3, 4};
    
    	pos := 2   // 待删除元素的位置
    	slice = append(slice[:pos], slice[pos + 1:]...)

# 版本一 #

stack.go

package main
    
    import "fmt"
    
    type Stack struct {
        
    	values []interface{
        } // 用来存储数据
    	top int // 栈顶元素索引
    	size int  // 栈最多能够存放多少元素，默认不限制
    }
    
    func NewStack() *Stack  {
        
    	return &Stack{
        
    		values: make([]interface{
        }, 0),
    		top:    -1,
    	}
    }
    
    func (s *Stack) SetSize(size int) error {
        
    	if s.top != -1 {
        
    		return fmt.Errorf("[ ERR ] Stack is not empty. To set the size, stack should be empty.")
    	}
    
    	s.size = size
    	return nil
    }
    
    // 放置元素
    func (s *Stack)Push(item interface{
        })  {
        
    	s.values = append(s.values, item)
    	s.top++
    }
    
    
    // 获取栈顶元素但是不删除它
    func (s *Stack)Peek()(interface{
        }, error)  {
        
    	if s.top < 0 {
        
    		return nil, fmt.Errorf("[ERR] Index out of range")
    	}
    
    	item := s.values[s.top]
    
    	return item, nil
    }
    
    // 栈中多少个元素
    func (s *Stack)Size() int  {
        
    	return s.top + 1
    }
    
    // 弹出栈顶元素
    func (s *Stack) Pop()(interface{
        }, error)  {
        
    	if s.top < 0 {
        
    		return nil, fmt.Errorf("[ ERR ] Index out of range")
    	}
    
    	item := s.values[s.top]
    	s.values = append(s.values[:s.top], s.values[s.top + 1:]...)
    	s.top--
    	return item, nil
    }

stack\_test.go

package main
    
    import "testing"
    
    func TestStackPushAndPop(t *testing.T) {
        
    	s := NewStack()
    	s.Push("test_1")
    
    	if v, err := s.Pop(); err == nil {
        
    		if "test_1" != v && s.top == 0 {
        
    			t.Errorf("Failed to Pop")
    		}
    	} else {
        
    		t.Errorf("Failed to Pop")
    	}
    
    	if s.top != -1 {
        
    		t.Errorf("The top should be -1. Instead: %d", s.top)
    	}
    
    	s.Push("test_2")
    	s.Push("test_3")
    
    	if s.top != 1 {
        
    		t.Errorf("The top should be 1. Instead: %d", s.top)
    	}
    
    	if v, err := s.Pop(); err == nil {
        
    		if "test_3" != v && s.top == 1 {
        
    			t.Errorf("Failed to Pop")
    		}
    	} else {
        
    		t.Errorf("Failed to Pop")
    	}
    }
    
    func TestStackSize(t *testing.T) {
        
    	s := NewStack()
    
    	if s.Size() != 0 {
        
    		t.Errorf("The size of the stack should be 0. Instead %d", s.Size())
    	}
    
    	s.Push("Test")
    	s.Push("Test_2")
    	s.Push("Test_3")
    
    	if s.Size() != 3 {
        
    		t.Errorf("The size of the stack should be 3. Instead %d", s.Size())
    	}
    }

# 版本二 #

package main
    
    import (
    	"fmt"
    	"sync"
    )
    
    var errEmptyStack = fmt.Errorf("[ERR], stack is empty\n")
    
    type Stack struct {
        
    	stack []interface{
        }
    	len   int
    	lock  sync.Mutex
    }
    
    func NewStack()*Stack  {
        
    	return &Stack{
        
    		stack: make([]interface{
        }, 0),
    		len:   0,
    		lock:  sync.Mutex{
        },
    	}
    }
    
    
    // 数组头部插入
    func (s *Stack)Push(v interface{
        })  {
        
    	s.lock.Lock()
    	defer s.lock.Unlock()
    
    	s.stack = append([]interface{
        }{
        v}, s.stack...) // ...是必须的
    	s.len++
    }
    
    func (s *Stack) Peek() (interface{
        }, error)  {
        
    	s.lock.Lock()
    	defer  s.lock.Unlock()
    
    	if s.len == 0 {
        
    		return nil, errEmptyStack
    	}
    
    
    	return s.stack[0], nil
    }
    
    func (s *Stack)Pop()  (interface{
        }, error)  {
        
    	s.lock.Lock()
    	defer  s.lock.Unlock()
    
    	if s.len == 0 {
        
    		return nil, errEmptyStack
    	}
    
    	var item interface{
        }
    	item, s.stack = s.stack[0], s.stack[1:]
    	s.len--
    	return item, nil
    }
    
    func (s *Stack)Len() int{
        
    	s.lock.Lock()
    	defer  s.lock.Unlock()
    
    	return s.len
    }
    
    
    func (s *Stack)Empty() bool{
        
    	return s.len == 0
    }

测试

package main
    
    import (
    	"fmt"
    	"testing"
    )
    func TestNew(t *testing.T) {
        
    	s := NewStack()
    
    	if !s.Empty() || s.len != 0 ||  s.Len() != 0 {
        
    		t.Error()
    	}
    
    	s.Push(1)
    	s.Push(2)
    	s.Push(3)
    
    	if s.stack[0] != 3 ||
    		s.stack[1] != 2 ||
    		s.stack[2] != 1 {
        
    		fmt.Println(s.stack)
    		t.Error()
    	}
    
    	if s.Len() != 3 {
        
    		t.Error()
    	}
    
    	a, _ := s.Pop()
    
    	if a != 3 || s.Len() != 2 {
        
    		t.Error()
    	}
    
    	b, _ := s.Peek()
    
    	if b != 2 {
        
    		t.Error()
    	}
    }

# 版本三 #

package main
    
    import (
    	"fmt"
    )
    
    
    
    type StackArray interface {
        
    	Push(v interface{
        }) error
    	Peek() (interface{
        }, error)
    	Pop()(interface{
        }, error)
    	Get() []interface{
        }
    	Size() int
    	IsEmpty() bool
    	Clear()
    	IsFull() bool //是否满了
    }
    
    
    type Stack struct {
        
    	values []interface{
        } // 用来存储数据
    	top int // 栈顶元素索引
    	capacity int  // 栈最多能够存放多少元素，默认不限制
    }
    
    func NewStack() *Stack{
        
    	return &Stack{
        
    		values: make([]interface{
        }, 0),
    		top: -1,
    		capacity: -1,
    	}
    }
    
    func NewStackSize(capacity int) *Stack  {
        
    	return &Stack{
        
    		values: make([]interface{
        }, capacity),
    		top:    -1,
    		capacity:   capacity,
    	}
    }
    
    func (s *Stack) SetSize(capacity int) error  {
        
    	if capacity < 0 {
        
    		return fmt.Errorf("capacity must > -1");
    	}
    
    	s.capacity = capacity
    	if capacity < s.Size() {
        
    		s.values = s.values[:capacity]
    		s.top = capacity - 1
    	}
    
    
    	return nil
    }
    
    
    
    func (s *Stack) IsFull() bool{
        
    	if s.capacity == -1 {
        
    		return false
    	}
    	return s.Size() == s.capacity
    }
    
    func (s *Stack)Clear()  {
        
    	s.top = -1
    	s.values = []interface{
        }{
        }
    }
    
    func (s *Stack) Push(v interface{
        }) error  {
        
    	if s.IsFull()  {
        
    		return fmt.Errorf("[ERR] Stack full");
    	}
    
    	//s.values = append(s.values, v)   --- error  []
    	s.values[s.top + 1] = v
    	s.top++;
    
    	return nil
    }
    
    func (s *Stack) Peek() (interface{
        }, error)  {
        
    	if s.IsEmpty() {
        
    		return nil, fmt.Errorf("[ERR] Stack is empty")
    	}
    
    	item := s.values[s.top]
    
    	return item, nil
    }
    
    
    
    func (s *Stack)Pop()(interface{
        }, error)  {
        
    	if s.IsEmpty(){
        
    		return nil, fmt.Errorf("[ERR] Stack is empty")
    	}
    
    	oldValue := s.values[s.top]
    
    	s.values[s.top] = nil
    	//s.values = append(s.values[:s.top], s.values[s.top + 1:]...)
    	s.top--
    
    	return oldValue, nil
    }
    
    func (s *Stack) Size() int  {
        
    	return s.top + 1
    }
    func (s *Stack)Get() []interface{
        }  {
        
    	return s.values[:s.top + 1]
    }
    
    
    
    func (s *Stack) IsEmpty() bool  {
        
    	return s.top == -1
    }
    
    
    func main() {
        
    	//var stack StackArray;
    	var stack *Stack;
    	stack = NewStackSize(12)
    
    	stack.Push(1)
    	stack.Push(2)
    	stack.Push(3)
    	stack.Push(1)
    	stack.Push(2)
    	stack.Push(3)
    	stack.Push(1)
    	stack.Push(2)
    	stack.Push(3)
    	stack.Push(1)
    	stack.Push(2)
    	stack.Push(3)
    
    	//stack.Clear()
    
    	//fmt.Println(stack.IsFull(), "--------" , stack.Size())
    	//
    	//for i := 3; i > 0; i--{
        
    	//	item, _ := stack.Pop()
    	//
    	//	fmt.Println(item)
    	//}
    
    	stack.SetSize(3);
    
    	fmt.Println(stack.Get())
    }