1，设计一个有getMin功能的栈
题目：实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返回栈中的最小值
要求：
1，pop、push、getMin操作的时间复杂度都是O（1）
2，设计的栈类型可以使用现成的栈的结构
public class Stack1 {
private Stack<Integer> stackMin;
private Stack<Integer> stackData;
public Stack1(){
stackMin=new Stack<>();
stackData=new Stack<>();
}
public int getMin(){
if(stackMin.isEmpty()){
throw new RuntimeException("stack is null");
}
return stackMin.peek();
}
//方案一
//节省空间，pop步骤多
public void push(int newNum){
if(stackMin.isEmpty()){
stackMin.push(newNum);
}else{
if(getMin()<=newNum){
stackMin.push(newNum);
}
}
stackData.push(newNum);
}
public int pop(){
if(stackData.isEmpty()){
throw new RuntimeException("stack is null");
}
int value=stackData.pop();
if(value==getMin()){
stackMin.pop();
}
return value;
}
//--------------------------
//方案2
//比方案1多费空间，但省时间
public void push2(int newNum){
if(stackMin.isEmpty()){
stackMin.push(newNum);
}else if(getMin()<newNum){
stackMin.push(stackMin.peek());
}else{
stackMin.push(newNum);
}
stackData.push(newNum);
}
public int pop2(){
if(stackData.isEmpty()){
throw new RuntimeException("stack is null");
}
stackMin.pop();
return stackData.pop();
}
}
2，由两个栈组成的队列
编写一个类，用两个栈实现队列，支持队列的基本操作（add,poll,peek）
public class TwoStackQueue{
private Stack<Integer> stackPush;
private Stack<Integer> stackPop;
public TwoStackQueue(){
stackPush=new Stack<>();
stackPop=new Stack<>();
}
public void add(int newNum){
stakPush.push(newNum);
}
public int poll(){
if(stackPush.isEmpty() && stackPop.isEmpty()){
throw new RuntimeException("stack is null");
}else if(stackPop.isEmpty()){
while(!stackPush.isEmpty()){
stackPop.push(stackPush.pop());
}
}
return stackPop.pop();
}
publuc int peek(){
if(stackPush.isempty() && stackPop.isEmpty()){
throw new RuntimeException("stack is null");
}else if(stackPop.isEmpty()){
while(!stackPush.isEmpty()){
stackPop.push(stackPush.pop());
}
}
retuen stackPop.peek();
}
}
3，如何仅用递归函数和栈操作逆序一个栈
题目：
一个栈依次压入1、2、3、4、5，那么从栈顶到栈底分别为5、4、3、2、1。将这个栈转置后，从栈顶到栈底为1、2、3、4、5，也就是实现栈中元素的逆序，但是只能用递归来实现。
public static int getAndRemoveLast(Stack<Integer> stack){
int result =stack.pop();
//System.out.println("result:"+result);
if(stack.isEmpty()){
return result;
}else{
int last =getAndRemoveLast(stack);
//System.out.println("last:"+last);
stack.push(result);
return last;
}
}
public static void reverse(Stack<Integer> stack){
if(stack.isEmpty()){
return;
}
int i=getAndRemoveLast(stack);
//System.out.println("i:"+i);
reverse(stack);
//System.out.println("push i="+i);
stack.push(i);
}
测试：
public static void main(String args[]){
Stack<Integer> stack =new Stack<>();
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
stack.push(5);
System.out.println(stack.toString());
reverse(stack);
System.out.println(stack.toString());
}
输出：
[1, 2, 3, 4, 5]
[5, 4, 3, 2, 1]
4，用一个栈实现另一个栈的排序
public static void sortStack(Stack<Integer> stack) {
if (stack.isEmpty()) {
throw new RuntimeException("stack is null");
}
Stack<Integer> help = new Stack<>();
while (!stack.isEmpty()) {
int value = stack.pop();
while (!help.isEmpty() && value < help.peek()) {
stack.push(help.pop());
}
help.push(value);
}
while (!help.isEmpty()) {
stack.push(help.pop());
}
}
测试：
public static void main(String[] args){
Stack<Integer> stack=new Stack<>();
stack.push(5);
stack.push(3);
stack.push(5);
stack.push(2);
stack.push(1);
stack.push(7);
stack.push(8);
stack.push(7);
System.out.println(stack.toString());
sortStack(stack);
System.out.println(stack.toString());
}
输出：
[5, 3, 5, 2, 1, 7, 8, 7]
[8, 7, 7, 5, 5, 3, 2, 1]
5.1，递归实现汉诺塔问题
public static int hanoiProblem(int num,String left,String mid,String right){
if(num<1){
return 0;
}
return process(num,left,mid,right,left,right);
}
public static int process(int num,String left,String mid,String right,String from,String to){
if(num==1){
if(from.equals(mid) || to.equals(mid)){
System.out.println("Move 1 from "+from +" to "+to);
return 1;
}else{
System.out.println("Move 1 form "+ from +" to "+mid);
System.out.println("Move 1 form "+ mid +" to "+to);
return 2;
}
}
if(from.equals(mid) || to.equals(mid)){
String another=(from.equals(left) || to.equals(left) ? right:left);
int part1=process(num-1,left,mid,right,from,another);
int part2=1;
System.out.println("Move "+num+ " from "+from+" to "+to);
int part3=process(num-1,left,mid,right,another,to);
return part1+part2+part3;
}else{
int part1=process(num-1,left,mid,right,from,to);
int part2=1;
System.out.println("Move "+num+" from "+from+" to "+mid);
int part3=process(num-1,left,mid,right,to,from);
int part4=1;
System.out.println("Move "+ num+" form "+mid+" to "+to);
int part5=process(num-1,left,mid,right,from,to);
return part1+part2+part3+part4+part5;
}
}
5.2，通过栈实现汉诺塔
public enum Action{
No,LToM,MToL,MToR,RToM
}
public static int hanoiProblem2(int num,String left,String mid,String right){
Stack<Integer> lS=new Stack<>();
Stack<Integer> mS=new Stack<>();
Stack<Integer> rS=new Stack<>();
lS.push(Integer.MAX_VALUE);
mS.push(Integer.MAX_VALUE);
rS.push(Integer.MAX_VALUE);
for(int i=num;i>0;i--){
lS.push(i);
}
Action[] record ={Action.No};
int step=0;
while (rS.size()!=num+1){
step += fStackToStack(record, Action.MToL,Action.LToM,lS,mS,left,mid);
step += fStackToStack(record, Action.LToM,Action.MToL,mS,lS,mid,left);
step += fStackToStack(record, Action.RToM,Action.MToR,mS,rS,mid,right);
step += fStackToStack(record, Action.MToR,Action.RToM,lS,mS,right,mid);
}
return step;
}
public static int fStackToStack(Action[] record,Action preNoAct,Action nowAct,Stack<Integer> fStack,Stack<Integer> tStack,String from,String to){
if(record[0] !=preNoAct && fStack.peek()<fStack.peek()){
tStack.push(fStack.pop());
System.out.println("Move "+tStack.peek()+" from "+from+" to "+to);
record[0]=nowAct;
return 1;
}
return 0;
}