queue

Documentation

Index

• type ArrayQueue
  • func CreateArrayQueue(capacity int) ArrayQueue
  • func CreateArrayQueueDefault() ArrayQueue
  • func (a ArrayQueue) Dequeue() (interface{}, error)
  • func (a ArrayQueue) Enqueue(item interface{})
  • func (a ArrayQueue) GetFront() (interface{}, error)
  • func (a ArrayQueue) GetSize() int
  • func (a ArrayQueue) IsEmpty() bool
  • func (a ArrayQueue) String() string
• type LinkedListQueue
  • func CreateLinkedListQueue() *LinkedListQueue
  • func (queue *LinkedListQueue) Dequeue() (interface{}, error)
  • func (queue *LinkedListQueue) Enqueue(item interface{})
  • func (queue LinkedListQueue) GetFront() (interface{}, error)
  • func (queue LinkedListQueue) GetSize() int
  • func (queue LinkedListQueue) IsEmpty() bool
  • func (queue LinkedListQueue) String() string
• type LoopQueue
  • func CreateLoopQueue(capacity int) *LoopQueue
  • func CreateLoopQueueDefault() *LoopQueue
  • func (l *LoopQueue) Dequeue() (interface{}, error)
  • func (l *LoopQueue) Enqueue(item interface{})
  • func (l *LoopQueue) GetCapacity() int
  • func (l *LoopQueue) GetFront() (interface{}, error)
  • func (l *LoopQueue) GetSize() int
  • func (l *LoopQueue) IsEmpty() bool
  • func (l *LoopQueue) String() string
• type Node
  • func (node Node) GetNext() *Node
  • func (node Node) GetValue() interface{}
  • func (node *Node) SetNext(next *Node)
  • func (node *Node) SetValue(value interface{})
  • func (node Node) String() string
• type PriorityQueue
  • func CreatePriorityQueue(comparator func(thisValue interface{}, compareValue interface{}) int) PriorityQueue
  • func (queue PriorityQueue) Dequeue() (interface{}, error)
  • func (queue PriorityQueue) Enqueue(item interface{})
  • func (queue PriorityQueue) GetFront() (interface{}, error)
  • func (queue PriorityQueue) GetSize() int
  • func (queue PriorityQueue) IsEmpty() bool
• type Queue

Types

type ArrayQueue

type ArrayQueue struct {
	// contains filtered or unexported fields
}

数组实现的队列,由于ArrayQueue是基于slice实现的,并不是真正的动态数组．所以其算法渐进时间复杂度并不高． 在出队和入队操作量不是很大的时候性能甚至高于LoopQueue 在出队和入队操作量很大的时候,LoopQueue性能更高一些但相差不多，并不是量级的差异

func CreateArrayQueue

func CreateArrayQueue(capacity int) ArrayQueue

创建一个指定容量的队列

func CreateArrayQueueDefault

func CreateArrayQueueDefault() ArrayQueue

创建一个默认容量的队列

func (ArrayQueue) Dequeue

func (a ArrayQueue) Dequeue() (interface{}, error)

~=O(1) 队首元素出队

func (ArrayQueue) Enqueue

func (a ArrayQueue) Enqueue(item interface{})

~=O(1) 队尾添加元素

func (ArrayQueue) GetFront

func (a ArrayQueue) GetFront() (interface{}, error)

查看队首元素

func (ArrayQueue) GetSize

func (a ArrayQueue) GetSize() int

获取队列大小

func (ArrayQueue) IsEmpty

func (a ArrayQueue) IsEmpty() bool

获取队列是否为空

func (ArrayQueue) String

func (a ArrayQueue) String() string

type LinkedListQueue

type LinkedListQueue struct {
	// contains filtered or unexported fields
}

基于链表实现的队列

func CreateLinkedListQueue

func CreateLinkedListQueue() *LinkedListQueue

创建基于链表的队列

func (*LinkedListQueue) Dequeue

func (queue *LinkedListQueue) Dequeue() (interface{}, error)

O(1)

　 删除队列头部的元素

func (*LinkedListQueue) Enqueue

func (queue *LinkedListQueue) Enqueue(item interface{})

O(1) 队列的尾部添加元素

func (LinkedListQueue) GetFront

func (queue LinkedListQueue) GetFront() (interface{}, error)

查看队首元素

func (LinkedListQueue) GetSize

func (queue LinkedListQueue) GetSize() int

获取队列大小

func (LinkedListQueue) IsEmpty

func (queue LinkedListQueue) IsEmpty() bool

获取队列是否为空

func (LinkedListQueue) String

func (queue LinkedListQueue) String() string

type LoopQueue

type LoopQueue struct {
	// contains filtered or unexported fields
}

front->item->item->tail 元素个数为3 item->tail->front-item 元素个数为3 循环队列，循环队列的好处是增加和删除元素的渐进时间复杂度都是O(1)

func CreateLoopQueue

func CreateLoopQueue(capacity int) *LoopQueue

创建指定容量的循环队列

func CreateLoopQueueDefault

func CreateLoopQueueDefault() *LoopQueue

创建一个默认容量的循环队列,默认容量是16

func (*LoopQueue) Dequeue

func (l *LoopQueue) Dequeue() (interface{}, error)

* ~=O(1)

func (*LoopQueue) Enqueue

func (l *LoopQueue) Enqueue(item interface{})

~=O(1) 循环队列的进队操作

func (*LoopQueue) GetCapacity

func (l *LoopQueue) GetCapacity() int

获取循环队列的容量

func (*LoopQueue) GetFront

func (l *LoopQueue) GetFront() (interface{}, error)

func (*LoopQueue) GetSize

func (l *LoopQueue) GetSize() int

循环队列中元素的个数

func (*LoopQueue) IsEmpty

func (l *LoopQueue) IsEmpty() bool

当队首和队尾相等的时候循环队列是空的

func (*LoopQueue) String

func (l *LoopQueue) String() string

type Node

type Node struct {
	// contains filtered or unexported fields
}

链表中的元素

func (Node) GetNext

func (node Node) GetNext() *Node

获取下一个节点

func (Node) GetValue

func (node Node) GetValue() interface{}

获取节点的值

func (*Node) SetNext

func (node *Node) SetNext(next *Node)

设置下一个节点

func (*Node) SetValue

func (node *Node) SetValue(value interface{})

设置节点的值

func (Node) String

func (node Node) String() string

打印node

type PriorityQueue

type PriorityQueue struct {
	// contains filtered or unexported fields
}

func CreatePriorityQueue

func CreatePriorityQueue(comparator func(thisValue interface{}, compareValue interface{}) int) PriorityQueue

创建优先队列

func (PriorityQueue) Dequeue

func (queue PriorityQueue) Dequeue() (interface{}, error)

func (PriorityQueue) Enqueue

func (queue PriorityQueue) Enqueue(item interface{})

func (PriorityQueue) GetFront

func (queue PriorityQueue) GetFront() (interface{}, error)

func (PriorityQueue) GetSize

func (queue PriorityQueue) GetSize() int

func (PriorityQueue) IsEmpty

func (queue PriorityQueue) IsEmpty() bool

type Queue

type Queue interface {
	fmt.Stringer

	/*
		队尾添加元素
	*/
	Enqueue(item interface{})
	/*
		队首元素出队
	*/
	Dequeue() (interface{}, error)
	/*
		查看队首元素
	*/
	GetFront() (interface{}, error)
	/*
		获取队列大小
	*/
	GetSize() int
	/*
		获取队列是否为空
	*/
	IsEmpty() bool
}