数据结构与算法 - 实战：队列2

题目：设计一个逆置队列元素的算法。

/**
 * 队列逆置类
 * @param <AnyType> 逆置的类型
 */
public class QueueReversal<AnyType> {
   
     

    /**
     * 构造方法
     */
    public QueueReversal() {}

    /**
     * 逆置队列元素
     * @param queue 原始队列
     * @return 逆置后的队列
     */
    public LinkListQueue<AnyType> reverseQueue(LinkListQueue<AnyType> queue) {
        LinkedListStack<AnyType> stack = new LinkedListStack<AnyType>();
        // 出队-->入栈
        while (!queue.isEmpty()) {
            stack.push(queue.deQueue());
        }
        // 出栈-->入队
        while (!stack.isEmpty()) {
            queue.enQueue(stack.pop());
        }
        return queue;
    }
}

测试代码，如下：

/**
 * 队列逆置测试方法
 */
public static void reverseQueueTest() {
    // 创建原始队列
    LinkListQueue<Integer> queue = new LinkListQueue<Integer>();
    queue.enQueue(1);
    queue.enQueue(9);
    queue.enQueue(3);
    queue.enQueue(7);

    // 创建逆置队列实例
    QueueReversal<Integer> qr = new QueueReversal<Integer>();
    // 创建结果队列
    LinkListQueue<Integer> result = new LinkListQueue<Integer>();
    // 逆置队列
    result = qr.reverseQueue(queue);

    // 输出结果 7 3 9 1
    while (!result.isEmpty()) {
        System.out.print(result.deQueue() + " ");
    }
}

题目：给定一个整数栈，如何检查栈中每对相邻数字是否是连续的。每对数字的值可以是递增或递减的。如果栈中的元素个数是奇数，那么组队时忽略栈顶元素。
例如，假设栈中元素为[4,5,-2,-3,11,10,5,6,20]，那么该算法应该忽略栈顶元素20，并输出true
因为每对(4,5)、(-2,-3)、(11,10)、(5,6)都是连续数字

/**
 * 给定一个整数栈，如何检查栈中每对相邻数字是否是连续的
 * 注意：要保证栈中元素顺序和个数不变
 * @param stack 给定的整数栈
 * @return true 是连续的 false 不是连续的
 */
public static boolean checkStackPairwiseOrder(LinkedListStack<Integer> stack) {
    LinkListQueue<Integer> queue = new LinkListQueue<Integer>();
    boolean pairwiseOrdered = true;
    // 出栈 --> 入队  --> 队列元素(队首-->队尾):[20,6,5,10,11,-3,-2,5,4]
    while (!stack.isEmpty()) {
        queue.enQueue(stack.pop());
    }
    // 出队 --> 入栈  --> 栈中元素(栈底-->栈顶):[20,6,5,10,11,-3,-2,5,4]
    while (!queue.isEmpty()) {
        stack.push(queue.deQueue());
    }
    // 出栈 --> 入队  --> 队列元素(队首-->队尾):[4,5,-2,-3,11,10,5,6,20]
    while (!stack.isEmpty()) {
        int m = stack.pop();
        queue.enQueue(m);
        if (!stack.isEmpty()) {
            int n = stack.pop();
            queue.enQueue(n);
            if (Math.abs(m - n) != 1) {
                pairwiseOrdered = false;
            }
        }
    }
    // 出队 --> 入栈  --> 栈中元素(栈底-->栈顶):[4,5,-2,-3,11,10,5,6,20]
    while (!queue.isEmpty()) {
        stack.push(queue.deQueue());
    }
    return pairwiseOrdered;
}

测试代码，如下：

/**
 * 测试方法
 */
public static void checkStackPairwiseOrderTest() {
    LinkedListStack<Integer> stack = new LinkedListStack<Integer>();
    stack.push(4);
    stack.push(5);
    stack.push(-2);
    stack.push(-3);
    stack.push(11);
    stack.push(10);
    stack.push(5);
    stack.push(6);
    stack.push(2);
    System.out.println(checkStackPairwiseOrder(stack)); // true
}

题目：给定一个整数k和一个整数队列，如何把队列中前k个元素逆置，其余元素保持不变？
例如：如果k为4，队列元素为[10,20,30,40,50,60,70,80,90],则输出[40,30,20,10,50,60,70,80,90]

/**
 * 逆置队列中前k个元素
 * @param k 逆置元素的个数
 * @param queue 整数队列
 * @throws Exception 
 */
public static LinkListQueue<Integer> reverseQueueFirstKElements(int k, LinkListQueue<Integer> queue) throws Exception {
    if (queue == null || k > queue.getQueueSize()) {
        throw new Exception("队列为空或K值太大！");
    } else {
        LinkedListStack<Integer> stack = new LinkedListStack<Integer>();
        // 将队列前k个元素压入栈中
        for (int i = 0; i < k; i++) {
            stack.push(queue.deQueue());
        }
        // 将栈中k个元素出栈，入队到队列
        while (!stack.isEmpty()) {
            queue.enQueue(stack.pop());
        }
        // 将队列中剩余元素逆置到队尾
        for (int i = 0; i < queue.getQueueSize() - k; i++) {
            queue.enQueue(queue.deQueue());
        }
        return queue;
    }

}

测试代码，如下：

/**
 * 逆置队列中前k个元素测试类
 * 输出结果：
 * 逆置前队列元素：10 20 30 40 50 60 70 80 90 
 * 逆置后队列元素：40 30 20 10 50 60 70 80 90 
 */
public static void reverseQueueFirstKElementsTest() {
    LinkListQueue<Integer> queue = new LinkListQueue<Integer>();
    queue.enQueue(10);
    queue.enQueue(20);
    queue.enQueue(30);
    queue.enQueue(40);
    queue.enQueue(50);
    queue.enQueue(60);
    queue.enQueue(70);
    queue.enQueue(80);
    queue.enQueue(90);

    int size = queue.getQueueSize();
    int count = 0;
    System.out.print("逆置前队列元素：");
    while (count < size) {
        int temp = queue.deQueue();
        queue.enQueue(temp);
        System.out.print(temp + " ");
        count++;
    }

    System.out.println();

    try {
        LinkListQueue<Integer> result = reverseQueueFirstKElements(4, queue);
        System.out.print("逆置后队列元素：");
        while (!result.isEmpty()) {
            System.out.print(result.deQueue() + " ");
        }
    } catch (Exception e) {
        e.printStackTrace();
    }
}

15、数据结构与算法 - 实战：队列2