• 文心一言 VS 讯飞星火 VS chatgpt （107）-- 算法导论10.1 5题

    五、用go语言，栈插入和删除元素只能在同一端进行，队列的插入操作和删除操作分别在两端进行，与它们不同的，有一种双端队列(deque)，其插入和删除操作都可以在两端进行。写出4个时间均为 O(1)的过程，分别实现在双端队列的两端插入和删除元素的操作，该队列是用一个数组实现的。

    文心一言：

    在 Go 语言中，我们可以使用切片（slice）来实现双端队列（deque）。这是因为切片可以在 O(1) 时间内进行头部和尾部的插入和删除操作。

    以下是实现的代码：

    package main  
  
import "fmt"  
  
type Deque struct {  
    elements []int  
}  
  
// 创建一个新的双端队列  
func NewDeque() *Deque {  
    return &Deque{}  
}  
  
// 在队列的头部插入一个元素  
func (d *Deque) InsertFront(value int) {  
    d.elements = append([]int{value}, d.elements...)  
}  
  
// 在队列的尾部插入一个元素  
func (d *Deque) InsertBack(value int) {  
    d.elements = append(d.elements, value)  
}  
  
// 从队列的头部删除一个元素  
func (d *Deque) RemoveFront() {  
    if len(d.elements) > 0 {  
        d.elements = d.elements[1:]  
    }  
}  
  
// 从队列的尾部删除一个元素  
func (d *Deque) RemoveBack() {  
    if len(d.elements) > 0 {  
        d.elements = d.elements[:len(d.elements)-1]  
    }  
}  
  
