创建队列、enque、deque 和 qempty 函数

Question

这就是广度优先的图遍历算法。我不知道如何创建“队列”、“出队”、“入队”、“qempty”功能，迫切需要帮助！

队列：创建一个队列（$s5）

入队：从源获取值到q

出队：将项目从 q 弹出到 v ($s5 --> $s3)

qempty：检查q是否为空

这是我的代码：

.data
#  id, mark, pointers
graph: .word 1 , 0   , 24, 48, 72, -1, # 0
  2 , 0   , 00, 96, 120, -1, # 24
  3 , 0   , 00, 120, -1, -1, # 48
  4 , 0   , 00, -1, -1, -1, # 72
  5 , 0   , 24, -1, -1, -1,  # 96
  6 , 0   , 24, 48, -1, -1 # 120
.text
# graph = $s0, source = $s1, size = $s2, v = $s3, w = $s4, queue = $s5, edge = $s6, i = $s7
# $a0 -> graph, $a1 -> source, $a2 -> size

main: 
la $s0, graph

addi $s2, $zero, 6

add $s1, $zero, $zero

move $a0, $s0

move $a1, $s1

move $a2, $s2

jal BFS

j finish

BFS:
addi $sp, $sp, -32

sw $s0, 0($sp)

sw $s1, 4($sp)

sw $s2, 8($sp)

sw $s3, 12($sp)

sw $s4, 16($sp)

sw $s5, 20($sp)

sw $s6, 24($sp)

sw $s7, 28($sp)

jal queue

move $s0, $a0

move $s1, $a1

move $s2, $a2

sll $t0, $s1, 2

add $t0, $t0, $s0

lw $t0, ($t0)

move $a0, $t0

jal enqueue

addi $t1, $s1, 1

sll $t1, $t1, 2

add $t1, $t1, $s0

addi $t2, $zero, 1

sw $t2, ($t1)

while: 
jal qempty

beq $v0, $zero, endwhile

jal dequeue

add $s3, $v0, $zero

for:

add $s7, $zero, $zero

slti $t3, $s7, 4

beq $t3, $zero, endfor

addi $t4, $s3, -1

mul $t4, $t4, 6

add $t4, $t4, $s7

sll $s6, $t4, 2

add $s6, $s6, $s0

lw $s6, 0($s6)

if1:

beq $s6, -1, endif1

move $s4, $s6

if2: 

addi $t5, $s4, 1

sll $t5, $t5, 2

add $t5, $t5, $s0

lw $t5, 0($t5)

bne $t5, 0, endif2

addi $t6, $s4, 1

sll $t6, $t6, 2

add $t6, $t6, $s0

sw $t6, 1

add $t7, $s4, $zero

sll $t7, $t7, 2

lw $t7, 0($t7)

move $a0, $t7

jal enqueue

endif2: 

endif1:

 j for

endfor: 

 j while

endwhile:

finish:

lw $s0, 0($sp)

lw $s1, 4($sp)

lw $s2, 8($sp)

lw $s3, 12($sp)

lw $s4, 16($sp)

lw $s5, 20($sp)

lw $s6, 24($sp)

lw $s7, 28($sp)

addi $sp, $sp, 32

Answer 1

对于 q，我们将创建一个带有两个指针的数组（一个用于开始，一个用于结束），这两个指针首先指向同一位置

入队：将数据从源移动到 q

        increment the end pointer

出队：将数据从 q 移动到 v

增量开始指针

qempty：从结束指针开始的子指针，

如果结果为零则队列为空