Go语言-队列

摘要

本文部分内容来源于网络，个人收集整理，请勿传播

数据结构里的队列就是模仿现实中的排队。队列简称FIFO。

队列有两个特点：

• 新来的都排在队尾；
• 最前面的办理业务后离队，后面一个跟上。

https://blog.csdn.net/u010278923/article/details/72582200

接口说明及实现

Init

初始化队列，其实是初始化里面单链表。

func (queue *Queue) Init() {
    lst := new(List)
    (*queue).list = lst

    lst.Init()
}

Enqueue

func (queue *Queue) Enqueue(data Object) bool {
    return (*queue).list.Append(data)
}

Dequeue

func (queue *Queue) Dequeue() Object {
    return (*queue).list.RemoveAt(0)
}

Peek

func (queue *Queue) Peek() Object {
    return (*queue).list.First()
}

GetSize

func (queue *Queue) GetSize() uint64 {
    return (*queue).list.GetSize()
}

container/list

list是一个双向链表。该结构具有链表的所有功能。

type Element struct {
    Value interface{}   //在元素中存储的值
}

基本用法

package main

import (
    "fmt"
    "container/list"
)

func main() {
    // 生成队列
    l := list.New()

    // 入队, 压栈
    l.PushBack(1)
    l.PushBack(2)
    l.PushBack(3)
    l.PushBack(4)

    // 出队
    i1 := l.Front()
    l.Remove(i1)
    fmt.Printf("%d\n", i1.Value)

    // 出栈
    i4 := l.Back()
    l.Remove(i4)
    fmt.Printf("%d\n", i1.Value)
}

用法详解

func (e *Element) Next() *Element  //返回该元素的下一个元素，如果没有下一个元素则返回nil
func (e *Element) Prev() *Element//返回该元素的前一个元素，如果没有前一个元素则返回nil。
type List
func New() *List //返回一个初始化的list
func (l *List) Back() *Element //获取list l的最后一个元素
func (l *List) Front() *Element //获取list l的第一个元素
func (l *List) Init() *List  //list l初始化或者清除list l
func (l *List) InsertAfter(v interface{}, mark *Element) *Element  //在list l中元素mark之后插入一个值为v的元素，并返回该元素，如果mark不是list中元素，则list不改变。
func (l *List) InsertBefore(v interface{}, mark *Element) *Element//在list l中元素mark之前插入一个值为v的元素，并返回该元素，如果mark不是list中元素，则list不改变。
func (l *List) Len() int //获取list l的长度
func (l *List) MoveAfter(e, mark *Element)  //将元素e移动到元素mark之后，如果元素e或者mark不属于list l，或者e==mark，则list l不改变。
func (l *List) MoveBefore(e, mark *Element)//将元素e移动到元素mark之前，如果元素e或者mark不属于list l，或者e==mark，则list l不改变。
func (l *List) MoveToBack(e *Element)//将元素e移动到list l的末尾，如果e不属于list l，则list不改变。
func (l *List) MoveToFront(e *Element)//将元素e移动到list l的首部，如果e不属于list l，则list不改变。
func (l *List) PushBack(v interface{}) *Element//在list l的末尾插入值为v的元素，并返回该元素。
func (l *List) PushBackList(other *List)//在list l的尾部插入另外一个list，其中l和other可以相等。
func (l *List) PushFront(v interface{}) *Element//在list l的首部插入值为v的元素，并返回该元素。
func (l *List) PushFrontList(other *List)//在list l的首部插入另外一个list，其中l和other可以相等。
func (l *List) Remove(e *Element) interface{}//如果元素e属于list l，将其从list中删除，并返回元素e的值。

实际用法示例

package main
 
import (
	"container/list"
	"fmt"
)
 
func main() {
	l := list.New() //创建一个新的list
	for i := 0; i < 5; i++ {
		l.PushBack(i)
	}
	for e := l.Front(); e != nil; e = e.Next() {
		fmt.Print(e.Value) //输出list的值,01234
	}
	fmt.Println("")
	fmt.Println(l.Front().Value) //输出首部元素的值,0
	fmt.Println(l.Back().Value)  //输出尾部元素的值,4
	l.InsertAfter(6, l.Front())  //首部元素之后插入一个值为10的元素
	for e := l.Front(); e != nil; e = e.Next() {
		fmt.Print(e.Value) //输出list的值,061234
	}
	fmt.Println("")
	l.MoveBefore(l.Front().Next(), l.Front()) //首部两个元素位置互换
	for e := l.Front(); e != nil; e = e.Next() {
		fmt.Print(e.Value) //输出list的值,601234
	}
	fmt.Println("")
	l.MoveToFront(l.Back()) //将尾部元素移动到首部
	for e := l.Front(); e != nil; e = e.Next() {
		fmt.Print(e.Value) //输出list的值,460123
	}
	fmt.Println("")
	l2 := list.New()
	l2.PushBackList(l) //将l中元素放在l2的末尾
	for e := l2.Front(); e != nil; e = e.Next() {
		fmt.Print(e.Value) //输出l2的值,460123
	}
	fmt.Println("")
	l.Init()           //清空l
	fmt.Print(l.Len()) //0
	for e := l.Front(); e != nil; e = e.Next() {
		fmt.Print(e.Value) //输出list的值,无内容
	}
}