func main() {  
    deque := NewDeque()  
    deque.InsertBack(1)  
    deque.InsertBack(2)  
    deque.InsertFront(0)  
    fmt.Println(deque.elements) // Output: [0 1 2]  
    deque.RemoveBack()  
    fmt.Println(deque.elements) // Output: [0 1]  
    deque.RemoveFront()  
    fmt.Println(deque.elements) // Output: [1]  
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48

    在这个实现中，InsertFront 和 InsertBack 方法分别在双端队列的头部和尾部插入一个元素，而 RemoveFront 和 RemoveBack 方法则分别从双端队列的头部和尾部删除一个元素。所有这些操作的时间复杂度都是 O(1)。

    在这里插入图片描述

    在这里插入图片描述

    讯飞星火：

    以下是使用Go语言实现的双端队列（deque）的四个时间复杂度为O(1)的操作：

    package main

import "fmt"

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

type Deque struct {
    head *Node
    tail *Node
}

// 在队列头部插入元素
func (dq *Deque) PushFront(value interface{}) {
    newNode := &Node{value: value}
    if dq.head == nil {
        dq.head = newNode
        dq.tail = newNode
    } else {
        newNode.next = dq.head
        dq.head.prev = newNode
        dq.head = newNode
    }
}

// 在队列尾部插入元素
func (dq *Deque) PushBack(value interface{}) {
    newNode := &Node{value: value}
    if dq.tail == nil {
        dq.head = newNode
        dq.tail = newNode
    } else {
        newNode.prev = dq.tail
        dq.tail.next = newNode
        dq.tail = newNode
    }
}

// 从队列头部删除元素
func (dq *Deque) PopFront() interface{} {
    if dq.head == nil {
        return nil
    }
    value := dq.head.value
    dq.head = dq.head.next
    if dq.head != nil {
        dq.head.prev = nil
    } else {
        dq.tail = nil
    }
    return value
}

// 从队列尾部删除元素
func (dq *Deque) PopBack() interface{} {
    if dq.tail == nil {
        return nil
    }
    value := dq.tail.value
    dq.tail = dq.tail.prev
    if dq.tail != nil {
        dq.tail.next = nil
    } else {
        dq.head = nil
    }
    return value
}

func main() {
    dq := &Deque{}
    dq.PushFront(1)
    dq.PushBack(2)
    fmt.Println(dq.PopFront()) // 输出：2
    fmt.Println(dq.PopBack())  // 输出：1
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78

    以上代码实现了一个双端队列（deque），其中PushFront方法用于在队列头部插入元素，PushBack方法用于在队列尾部插入元素，PopFront方法用于从队列头部删除元素，PopBack方法用于从队列尾部删除元素。这些操作的时间复杂度均为O(1)。

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    360智脑：

    以下是在双端队列的两端插入和删除元素的时间均为 O(1) 的过程:

    1. 在队列的一端插入元素:
    func insertFront(q *Deque, x interface{}) {
    n := q.Front.Value.(int)
    if n == 0 {
        q.Front = q.Back
        q.Back = &Node{Value: make([]byte, 1)}
    } else if n == 1 {
        q.Front.Value = &Node{Value: make([]byte, 1)}
    } else {
        q.Front.Value.(*Node).Value = x
        q.Front = &Node{Value: make([]byte, 1)}
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    1. 在队列的另一端插入元素:
    func insertRear(q *Deque, x interface{}) {
    n := q.Back.Value.(int)
    if n == 0 {
        q.Front = q.Back
        q.Back = &Node{Value: make([]byte, 1)}
    } else if n == 1 {
        q.Back.Value = &Node{Value: make([]byte, 1)}
    } else {
        q.Back.Value.(*Node).Value = x
        q.Back = &Node{Value: make([]byte, 1)}
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    1. 从队列的一端删除元素:
    func removeFront(q *Deque, x interface{}) {
    n := q.Front.Value.(int)
    if n == 0 {
        q.Front = q.Back
        q.Back = &Node{Value: make([]byte, 1)}
    } else if n == 1 {
        q.Front.Value = &Node{Value: make([]byte, 1)}
    } else {
        q.Front.Value.(*Node).Value = nil
        q.Front = &Node{Value: make([]byte, 1)}
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    1. 从队列的另一端删除元素:
    func removeRear(q *Deque, x interface{}) {
    n := q.Back.Value.(int)
    if n == 0 {
        q.Front = q.Back
        q.Back = &Node{Value: make([]byte, 1)}
    } else if n == 1 {
        q.Front.Value = &Node{Value: make([]byte, 1)}
    } else {
        q.Back.Value.(*Node).Value = nil
        q.Back = &Node{Value: make([]byte, 1)}
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    智谱清言：

    为了实现双端队列 (deque) 的两端插入和删除操作，我们可以使用一个长度为 2 的数组来实现。其中一个数组用于存储队列的头部，另一个数组用于存储队列的尾部。当头部数组的最后一个位置被占满时，我们需要从头部数组的第一个位置开始存储新的元素。同样，当尾部数组的第一个位置被占满时，我们需要从尾部数组的最后一个位置开始存储新的元素。

    以下是用 Go 语言实现双端队列的两端插入和删除操作的代码：

    package main
import "fmt"
type Deque struct {  
	head [1]int  
	tail [1]int  
	size  int  
}
func (d *Deque) PushFront(value int) {  
	if d.size == 0 {  
		d.head[0] = value  
	} else {  
		d.head[0] = value  
		d.head[1] = d.head[0]  
		d.head[0] = d.head[1]  
		d.head[1] = value  
	}  
	d.size++  
}
func (d *Deque) PushBack(value int) {  
	if d.size == 0 {  
		d.tail[0] = value  
	} else {  
		d.tail[0] = value  
		d.tail[1] = d.tail[0]  
		d.tail[0] = d.tail[1]  
		d.tail[1] = value  
	}  
	d.size++  
}
func (d *Deque) PopFront() int {  
	if d.size == 0 {  
		return 0  
	}  
	value := d.head[0]  
	d.head[0] = d.head[1]  
	d.head[1] = value  
	d.size--  
	return value  
}
func (d *Deque) PopBack() int {  
	if d.size == 0 {  
		return 0  
	}  
	value := d.tail[0]  
	d.tail[0] = d.tail[1]  
	d.tail[1] = value  
	d.size--  
	return value  
}
func main() {  
	deque := Deque{}  
	deque.PushFront(1)  
	deque.PushFront(2)  
	deque.PushBack(3)  
	deque.PushBack(4)  
	fmt.Println(deque.PopFront()) // 输出 2  
	fmt.Println(deque.PopFront()) // 输出 1  
	fmt.Println(deque.PopBack()) // 输出 4  
	fmt.Println(deque.PopBack()) // 输出 3  
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60

    在这个实现中，我们使用了四个时间复杂度为 O(1) 的过程来实现双端队列的两端插入和删除操作。

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    通义千问：

    双端队列是一种特殊的队列，可以在队列的两端进行插入和删除操作，以下是在双端队列的两端插入和删除元素的操作的四个时间均为 O(1)的过程，该队列是用一个数组实现的：

    1.在队列的前端插入元素：首先检查队列是否已满，如果已满则返回错误。然后检查队列是否为空，如果为空则将队列的大小增加一，将新元素添加到队列的开始位置。最后，将队列的前端指针前移一位。

    2.在队列的后端插入元素：首先检查队列是否已满，如果已满则返回错误。然后检查队列是否为空，如果为空则将队列的大小增加一，将新元素添加到队列的末尾位置。最后，将队列的后端指针后移一位。

    3.在队列的前端删除元素：首先检查队列是否为空，如果为空则返回错误。然后，将队列的前端指针前移一位，并返回队列的开始位置的元素。

    4.在队列的后端删除元素：首先检查队列是否为空，如果为空则返回错误。然后，将队列的后端指针后移一位，并返回队列的末尾位置的元素。

    以上四个过程的时间复杂度均为 O(1)，因为它们只涉及到指针的移动和数组的大小调整，这些操作的时间复杂度均为常数时间。

    在这里插入图片描述

    天工：

    下面是使用 Go 语言实现的双端队列，支持在队首和队尾进行插入和删除操作：

    package main

import "fmt"

type Deque struct {
    items []int
}

func NewDeque() *Deque {
    return &Deque{}
}

func (d *Deque) Front() int {
    if len(d.items) == 0 {
        return -1
    }
    return d.items[0]
}

func (d *Deque) Rear() int {
    if len(d.items) == 0 {
        return -1
    }
    return d.items[len(d.items)-1]
}

func (d *Deque) 

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27

    在这里插入图片描述

    chatgpt：

    以下是使用数组实现的双端队列的四个时间复杂度为O(1)的操作：

    1.在队列前端插入元素（push_front）：

    • 创建一个新的临时数组tmp，长度比原数组多1。

    • 将要插入的元素赋值给tmp的第一个位置。

    • 将原数组中的所有元素依次赋值给tmp中对应的位置（原数组下标+1）。

    • 将tmp赋值给原数组。

    • 更新队列长度。

    2.在队列前端删除元素（pop_front）：

    • 创建一个新的临时数组tmp，长度比原数组少1。

    • 将原数组中除了第一个元素以外的所有元素依次赋值给tmp中对应的位置（原数组下标-1）。

    • 将tmp赋值给原数组。

    • 更新队列长度。

    3.在队列后端插入元素（push_back）：

    • 将要插入的元素赋值给原数组的队列长度位置（最后一个元素的下一个位置）。

    • 更新队列长度。

    4.在队列后端删除元素（pop_back）：

    • 将原数组的最后一个元素置为空。

    • 更新队列长度。

    请注意，这里的时间复杂度为O(1)是指在插入或删除操作内部的操作数量与数组的大小无关，即不随着队列元素数量的增加而增加。通过对数组的封装和移动元素的操作，可以实现这种操作复杂度。

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

  • 相关阅读:
    VS2019无法设置Qt版本解决方案
    【【萌新的FPGA学习之按键控制蜂鸣器之消抖介绍】】
    FITC-PEG-MAL，荧光素聚乙二醇马来酰亚胺，FITC-PEG-Maleimidev
    Linux权限的认识
    SpringCloud - Spring Cloud Alibaba 之 Seata分布式事务服务；集成Nacos配置中心（十九）
    [信息抽取]基于ERNIE3.0的多对多信息抽取算法：属性关系抽取
    blender导出UE4用的FBX骨骼动画
    ConcurrentHashMap 成员、方法分析
    如何有效防止服务器被攻击？
    JavaScript脚本操作CSS
  • 原文地址：https://blog.csdn.net/weixin_48502062/article/details/133616961