栈(stack)在计算机科学中是限定仅在表尾进行插入或删除操作的线性表。栈是一种数据结构,它按照后进先出的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据。栈是只能在某一端插入和删除的特殊线性表。用桶堆积物品,先堆进来的压在底下,随后一件一件往上堆。取走时,只能从上面一件一件取。读和取都在顶部进行,底部一般是不动的。栈就是一种类似桶堆积物品的数据结构,进行删除和插入的一端称栈顶,另一端称栈底。插入一般称为进栈,删除则称为退栈。 栈也称为后进先出表

实现

在内部,堆栈将用一个slice类型表示,我将公开如下方法

  • Push()
  • Pop()
  • New()

New() 用作构造函数,在我们开始使用它时初始化内部切片。

我将创建一个Stack通用类型,并发安全,可以生成包含任何类型的堆栈,创建特定于类型的堆栈实现,封装包含数据的实际值特定数据结构。

// 队列中Item的类型
type Type interface{}

// 队列中的Item
type Item Type
import "sync"

type Stack struct {
    items []Item
    lock  sync.RWMutex
}

//创建一个安全的Stack(后进先出)
func (s *Stack) New() *Stack {
    s.items = []Item{}
    return s
}

//入栈
func (s *Stack) Push(item Item) {
    s.lock.Lock()
    s.items = append(s.items, item)
    s.lock.Unlock()
}

//出栈
func (s *Stack) Pop() *Item {
    s.lock.Lock()
    item := s.items[len(s.items)-1]
    s.items = s.items[0 : len(s.items)-1]
    s.lock.Unlock()
    return &item
}

测试

测试上面公开的方法

import (
    "testing"
)

var stack Stack

func initStack() *Stack {
    if stack.items == nil {
        stack = Stack{}
        stack.New()
    }
    return &stack
}

func TestPush(t *testing.T) {
    s := initStack()
    s.Push(1)
    s.Push(2)
    s.Push(3)
    if size := len(s.items); size != 3 {
        t.Errorf("wrong count, expected 3 and got %d", size)
    }
}

func TestPop(t *testing.T) {
    stack.Pop()
    if size := len(stack.items); size != 2 {
        t.Errorf("wrong count, expected 2 and got %d", size)
    }

    stack.Pop()
    stack.Pop()
    if size := len(stack.items); size != 0 {
        t.Errorf("wrong count, expected 0 and got %d", size)
    }
}