Golang程序 实现队列的数据结构
在这个Golang程序中,队列是一种数据结构,其工作原理是先进先出(FIFO),即元素被添加到后面,然后从前面删除。虽然Go没有内置的队列数据结构,但切片、链接列表和其他数据结构都可以用来建立一个队列。我们将使用两种方法来实现队列数据结构,即使用分片和链表。
方法1:使用Slice法
一个队列数据结构的基本操作。Enqueue、Dequeue和IsEmpty在这个实现中实现,它采用了一个片断来保存队列中的项目
算法
- 第1步 – 创建一个包main,并在程序中声明fmt(format package)包,其中main产生可执行代码,fmt帮助格式化输入和输出。
-
第2步 – 在队列数据结构中创建一个名为q.item_value的空片,用来存放组件。
-
第 3步 – 在enqueue操作中,只需使用append函数将元素追加到q.item_value片中,将其添加到队列的末端。
-
第4步 – 在dequeue操作中,使用索引从q.item_value slice中提取第一个项目,并把它放在一个变量中,以便从队列的前面删除一个元素。然后,为了消除第一个项目,从第二个元素开始对q.item_value slice进行切片。返回被提取的项目。
-
第5步 – 实现函数IsEmpty来确定队列是否为空,只需确定q.item_value的长度是否为0。
-
第6步 – 这个例子展示了如何利用Go中的基本队列数据结构来排队和取消排队元素,以及验证队列是否为空。
例子
在这个例子中,我们将使用slice来实现队列数据结构。让我们看看如何执行。
package main
import "fmt"
type Queue struct {
item_value []int
}
func (q *Queue) Enqueue(item int) {
q.item_value = append(q.item_value, item) //used to add items
}
func (q *Queue) Dequeue() int {
item := q.item_value[0]
q.item_value = q.item_value[1:] //used to remove items
return item
}
func (q *Queue) IsEmpty() bool {
return len(q.item_value) == 0
}
func main() {
fmt.Println("Enqueue and Dequeue the elements:")
q := &Queue{} // create a queue instance which will be used to enqueue and dequeue elements
q.Enqueue(1)
q.Enqueue(2)
q.Enqueue(3)
for !q.IsEmpty() {
fmt.Println(q.Dequeue()) //check whether the queue is empty or not
}
}
输出
Enqueue and Dequeue the elements:
1
2
3
方法2:使用Linked List
在这种方法中,队列的元素被保存在一个链接列表中。在链接列表的每个节点中都包含一个值和一个指向下一个节点的指针。行的前面由头部指针显示,而后面则由尾部指针表示。通过修改现有尾部节点的下一个指针和尾部指针指向新的节点,Enqueue操作将一个新的节点添加到链表的末端。通过改变头部指针指向后续节点,Dequeue操作将前面的节点从链接列表中删除。Size操作返回队列的总条目数。
算法
- 第1步 – 创建一个包main,并在程序中声明fmt(格式包)包,其中main产生可执行代码,fmt帮助格式化输入和输出。
-
第2步– 初始化一个队列数据结构,其大小可变,以记录队列的元素数和指向链表头和尾的指针。
-
第 3步 – 将一个新节点的下一个指针设置为nil,并以指定的值创建它。
-
第4步 – 如果队列是空的,更新新节点的头和尾指针。
-
第5步 – 否则,更新尾部指针和当前尾部节点的下一个指针都指向新节点。给size变量加一。
-
第6步 – 如果队列是空的,返回0和false。如果不是,从size变量中减去1,提取前面节点的值,更新指向下一个节点的头部指针,并返回提取的值和true。
-
第7步 – 使用size操作返回size变量的值。
-
第8步 – 前面的例子展示了如何使用链表在Go中创建一个队列数据结构,以及如何使用它来排队和取消排队的元素,以及获得队列的大小。
例子
在这个例子中,我们将使用链表来实现队列数据结构。让我们看一下代码。
package main
import "fmt"
type Node struct {
value int
next *Node //use of linked list to implements queue
}
type Queue struct {
head *Node
tail *Node
size int
}
//add the elements in the queue
func (qe *Queue) Enqueue(value int) {
newNode := &Node{value: value}
if qe.size == 0 {
qe.head = newNode
qe.tail = newNode
} else {
qe.tail.next = newNode
qe.tail = newNode
}
qe.size++
}
//remove the elements from queue
func (qe *Queue) Dequeue() (int, bool) {
if qe.size == 0 {
return 0, false
}
value := qe.head.value
qe.head = qe.head.next
qe.size--
return value, true
}
//return the size of queue
func (qe *Queue) Size() int {
return qe.size
}
func main() {
qe := &Queue{} //create an instance of queue
qe.Enqueue(1)
qe.Enqueue(2)
qe.Enqueue(3)
fmt.Println("Enqueue and Dequeue the elements:")
for qe.Size() > 0 {
value, success := qe.Dequeue()
if success {
fmt.Println(value)
}
}
}
输出
Enqueue and Dequeue the elements:
1
2
3
结论
我们用两种方法执行了实现队列数据结构的程序。在第一种方法中,我们使用了slice,在第二个例子中,我们使用了lined list来执行该程序。