func my() {
    l := list.New()
    l.PushBack(path)

    var result []string
    for l.Len() > 0 {
        i1 := l.Front()
        l.Remove(i1)
        value, ok := i1.Value.(string)
        if !ok {
            fmt.Println("It's not ok for type string")
            continue
        }
        ret, e := d.SDK.Bucket(d.Bucket).Prefix(value).Delimiter(delimiter).HasCommonPrefix(true).ListObject()
        if e != nil {
            fmt.Printf("ListObject %v [%s]<%s> failed, %v", d.Bucket, prefix, delimiter, e)
        }

        for _, dir := range ret.CommonPrefixes {
            if strings.HasSuffix(dir, "/") {
                dir = strings.TrimSuffix(dir, "/")
            }
            result = append(result, dir)
            l.PushBack(dir+"/")
        }

        for _, file := range ret.Contents {
            result = append(result, file.Key)
        }
    }
}

Stack

package algorithm

import (	
	"errors"
	"fmt"
)


type Stack struct {
	Element []interface{} //Element
}

func NewStack() *Stack {
	return &Stack{}
}

func (stack *Stack)Push(value ...interface{}){
	stack.Element = append(stack.Element,value...)	
}

//返回下一个元素
func (stack *Stack)Top()(value interface{}){
	if stack.Size() > 0 {
		return stack.Element[stack.Size() - 1]
	}
	return nil //read empty stack
}

//返回下一个元素,并从Stack移除元素
func (stack *Stack)Pop()(err error){
	if stack.Size()> 0 {
		stack.Element = stack.Element[:stack.Size() - 1]
		return nil
	}
	return errors.New("Stack为空.") //read empty stack
}

//交换值
func (stack *Stack)Swap(other *Stack){ 
	switch{
	case stack.Size() == 0 && other.Size() == 0:
		return 		
	case other.Size() == 0 :
		other.Element = stack.Element[:stack.Size()]
		stack.Element = nil
	case stack.Size()== 0 :
		stack.Element = other.Element
		other.Element = nil
	default:
		stack.Element,other.Element = other.Element,stack.Element
	}
	return 	
}

//修改指定索引的元素
func (stack *Stack)Set(idx int,value interface{})(err error){
	if idx >= 0 && stack.Size() > 0 && stack.Size() > idx{
		stack.Element[idx] = value
		return nil
	}
	return errors.New("Set失败!")
}

//返回指定索引的元素
func (stack *Stack)Get(idx int)(value interface{}){
	if idx >= 0 && stack.Size() > 0 && stack.Size() > idx {
		return stack.Element[idx]
	}
	return nil //read empty stack
}

//Stack的size
func (stack *Stack)Size()(int){	
	return len(stack.Element)
}

//是否为空
func (stack *Stack)Empty()(bool){
	if stack.Element == nil || stack.Size() == 0 {
		return true
	}
	return false
}	

//打印
func (stack *Stack)Print(){
	for i := len(stack.Element) - 1; i >= 0; i--{	
		fmt.Println(i,"=>",stack.Element[i])
	}
}

测试

package main
 

import (
	"fmt"
	"github.com/xcltapestry/xclpkg/algorithm"  
)
 
func main(){
 
	stack := algorithm.NewStack()
	if stack.Empty() {
		fmt.Println("Stack为空! ")
	}else{
		fmt.Println("Stack不为空! ",stack.Size())
	}
 
	stack.Push(10)
	stack.Push(20)
	stack.Push(30)
	stack.Push(40)
	fmt.Println("当前Size() = ",stack.Size())
	stack.Print()
 
	fmt.Println("当前Top() = ",stack.Top())
 
	stack.Pop()
	fmt.Println("执行完Pop()后的Top() = ",stack.Top())
	stack.Print()
 
	
	stack.Set(2,900)
	fmt.Println("\n执行完Set(2,900)后的Stack")
 	stack.Print()
 
	fmt.Println("\nGet()查看指定的元素: ")
	fmt.Println("当前idx为1的元素 = ",stack.Get(1))
	fmt.Println("当前idx为2的元素 = ",stack.Get(2))
 
	stack2 := algorithm.NewStack()
	stack2.Push("111")
	stack2.Push("222")
	fmt.Println("\nstack2的初始内容:")
	stack2.Print()
 
	stack.Swap(stack2)	
	fmt.Println("Swap()后stack的内容:")
	stack.Print()
	fmt.Println("Swap()后stack2的内容:")
	stack2.Print()
 
 
	fmt.Println("\nstack增加字符串元素: ")
	stack.Push("中文元素")
	stack.Push("elem1")	
	stack.Print()
}