第三十五天(队列)

今天完成题目:641,621,622 641:设计循环双端队列

• 双端队列:可以从两端进出队

• 循环队列:队头连接队尾(链表),通过取模来获得索引(数组)

621:任务调度器

• 默认选择数量最多(max_count)的任务按照间隔n排开,共有(max_count-1)个间隔

• 其他任务由于小于等于该任务数:

  • 所以若小于,必定能在(max_count-1)中合理插入

  • 若等于,则会多出一个,可以计入max_number中

• 当其他任务数的总和大于所留下的间隔时:

  • 必然可以插满,没有待命

• 也可以用列优先的图来理解.

622:设计循环队列

• 两个索引,一个记录起始的结点,一个记录下一个数据插入的结点

• 需要区分队空和队满

  1. 利用一个多余的空间

  2. 设置原始数据为-1,表示未插入

  3. 设计一个记录数组长度的变量

空闲单元法