栈实现队列，探求正整数的下一个数

6.用栈模仿队列

题目

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

用两个栈，一个栈用来存储入队元素，另一个栈用来存储，出队元素。
比如，有两个栈A，B，入队元素，先进入到栈A，每次元素要出队时，就把栈A的元素依次出栈，进入到栈B，再从栈B出栈，来模仿元素出队。
代码

1. public class QueueByStack {
3.     private Stack<Integer> stackA = new Stack<>();
4.     private Stack<Integer> stackB = new Stack<>();
7.     /**
8.      * 入队
9.      * @param element 元素
10.      */
11.     public void enQueue(int element){
12.         stackA.push(element);
13.     }
15.     /**
16.      * 出队操作
17.      * @return
18.      */
19.     public Integer deQueue(){
20.         if(stackB.isEmpty()){
21.             if(stackA.isEmpty())
22.                 throw new RuntimeException("queue is empty...");
23.             transfer();
24.         }
25.         return stackB.pop();
26.     }
28.     /**
29.      * 栈A元素转移到栈B
30.      */
31.     public void transfer(){
32.         while(!stackA.isEmpty())
33.             stackB.push(stackA.pop());
34.     }
36.     public static void main(String[] args) {
37.         QueueByStack queueByStack = new QueueByStack();
38.         queueByStack.enQueue(1);
39.         queueByStack.enQueue(3);
40.         queueByStack.enQueue(4);
41.         System.out.println(queueByStack.deQueue());
42.         System.out.println(queueByStack.deQueue());
43.         queueByStack.enQueue(5);
44.         System.out.println(queueByStack.deQueue());
45.         System.out.println(queueByStack.deQueue());
46.     }
47. }

复制代码

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。
代码

1. public class NextNumber {
3.     public static int findNearestNumber(int number){
4.         int[] numbers = intToIntArray(number);
5.         int index = findTransferPoint(numbers);
6.         if(index == 0)//代表数整体都是逆序排列，是所有排列组合中最大的，无法寻找下一位
7.             return -1;
8.         exchangeHead(numbers,index);
9.         reverse(numbers,index);
10.         return intArrayToInt(numbers);
11.     }
13.     /**
14.      * 寻找逆序区域，注意返回的index还是属于逆序区域
15.      */
16.     private static int findTransferPoint(int[] numbers) {
17.         for (int i = numbers.length - 1; i > 0; i--) {//数从后往前遍历
18.             if (numbers[i] > numbers[i - 1])//发现后一个数大于前一个数的情况下，就是找到了逆序区域的边界
19.                 return i;
20.         }
21.         return 0;
22.     }
24.     /**
25.      * 交换
26.      */
27.     private static int[] exchangeHead(int[] numbers, int index) {
28.         int head = numbers[index - 1];//逆序区域的前一位数
29.         //从后往前，第一个大于head的数，就是逆序区域中大于head的最小数，因为是逆序区域
30.         for (int i = numbers.length - 1; i > 0; i--) {
31.             if(head < numbers[i]){
32.                 numbers[index - 1] = numbers[i];
33.                 numbers[i] = head;
34.                 break;
35.             }
36.         }
37.         return numbers;
38.     }
40.     /**
41.      * 将int[]数组，从index开始后的数，反转 1,2,4,6,5,3 -> 1,2,4,3,5,6
42.      */
43.     private static int[] reverse(int[] num,int index){
44.         for(int i =index,j = num.length-1;i < j;i++,j--){
45.             int temp = num[i];
46.             num[i] = num[j];
47.             num[j] = temp;
48.         }
49.         return num;
50.     }
52.     public static void main(String[] args) {
53.         int number = 123654;
54.         for(int i = 0; i < 10; i++){
55.             number = findNearestNumber(number);
56.             System.out.println(number);
57.         }
58.     }
60.     /**
61.      * int数，转成各个位构成的int[]
62.      */
63.     private static int[] intToIntArray(int number){
64.         String numAsString = String.valueOf(number);
65.         int[] digits = new int[numAsString.length()];
66.         for(int i = 0; i < numAsString.length(); i++)
67.             digits[i] = numAsString.charAt(i) - '0';//减去'0'的ASCII码值，得到数。char类型在java中可以看作是一个int的数
68.         return digits;
69.     }
71.     /**
72.      * int[]，转成int
73.      */
74.     private static int intArrayToInt(int[] numbers){
75.         StringBuilder sb = new StringBuilder();
76.         for(int i : numbers)
77.             sb.append(i);
78.         return Integer.parseInt(sb.toString());
79.     }
81. }

复制代码

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

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。