Detailed implementation of Queue data structure in Golang

preface

This article mainly introduces to you about the Golang data structure Queue implementation related content, sharing for your reference and learning, the following words do not say much, let's have a look at the detailed introduction.

demand

The characteristics of queues are relatively single 1. The basic operations are initialization, size acquisition, element addition, element removal and so on. The most important feature is first in, first out.

implementation

Next, follow the previous routine, step by step, to analyze how to implement the data structure of Queue using the syntax features of Go.

define

Each node Node structure is defined first. As usual, the value type of Value can be any type, and the pointer type of the front and back pointer fields of the node is node

type node struct {
 value interface{}
 prev *node
 next *node
}

Continue to define the linked list structure, define Pointers to head and tail nodes, and define the queue size size:

type LinkedQueue struct {
 head *node
 tail *node
 size int
}

The size of the

To get the queue size, just get the size size in LinkedQueue:

func (queue *LinkedQueue) Size() int {
 return queue.size
}

Peek

The Peek operation simply fetches the element of the queue header without deleting it. The return type is arbitrary and can be implemented using an interface. In addition, if the pointer field of head is nil, an exception needs to be thrown with panic. If 1 cut ok, the value of the header node can be returned:

func (queue *LinkedQueue) Peek() interface{} {
 if queue.head == nil {
 panic("Empty queue.")
 }
 return queue.head.value
}

add

In order not to waste memory, the pointer variable of the newly added node should be set to nil:

func (queue *LinkedQueue) Add(value interface{}) {
 new_node := &node{value, queue.tail, nil}
 if queue.tail == nil {
 queue.head = new_node
 queue.tail = new_node
 } else {
 queue.tail.next = new_node
 queue.tail = new_node
 }
 queue.size++
 new_node = nil
}

remove

The delete operation of the queue is also very simple, nothing more than the disconnection operation of the node. Before we do that, we need to determine the state of the list, is it nil? For the node at the front of the queue that is removed, save the node at the front of the queue with a new variable node first, and after 1 series of operations, reach nil and reduce the length.

func (queue *LinkedQueue) Remove() {
 if queue.head == nil {
 panic("Empty queue.")
 }
 first_node := queue.head
 queue.head = first_node.next
 first_node.next = nil
 first_node.value = nil
 queue.size--
 first_node = nil
}

Ok, that's how you implement Queue with the basic syntax features of Go. Thanks for reading!!

conclusion