Data structure: Unidirectional Queue

One – way queue, first – in, first – out (last – in, last – out), one of the common data structures. Breadth-first traversal simulates operations based on this data structure.

Brush questions are often used.

Implementation one, based on the GO standard librarycontainer/list

import "container/list"

type Queue struct {
	l *list.List
}

func NewQueue(a) *Queue {
	return &Queue{
		l: list.New(),
	}
}

func (o *Queue) Push(v interface{}) {
	o.l.PushBack(v)
}

func (o *Queue) Pop(a) interface{} {
	if o.IsEmpty() {
		panic("Queue is empty")
	}
	e := o.l.Front()
	o.l.Remove(e)
	return e.Value
}

func (o *Queue) Front(a) interface{} {
	if o.IsEmpty() {
		panic("Queue is empty")}return o.l.Front().Value
}

func (o *Queue) Back(a) interface{} {
	if o.IsEmpty() {
		panic("Queue is empty")}return o.l.Back().Value
}

func (o *Queue) IsEmpty(a) bool {
	return o.l.Len() == 0
}

func (o *Queue) Len(a) int {
	return o.l.Len()
}
Copy the code

Implementation two, based onSingly linked lists

// Import the single linked list package
import "algo/internal/singlylinkedlist"

type Queue struct {
	list *singlylinkedlist.SinglyLinkedList
	size int
}

func NewQueue(a) *Queue {
	return &Queue{
		list: &singlylinkedlist.SinglyLinkedList{},
	}
}

func (o *Queue) Len(a) int {
	return o.size
}

func (o *Queue) IsEmpty(a) bool {
	return o.size == 0
}

func (o *Queue) Push(v interface{}) {
	o.list.AddToTail(v)
	o.size++
}

func (o *Queue) Peek(a) interface{} {
	if o.IsEmpty() {
		panic("Queue is empty")}return o.list.Head().V
}

func (o *Queue) Pop(a) interface{} {
	if o.IsEmpty() {
		panic("Queue is empty")
	}
	node := o.list.Head()
	o.list.RemoveHead()
	o.size--
	return node.V
}
Copy the code

The test code

package main

import "fmt"

func main(a) {
	q := NewQueue()
	for i := 0; i < 9; i++ {
		q.Push(i * 10)}for! q.IsEmpty() { fmt.Println(q.Front(),q.Back(),q.Len(),q.Pop().(int))}}Copy the code