02 基本数据结构：队列与栈

队列是一种受限的线性表，一般由链表实现（也可以用数组实现，链表队列性能较高），因为它只允许表头进入表尾推出，顺序为先进先出。

• enqueue(element) 向队尾添加一个或多个项
• dequeue(): 移除队列的第一（即趴在队列最前面的）项，并返回被移除的元素
• front()：返回队列中的第一个元素——即最先被添加，也将是最先被移除的元素，队列不做任何变动（不移除元素，只返回元素值）
• isEmpty()：如果队列中不包含任何元素，返回true，否则返回false
• size()：返回队列包含的元素个数，与数组的length类似
• toString()：将队列的内容转成字符串输出

以下为Go代码实现：

type element struct {
	value interface{}
}

type ArrayQueue struct {
	list []element // 内部由数组切片维护
	size int       // 队列长度
	sync.Mutex     // 锁
}

func NewArrayQueue(n int) *ArrayQueue {
	queue := new(ArrayQueue)
	list := make([]element, 0, n)
	queue.list = list
	queue.size = n
	return queue
}

// 队列管理：进队,从0号开始追加
func (q *ArrayQueue) Enqueue(items ...interface{}) bool {
	q.Lock()
	for _, item := range items {
		if len(q.list) < q.size {
			q.list = append(q.list, element{item})
		} else {
			q.Unlock()
			return false
		}
	}
	q.Unlock()
	return true
}

// 队列管理：出队,从0号位开始弹出，并移位后续元素
func (q *ArrayQueue) Dequeue() interface{} {
	q.Lock()
	e := q.list[0]
	l := len(q.list)
	for i := 0; i < l-1; i++ {
		q.list[i] = q.list[i+1]
	}

	q.Unlock()
	return e.value
}

// 获取队头
func (q *ArrayQueue) Front() interface{} {
	return q.list[0]
}

func (q *ArrayQueue) IsEmpty() bool {
	return len(q.list) == 0
}

func (q *ArrayQueue) Size() int {
	return len(q.list)
}

func (q *ArrayQueue) ToString() string {

	return fmt.Sprintf("len:%d,cap:%d,Print:%v", len(q.list), cap(q.list), q.list)
}

以下为Go代码实现

/*
以链表实现队列，从链表头进队，链表尾出队，并提供一些基于链表操作的队列元素管理方法
*/

type LinkQueue struct {
	list *containerList.List // 内部由双向循环链表维护
	size int                 // 队列长度
	sync.Mutex               // 锁
}

func NewLinkQueue(n int) *LinkQueue {
	queue := new(LinkQueue)
	queue.list = containerList.New()
	queue.size = n
	return queue
}

// 队列管理：进队，每次都从链表尾插入
func (q *LinkQueue) Enqueue(items ...interface{}) bool {
	q.Lock()
	for _,item := range items {
		if q.list.Len() < q.size {
			q.list.PushBack(item)
		}else {
			q.Unlock()
			return false
		}
	}
	q.Unlock()
	return true
}

// 队列管理：出队，每次都从链表头移出
func (q *LinkQueue) Dequeue() interface{} {
        if q.Size() == 0 {
		return nil
	}
	q.Lock()
	back := *q.list.Front()
	q.list.Remove(q.list.Front())
	q.Unlock()
	return back.Value
}

// 获取队头，及链表尾部元素
func (q *LinkQueue) Front() interface{} {
	return q.list.Back().Value
}


func (q *LinkQueue) IsEmpty() bool {
	return q.list.Len() == 0
}

func (q *LinkQueue) Size() int {
	return q.list.Len()
}

func (q *LinkQueue) ToString() string {
	var content []interface{}
	next := q.list.Front()
	if next == nil {
		return ""
	}
	content = append(content, next.Value)
	for {
		next = next.Next()
		if next == nil {
			break
		}
		content = append(content, next.Value)
	}
	return fmt.Sprintf("%v", content)
}

栈也是一种受限的线性表，一般用数组实现（也可以用链表实现，性能差不多），因为它只允许表头进入，表头弹出，顺序为先进后出；

• push(element)： 添加一个新元素到栈顶位置
• pop()：移除栈顶元素，同时返回被移除的元素
• peek()：返回栈顶的元素，不对栈做任何修改（不移除栈顶，只返回栈顶值）
• isEmpty()：如果栈里没有任何元素就返回true，否则false
• size()：返回栈的元素个数，这个方法和数组的length类似
• toString()：将栈结构的内容以字符形式返回

// 自定义栈类型，底层为切片数组
type element struct {
	value interface{}
}

type ArrayStack struct {
	list []element
	size int
	sync.Mutex
}

// 栈工厂方法
func NewArrayStack(n int) *ArrayStack {
	stack := new(ArrayStack)
	stack.list = make([]element, 0, n)
	stack.size = n
	return stack
}

// 计算长度；
func (s *ArrayStack) Len() int {
	return len(s.list)
}

// 是否为空
func (s *ArrayStack) isEmpty() bool {
	return len(s.list) == 0
}

// 压栈:追加到切片尾部
func (s *ArrayStack) Push(items ...interface{}) bool {
	s.Lock()
	for _, item := range items {
		if len(s.list) < s.size {
			s.list = append(s.list, element{item})
		}else {
			s.Unlock()
			return false
		}
	}
	s.Unlock()
	return true
}

// 出栈:切片尾部出栈
func (s *ArrayStack) Pop() interface{} {
	l := len(s.list)
	if l == 0 {
		return nil
	}
	s.Lock()
	tail := s.list[l-1]
	s.list = s.list[:l-1]
	s.Unlock()
	return tail.value
}

// 返回栈顶
func (s *ArrayStack) Peek() interface{} {
	len := len(s.list)
	return s.list[len-1].value
}

// 字符串
func (s *ArrayStack) ToString() string {
	return fmt.Sprintf("len:%d,cap:%d,Print:%v",len(s.list),cap(s.list), s.list)
}

// 链式栈
type LinkListStack struct {
	stack *containerList.List // 内部维护一个双向链表
	size  int
	sync.Mutex
}

// 栈工厂方法
func NewLinkListStack(n int) *LinkListStack {
	stack := new(LinkListStack)
	stack.stack = containerList.New()
	stack.size = n
	return stack
}

// 计算长度；
func (l *LinkListStack) Len() int {
	return l.stack.Len()
}

// 计算长度；
func (l *LinkListStack) isEmpty() bool {
	return l.stack.Len() == 0
}

// 压栈：从链表头部进栈
func (l *LinkListStack) Push(items ...interface{}) bool {

	l.Lock()
	for _, item := range items {
		if l.stack.Len() < l.size {
			l.stack.PushFront(item)
		} else {
			l.Unlock()
			return false
		}
	}
	l.Unlock()
	return true
}

// 出栈：从链表头部出栈
func (l *LinkListStack) Pop() interface{} {
	l.Lock()
	front := l.stack.Front()
	popEle := *front
	l.stack.Remove(front)
	l.Unlock()
	return popEle.Value
}

// 返回栈顶
func (l *LinkListStack) Peek() interface{} {
	return l.stack.Front()
}

// 字符串
func (l *LinkListStack) ToString() string {
	var content []interface{}
	next := l.stack.Front()
	if next == nil {
		return ""
	}
	content = append(content, next.Value)
	for {
		next = next.Next()
		if next == nil {
			break
		}
		content = append(content, next.Value)
	}
	return fmt.Sprintf("%v", content)
}