本文为《Algorithms》读书笔记,做学习记录用,其中代码使用Golang进行实现,并不是原书之中的Java

1. Bag 背包

对于背包原书中并没有做过多的介绍,仅描述为是一种不支持从其中删除元素的集合数据类型,目的就是收集并迭代遍历收集到的元素。

对于Bag这种集合数据类型应该拥有如下API

返回值 接口名 描述
*Bag NewBag() 创建一个空的背包
void Add(item interface{}) 添加一个元素
bool IsEmpty() 是否为空
int Size() 背包中的元素数量

根据以上简单的API接口定义可以很快的实现它:

package collections

type (
	Bag struct {
		destination []interface{}
	}
)

func NewBag() *Bag {
	return &Bag{
		destination: make([]interface{}, 0),
	}
}

func (bag *Bag) Add(item interface{}) {
	if item == nil {
		panic("invalid arguments, item is nil")
	}
	bag.destination = append(bag.destination, item)
}

func (bag *Bag) IsEmpty() bool {
	return len(bag.destination) == 0
}

func (bag *Bag) Size() int {
	return len(bag.destination)
}

并且可以简单的为Bag添加一个基于回调函数的迭代器用于遍历元素:

func (bag *Bag) Iterate(callback func(interface{})) {
	for _, v := range bag.destination {
		callback(v)
	}
}

使用方式如下:

func main() {
  bag := NewBag()
  bag.Add("C")
	bag.Add("B")
	bag.Add("Gavin")
	bag.Add("A")
	bag.Iterate(func(item interface{}) {
		fmt.Printf("%s\t", item)
	})
}

2. 链表

在进行实现下压栈和队列之前,先要了解什么是链表。

链表表示了一列元素,我们用Node来表示一个元素节点,每一个元素节点的Next都是下一个元素节点的指针,Item是当前元素节点所表示的实际值;我用一个简单图表示链表是如何将一系列元素进行串联起来的:

linked-list

2.1 在链表头插入节点

假设想在链表头插入一个新的节点,值为New Head First的字符串,我们需要先将原有的first节点指针保存至oldfirst中,再创建一个新的节点,将其指针指向first,并将其的值设置为New Head FirstNext的值设置为oldfirst

package main

type (
  Node struct {
    Item interface{}
    Next *Node
  }
)

func main() {
  first := &Node{}
  // 保存原有first节点的指针
  oldfirst := first
  // 创建新的节点并将first指向新创建的节点
  first = &Node{}
  // 设置值并设置Next为原有的first节点指针
  first.Item = "New Head First"
  first.Next = oldfirst
}

2.2 从链表头删除节点

假设想删除链表头的节点,这个操作非常简单,只需要将first的值修改为first.Next的指针即可完成,一般来说我们需要在删除之后获取到被删除节点的值,我们需要在修改first指针之前先拿到原有first的值。

package main

type (
  Node struct {
    Item interface{}
    Next *Node
  }
)

func main() {
  second := &Node{
    Item: "DEF",
    Next: nil
  }
  first := &Node{
    Item: "ABC",
    Next: second
  }
  firstNodeValue := first.Item
  first = first.Next
}

3. 队列

链表是一种线性的数据结构,常使用链表来进行实现,队列使用先进先出(FIFO)的排程顺序,队列中添加元素和删除元素的操作分别被称为入队(Enqueue)出队(Dequeue),入队只允许在后端进行插入操作,则只允许在前端进行出队操作。

对于Queue这种集合数据类型应该拥有如下API

返回值 接口名 描述
*Queue NewQueue() 创建一个空的队列
void Enqueue(item interface{}) 将一个元素入队
interface{} Dequeue() 将一个元素出队
bool IsEmpty() 是否为空
int Size() 背包中的元素数量

使用链表来实现Queue这种数据结构:

package collections

type (
	Node struct {
		Item interface{}
		Next *Node
	}
	Queue struct {
		first   *Node
		last    *Node
		numNode int
	}
)

func NewQueue() *Queue {
	return &Queue{
		numNode: 0,
	}
}

func newNode(item interface{}, next *Node) *Node {
	return &Node{item, next}
}

func (queue *Queue) Enqueue(item interface{}) {
	if item == nil {
		panic("invalid arguments, item is nil")
	}
	oldLast := queue.last
	queue.last = newNode(item, nil)
	if queue.IsEmpty() {
		queue.first = queue.last
	} else {
		oldLast.Next = queue.last
	}
	queue.numNode++
}

func (queue *Queue) Dequeue() interface{} {
	if queue.IsEmpty() {
		return nil
	}
	item := queue.first.Item
	queue.first = queue.first.Next
	if queue.IsEmpty() {
		queue.last = nil
	}
	queue.numNode--
	return item
}

func (queue *Queue) IsEmpty() bool {
	return queue.first == nil // otherwise queue.numNode == 0
}

func (queue *Queue) Size() int {
	return queue.numNode
}

我们可以为Queue添加一个基于回调函数的迭代器来用于遍历元素并对元素进行操作:

func (queue *Queue) Iterate(callback func(interface{})) {
	current := queue.first
	for current != nil {
		item := current.Item
		current = current.Next
		callback(item)
	}
}

4. 下压栈

待补全