栈的链表和切片实现

本篇文章将会使用数据结构中的栈来实现音乐播放器的音乐添加和删除功能，分别使用切片和链表实现它。

1. 音乐播放器的链表实现

1.1 音乐添加

type song struct {
	value interface{}
	next  *song
}

type Stack struct {
	top  *song
	size int
}

func (stack *Stack) add_song(value interface{}) {
	stack.top = &song{value: value, next: stack.top}
	fmt.Printf("the top song is %s\n", stack.top.value)
	stack.size++
}

实现介绍:

• 使用空接口 value 实现任意类型的存储。
• 栈是 LIFO(Last In First Out) 结构，因此定义 top 指针始终指向栈顶，实现音乐的添加和删除。
• 这里将栈顶 top 指针和链表的 next 指针关联，并且取代了头指针，栈底是 next 指针指向 nil 的元素。

1.2 音乐删除

func (stack *Stack) delete_song() {
	if stack.top.next != nil {
		stack.top = stack.top.next
		fmt.Printf("the top song is %s\n", stack.top.value)
		stack.size--
	} else {
		stack.size = 0
		fmt.Printf("it‘s an empty playlist\n")
	}
}

2. 音乐播放器的切片实现

2.1 音乐添加

type ItemType interface{}

type Stack_Slice struct {
	song   []ItemType
	rwLock sync.RWMutex
}

func (stack *Stack_Slice) add_song_slice(value interface{}) {
	stack.rwLock.Lock()
	stack.song = append(stack.song, value)
	stack.rwLock.Unlock()
}

实现介绍:

• 使用空接口实现切片对任何类型的存储。
• 使用读写锁防止切片数据的修改。
• 音乐添加实际做的是切片的 append 操作。

2.2 音乐删除

func (stack *Stack_Slice) delete_song_slice() {
	if len(stack.song) != 0 {
		stack.rwLock.Lock()
		stack.song = stack.song[0 : len(stack.song)-1]
		stack.rwLock.Unlock()
	} else {
		fmt.Printf("It‘s a empty playlist")
	}
}

实现介绍:

• 音乐删除实际上做的是切片的分片操作。

Tips: 栈的链表/切片实现，其复杂度均为 O(1)

栈的链表和切片实现

原文：https://www.cnblogs.com/xingzheanan/p/14644689.html