栈实现队列，寻找正整数的下一个数

6.用栈模拟队列

题目

用栈来模拟一个队列，要求实现队列的两个基本操作：入队、出队。

思路

用两个栈，一个栈用来存储入队元素，另一个栈用来存储，出队元素。

比如，有两个栈A，B，入队元素，先进入到栈A，每次元素要出队时，就把栈A的元素依次出栈，进入到栈B，再从栈B出栈，来模拟元素出队。

代码

public class QueueByStack {

    private Stack<Integer> stackA = new Stack<>();
    private Stack<Integer> stackB = new Stack<>();


    /**
     * 入队
     * @param element 元素
     */
    public void enQueue(int element){
        stackA.push(element);
    }

    /**
     * 出队操作
     * @return
     */
    public Integer deQueue(){
        if(stackB.isEmpty()){
            if(stackA.isEmpty())
                throw new RuntimeException("queue is empty...");
            transfer();
        }
        return stackB.pop();
    }

    /**
     * 栈A元素转移到栈B
     */
    public void transfer(){
        while(!stackA.isEmpty())
            stackB.push(stackA.pop());
    }

    public static void main(String[] args) {
        QueueByStack queueByStack = new QueueByStack();
        queueByStack.enQueue(1);
        queueByStack.enQueue(3);
        queueByStack.enQueue(4);
        System.out.println(queueByStack.deQueue());
        System.out.println(queueByStack.deQueue());
        queueByStack.enQueue(5);
        System.out.println(queueByStack.deQueue());
        System.out.println(queueByStack.deQueue());
    }
}

7.寻找全排列的下一个数

题目

给出一个正整数，找出这个正整数所有数字全排列的下一个数。通俗点说就是在一个整数所包含数字的全部组合中，找到一个大于且仅大于原数的新整数。

如果输入12345，则返回12354。如果输入12354，则返回12435。如果输入12435，则返回12453。

思路

由固定数字组成的数，排列的最大值，一定逆序排列，排列的最小值，一定是顺序排列。

如1，2，3，4，5，6这些数字，最大值，是654321，最小值是123456。

给定一个整数，如何找大于且仅大于当前数的新整数呢？

例如，123654，为了和原数接近，我们要尽量保持高位不变，低位在最小范围内变换顺序。变换顺序的范围大小，却决于当前整数的逆序区域。

什么是逆序区域，就是我们把一个数，从最后一位往前数，数字是顺序排列的区域，就是逆序区域。

比如，123654，其中654就是这个数据的逆序区域。123465，其中65就是这个数据的逆序区域。123456，其中6就是这个数的逆序区域。654321，则整体都是逆序区域，最大值，找不出大于且仅大于原数的整数了。

如何，找出123654的大于且仅大于原数的新整数呢？

我们只需要，找出逆序区域中，大于逆序区域边界前一个数中最小的数，进行交换，然后，将逆序区域，变为顺序，就是了。首先从逆序区域中，找出一个大于边界前一个数，最小的数，与之交换，是保证交换后的数，大于原数。将逆序区域，改为顺序，是为了保证，是排序后的数，大于原数的情况下最小的一个。

例如，123654，逆序区域为654，其中大于3的最小的是4，交换后，是124653，满足大于元素，但不是最小，因为653这个三位的排列，不满足最小的，需要改为顺序排列，356，所以，大于且仅大于原数的新整数，即为124356。

代码

public class NextNumber {

    public static int findNearestNumber(int number){
        int[] numbers = intToIntArray(number);
        int index = findTransferPoint(numbers);
        if(index == 0)//代表数整体都是逆序排列，是所有排列组合中最大的，无法寻找下一位
            return -1;
        exchangeHead(numbers,index);
        reverse(numbers,index);
        return intArrayToInt(numbers);
    }

    /**
     * 寻找逆序区域，注意返回的index还是属于逆序区域
     */
    private static int findTransferPoint(int[] numbers) {
        for (int i = numbers.length - 1; i > 0; i--) {//数从后往前遍历
            if (numbers[i] > numbers[i - 1])//发现后一个数大于前一个数的情况下，就是找到了逆序区域的边界
                return i;
        }
        return 0;
    }

    /**
     * 交换
     */
    private static int[] exchangeHead(int[] numbers, int index) {
        int head = numbers[index - 1];//逆序区域的前一位数
        //从后往前，第一个大于head的数，就是逆序区域中大于head的最小数，因为是逆序区域
        for (int i = numbers.length - 1; i > 0; i--) {
            if(head < numbers[i]){
                numbers[index - 1] = numbers[i];
                numbers[i] = head;
                break;
            }
        }
        return numbers;
    }

    /**
     * 将int[]数组，从index开始后的数，反转 1,2,4,6,5,3 -> 1,2,4,3,5,6
     */
    private static int[] reverse(int[] num,int index){
        for(int i =index,j = num.length-1;i < j;i++,j--){
            int temp = num[i];
            num[i] = num[j];
            num[j] = temp;
        }
        return num;
    }

    public static void main(String[] args) {
        int number = 123654;
        for(int i = 0; i < 10; i++){
            number = findNearestNumber(number);
            System.out.println(number);
        }
    }

    /**
     * int数，转成各个位构成的int[]
     */
    private static int[] intToIntArray(int number){
        String numAsString = String.valueOf(number);
        int[] digits = new int[numAsString.length()];
        for(int i = 0; i < numAsString.length(); i++)
            digits[i] = numAsString.charAt(i) - '0';//减去'0'的ASCII码值，得到数。char类型在java中可以看作是一个int的数
        return digits;
    }

    /**
     * int[]，转成int
     */
    private static int intArrayToInt(int[] numbers){
        StringBuilder sb = new StringBuilder();
        for(int i : numbers)
            sb.append(i);
        return Integer.parseInt(sb.toString());
    }

}

只是为了记录自己的学习历程，且本人水平有限，不对之处，请指正。