6.用栈模拟队列
题目
用栈来模拟一个队列，要求实现队列的两个基本操作：入队、出队。
思路
用两个栈，一个栈用来存储入队元素，另一个栈用来存储，出队元素。
比如，有两个栈A，B，入队元素，先进入到栈A，每次元素要出队时，就把栈A的元素依次出栈，进入到栈B，再从栈B出栈，来模拟元素出队。
代码
```java
public class QueueByStack {
private Stack stackA = new Stack<>();
private Stack 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。
代码
```java
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());
}
}
```
只是为了记录自己的学习历程，且本人水平有限，不对之处，请指正。
相关文章
