1、栈的测试：
type MyStack struct {
Container [10]int
Pointer int
}
func NewMyStack() *MyStack {
return &MyStack{}
}
func (m *MyStack) Put(item int) error {
if m.Pointer >= 10 {
return errors.New("栈已经满了")
}
m.Container[m.Pointer] = item
m.Pointer++
return nil
}
func (m *MyStack) Get() (int, error) {
if m.Pointer == 0 {
return 0, errors.New("站已经空了")
}
m.Pointer--
return m.Container[m.Pointer], nil
}
func test() {
mystack := NewMyStack()
for i := 0; i < 20; i++ {
err := mystack.Put(i + 5)
if err != nil {
fmt.Println(err)
break
}
}
fmt.Println(mystack)
for i := 0; i < 3; i++ {
_, err := mystack.Get()
if err != nil {
break
}
}
for i := 0; i < 20; i++ {
err := mystack.Put(100 + i)
if err != nil {
fmt.Println(err)
break
}
}
var err error
var item int
for err == nil {
item, err = mystack.Get()
if err != nil {
continue
}
fmt.Println("取出值", item)
}
}
2、队列的实现：
type LouisQueue struct {
Container [3]int
Head int //出队列指针
Tail int // 入队列指针
}
func NewLouisQueue() *LouisQueue {
return &LouisQueue{
Head: 0,
Tail: 0,
}
}
func (l *LouisQueue) IsEmpty() bool {
if l.Head == l.Tail {
return true
}
return false
}
func (l *LouisQueue) IsFull() bool {
return (l.Tail+1)%len(l.Container) == l.Head
}
func (l *LouisQueue) Push(item int) error {
if l.IsFull() {
return errors.New("队列满了")
}
l.Container[l.Tail] = item
l.Tail = (l.Tail + 1) % len(l.Container)
return nil
}
func (l *LouisQueue) Pop() (int, error) {
if l.IsEmpty() {
return 0, errors.New("队列为空")
}
res := l.Container[l.Head]
l.Head = (l.Head + 1) % len(l.Container)
return res, nil
}
func (l *LouisQueue) Size() int {
return (l.Tail + len(l.Container) - l.Head) % len(l.Container)
}
func test() {
myqueue := NewLouisQueue()
for i := 0; i < 3; i++ {
err := myqueue.Push(i + 1)
if err != nil {
fmt.Println(err)
break
}
}
res, err := myqueue.Pop()
if err != nil {
fmt.Println(err)
}
fmt.Println("获取队列的值是:", res)
for i := 0; i < 3; i++ {
err := myqueue.Push(i + 5)
if err != nil {
fmt.Println(err)
break
}
}
fmt.Println(myqueue)
for {
res, err = myqueue.Pop()
if err != nil {
fmt.Println("队列的值已经取完了.....")
break
}
fmt.Println("取得队列的值是:", res)
}
}
3、单量排序链表的实现：
type LinkNode struct {
Item int
Next *LinkNode
}
func NewLinkNode() *LinkNode {
return &LinkNode{}
}
// Size 取有序列表的长度
func (l *LinkNode) Size() int {
linksLen := 0
head := l
for head.Next != nil {
linksLen++
head = head.Next
}
return linksLen
}
// Add 添加节点
func (l *LinkNode) Add(item int) {
node := &LinkNode{}
node.Item = item
if l.Size() == 0 {
l.Next = node
return
}
preNode := l
currentNode := preNode.Next
for currentNode != nil && currentNode.Item < item {
preNode = currentNode
currentNode = currentNode.Next
}
node.Next = currentNode
preNode.Next = node
}
// Remove 删除节点
func (l *LinkNode) Delete(item int) error {
if l.Size() == 0 {
return errors.New("链表长度是0，没有可供删除的节点")
}
preNode := l
currentNode := preNode.Next
for currentNode != nil && currentNode.Item < item {
preNode = currentNode
currentNode = currentNode.Next
}
if currentNode.Item == item {
preNode.Next = currentNode.Next
return nil
}
return errors.New("没有找到指定的节点")
}
// LinkIterator 遍历链表
func (l *LinkNode) LinkIterator() {
if l.Size() == 0 {
fmt.Println("链表长度是0 ，没有课遍历的元素")
return
}
first := l.Next
for first != nil {
fmt.Println(first.Item)
first = first.Next
}
}
func test() {
fmt.Println("开始进行相关的研究 ---只要有一个头节点就能拉出整个链表---有序链表")
newLink := NewLinkNode()
newLink.Add(5)
newLink.Add(4)
newLink.Add(6)
newLink.Add(2)
newLink.Add(1)
newLink.Add(100)
newLink.Add(30)
newLink.Add(6)
newLink.Add(2)
newLink.Add(1)
fmt.Println("链表长度", newLink.Size())
newLink.LinkIterator()
}4、环形单向链表（并顺带解决约瑟夫问题）---公司抽奖程序原型
type CircleNode struct {
Item int
Next *CircleNode
}
func NewCircleNode(item int) *CircleNode {
node := &CircleNode{}
node.Item = item
return node
}
//新增节点
func (c *CircleNode) Add(item int) {
newNode := NewCircleNode(item)
headNode := c
tailNode := c
for tailNode.Next != headNode {
tailNode = tailNode.Next
}
tailNode.Next = newNode
newNode.Next = headNode
}
/*第一个节点创建环形链表*/
func FirstNode(item int) *CircleNode {
node := NewCircleNode(item)
node.Next = node
return node
}
// Delete 删除节点
func (c *CircleNode) Delete(item int) error {
headNode := c
tailNode := c
for tailNode.Next != headNode {
tailNode = tailNode.Next
}
currentNode := headNode
for currentNode.Item != item && currentNode.Next != headNode {
currentNode = currentNode.Next
tailNode = tailNode.Next
/* ==等效前面两行
tailNode=currentNode
currentNode = currentNode.Next
*/
}
if currentNode.Item == item {
tailNode.Next = currentNode.Next
return nil
} else {
return errors.New("没有找到对应的节点")
}
}
//遍历环形链表
func (c *CircleNode) LinkIterator() {
head := c
currentNode := c
for {
fmt.Println(currentNode.Item)
currentNode = currentNode.Next
if currentNode == head {
break
}
}
}
// EscapeGame 约瑟夫问题的解决
func (c *CircleNode) EscapeGame(interval int) {
currentNode := c
tailNode := c
for tailNode.Next != currentNode {
tailNode = tailNode.Next
}
currentIndex := 1
for currentNode.Next != currentNode {
for i := 0; i < interval; i++ {
currentNode = currentNode.Next
tailNode = tailNode.Next
}
fmt.Println(currentIndex, "次:", currentNode.Item)
currentIndex++
//删除当前节点
currentNode = currentNode.Next
tailNode.Next = currentNode
}
fmt.Println(currentIndex, "次:", currentNode.Item)
}
func test() {
myCircleLink := FirstNode(1)
myCircleLink.Add(2)
myCircleLink.Add(3)
myCircleLink.Add(4)
myCircleLink.Add(5)
myCircleLink.Add(6)
myCircleLink.Add(7)
myCircleLink.Add(8)
myCircleLink.Add(9)
myCircleLink.Add(10)
myCircleLink.Add(11)
myCircleLink.Add(12)
myCircleLink.Add(13)
myCircleLink.EscapeGame(5)
}