List实现队列--杀人游戏

使用list集合实现一个队列

package queue;/*
 * @auther 顶风少年
 * @mail dfsn19970313@foxmail.com
 * @date 2020-01-09 09:42
 * @notify
 * @version 1.0
 */

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Queue<T> {

    private ArrayList<T> queue = new ArrayList<T>();

    //从队列尾部添加元素
    public void add(T... ts) {
        List<T> ts1 = Arrays.asList(ts);
        queue.addAll(ts1);
    }

    //从队列头部删除一个元素
    public T del() {
        if (queue.isEmpty()) {
            return (T) "-1";
        }
        T remove = queue.remove(0);
        return remove;
    }

    //返回头部的元素，不是删除
    public T head() {
        if (queue.isEmpty()) {
            return (T) "-1";
        }
        return queue.get(0);
    }

    //返回队列的大小
    public int size() {
        return queue.size();
    }

    //清空队列
    public void clear() {
        queue.clear();
    }

    //判断队列是否为空
    public boolean isEmpty() {
        return queue.isEmpty();
    }

    //返回队列尾部元素
    public T tail() {
        if (queue.isEmpty()) {
            return (T) "-1";
        }
        return queue.get(queue.size() - 1);
    }
}

View Code

/*
* 约瑟夫问题是个有名的问题：
* N个人围成一圈，从第一个开始报数，第M个将被杀掉，
* 最后剩下一个，其余人都将被杀掉。例如N=6，M=5，
* 被杀掉的顺序是：5，4，6，2，3，1。
* 思路：做一个计数器，计数器起步为1，被杀者从1开始喊，前4个人
* 1 2 3 4 不会被杀，但是当第N个人喊完数后，还要从第一个开始喊，
* 所以我们将没有被杀的依次从队列的头部删除，添加到队列尾部，并将计数器+1。形成
* 一个圆环，当计数器喊道5，则表示有人要被杀，此时将计数器归为1.直到队列中只剩下
* 一个人。
* */

 @Test
    public void t1() {
        Queue queue = new Queue();
        queue.add(1, 2, 3, 4, 5, 6);
        int index = 1;
        while (queue.size() != 1) {
            if (index == 5) {
                Object del = queue.del();
                index = 1;
                System.out.println(del);
            } else {
                Object del = queue.del();
                queue.add(del);
                index += +1;
            }
        }
        System.out.println("幸运儿：" + queue.head());
    }

View Code

/菲波那切数列
1 1 2 3 5 8 13 21 34 55
* 从第三个数开始，当前数是前两个数相加的值。
* 1 1 2
* 1 2 3
* 2 3 5
* 3 5 8
* 。。。
* 思路：计算第10项则需要累加10次。前两个 1 1 占两项。
* 循环条件为当前项小于总项数
* 每次循环将队列头部元素移除，将移除的元素和当前队列头部元素相加
* 即为下一项的值。1 1 将1移除和1相加为2 将2添加队列。
* 1 2 将1移除和2相加为3，将3添加队列尾部。循环结束队列中有两个数字
* 队列尾部的则为计算后的值
* */

    @Test
    public void t2() {
        int item = 10;
        int index = 2;
        Queue<Integer> queue = new Queue<>();
        queue.add(1, 1);
        while (index < item) {
            Integer del = queue.del();
            queue.add(queue.head() + del);
            index += 1;
        }
        System.out.println(queue.tail());
    }

View Code