Golang 实现队列数据结构

在这个Golang程序中，队列是一种基于先进先出（FIFO）原则工作的数据结构，元素从队列的尾部添加，从队列的前部移除。尽管Go语言没有内置的队列数据结构，但可以使用切片、链表和其他数据结构来构建一个队列。我们将使用两种方法来使用切片和链表实现队列数据结构。

方法1：使用切片方法

在这个实现中，队列数据结构的基本操作：入队、出队和判空，都是使用切片来实现的。

步骤

步骤1 －创建一个package main，并在程序中声明fmt（输入输出格式化的包）包，其中main用于生成可执行的代码，fmt用于格式化输入和输出。
步骤2 －创建一个名为q.item_value的空切片，用于存储队列的元素。
步骤3 －在入队操作中，使用append函数将元素添加到q.item_value切片的末尾。
步骤4 －在出队操作中，使用索引从q.item_value切片中提取第一个元素，并将其放入变量中，以从队列的前部删除元素。然后，通过对q.item_value切片从第二个元素开始进行切片，来删除第一个元素。返回被提取的元素。
步骤5 －实现IsEmpty函数，用于判断队列是否为空，只需判断q.item_value的长度是否为0。
步骤6 －这个示例展示了如何在Go语言中使用基本的队列数据结构，入队和出队元素，并验证队列是否为空。

示例

在这个示例中，我们将使用切片来实现队列数据结构。让我们看一下如何执行这个程序。

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：使用链表

在这种方法中，队列的元素保存在一个链表中。链表的每个节点中都包含一个值和指向下一个节点的指针。头指针表示队列的前端，尾指针表示队列的后端。通过修改现有尾节点的next指针和尾指针来指向新节点，入队操作将新节点添加到链表的末尾。通过将头指针改为指向下一个节点，出队操作可从链表中移除前端节点。Size操作返回队列的总条目数。

步骤

步骤1 - 在程序中创建一个main包，并声明fmt（格式化包）包，其中main生成可执行代码，fmt用于格式化输入和输出。
步骤2 - 使用一个变量size初始化队列数据结构，用于跟踪队列的元素数量，并使用head和tail的指针来指向链表的头和尾。
步骤3 - 将新节点的next指针设置为nil，并使用指定的值创建新节点。
步骤4 - 如果队列为空，则将头指针和尾指针更新为新节点。
步骤5 - 否则，将尾指针和当前尾节点的next指针更新为新节点。将size变量加1。
步骤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)
      }
   }
}