在go语言中数据结构之队列链表实现示例代码

Go  /  管理员 发布于 2年前   373

数据结构-队列描述：遵循先进先出原则的线性表，其插入与删除操作分别在表的两端进行，

进行插入操作的是队尾 (back/rear)，删除操作的是队首 (front)。

队列链表实现代码示例：

基于单链表实现同样要区分一下哪里是队列头，哪里是队列尾

首先我们需要两个指针，front 与 back 分别指向头与尾

如果是插入操作的话，无论哪一端是队尾都是很简单的

如果头节点是队尾：

queue= &node{
    Val:val,
    Next:head,
}

如果链表结尾是队尾：

back.Next :=  &node{
Val:val,
Next:nil,
}
back = back.Next

可见他们都是 O (1) 操作，但是删除操作就不一样了。

假设是头节点为队尾，那么删除操作需要先遍历到队尾前一个节点，随后断开链。

而链尾是队尾的情况只需要让 front = front.Next 就可以轻松断开

所以我们定义这个链表实现的队列，头节点处为队首，尾节点处为队尾

type  LinkedQueue  struct {
 // 指向链首
    QueueFront *chainNode
    QueueBack  *chainNode
    QueueSize  int
}

type  chainNode  struct {
    Val  interface{}
    Next *chainNode
}

func (q *LinkedQueue) Empty() bool {
 /*
        if q.QueueBack == q.QueueBack && q.QueueFront == nil {
            return true
        }
        return false
    */
 return q.QueueSize == 0
}

func (q *LinkedQueue) Size() int {
 return q.QueueSize
}

func (q *LinkedQueue) Front() (interface{}, bool) {
 if q.Empty() {
 return  nil, false
    }
 return q.QueueFront.Val, true
}

func (q *LinkedQueue) Back() (interface{}, bool) {
 if q.Empty() {
 return  nil, false
    }
 return q.QueueBack.Val, true
}

func (q *LinkedQueue) Pop() (interface{}, bool) {
 if q.Empty() {
 return  nil, false
    }
 val := q.QueueFront.Val
 q.QueueFront = q.QueueFront.Next
    q.QueueSize--
 return val, true
}

func (q *LinkedQueue) Push(val interface{}) bool {
 node := &chainNode{
        Val: val,
    }
 if q.Empty() {
 q.QueueFront = node
} else {
 q.QueueBack.Next = node
    }
 q.QueueBack = node
    q.QueueSize++
 return  true
}