Detailed implementation of Queue data structure in Golang
- 2020-06-07 04:39:35
- OfStack
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