【程序员代码面试指南】-栈和队列-最小栈/ 双栈队列/ 栈排序

【题目一】

实现一个特殊栈，实现pop，push函数并且实现返回栈中最小元素的函数getMin

【要求】

时间复杂度O（1），可以使用现成的栈结构

【代码】

//用两个栈实现，一个正常存取，另一个只存放当前最小值
	private Stack<Integer> stackData;	
	private Stack<Integer> stackMin;
	
	public Stack01() {
		stackData = new Stack<>();
		stackMin = new Stack<>();
	}
	
	public void push(int data) {
		if (stackMin.isEmpty()) {
			stackMin.push(data);
		}else if (data < stackMin.peek()) {
			stackMin.push(data);
		}else{
			stackMin.push(stackMin.peek());
		}
		stackData.push(data);
	}
	
	public int pop() {
		if (stackData.isEmpty()) {
			System.out.println("stack is Empty");
			return -999;
		}
		stackMin.pop();
		return stackData.pop();
	}
	
	public int getMin() {
		if (stackData.isEmpty()) {
			System.out.println("stack is Empty");
			return -999;
		}
		return stackMin.peek();
		
	}

【测试】

【题目二】

用两个栈实现队列，实现pop,add,peek操作

【代码】

//用两个栈实现，一个负责压入，另一个负责弹出,查看
	private Stack<Integer> stackPush;	
	private Stack<Integer> stackPop;
	
	public Queue01() {
		stackPush = new Stack<>();
		stackPop = new Stack<>();
	}
	
	public void add(int data) {
		stackPush.push(data);
	}
	
	public int pop() {
		if (stackPop.isEmpty()) {
			if (!stackPush.isEmpty()) {
				//将目前压入栈的所有元素依次弹出，压入弹出栈
				while (!stackPush.isEmpty()) {
					stackPop.push(stackPush.pop());
				}
			}else {
				throw new RuntimeException("stack is Empty");
			}
		}
		return stackPop.pop();
	}	
	
	public int peek() {
		if (stackPop.isEmpty()) {
			if (!stackPush.isEmpty()) {
				//将目前压入栈的所有元素依次弹出，压入弹出栈
				while (!stackPush.isEmpty()) {
					stackPop.push(stackPush.pop());
				}
			}else {
				throw new RuntimeException("stack is Empty");
			}
		}
		return stackPop.peek();
	}

【测试】

【题目三】

实现栈从顶到底按从大到小排序，除了一个栈外，不能申请其他数据结构

【代码】

public static void sortByStack(Stack<Integer> stack) {
		Stack<Integer> help = new Stack<>();
		while(!stack.isEmpty()) {
			//从stack栈顶取出一个元素，存入临时tem里
			int tem = stack.pop();
			//将help里小于tem的元素从上到下依次弹出压会stack中
			while (!help.isEmpty() && help.peek()<tem ) {
				stack.push(help.pop());
			}
			//将tem压入help中，此时要么help只有tem一个元素
			// 要么tem下边的元素均比tem大 
			help.push(tem);
			//重复上述过程，实现help内元素顶到底是从小到大排列的，stack为空
		}
		while (!help.isEmpty()) {
			stack.push(help.pop());
		}
	}

	//实现从顶到底打印,借助help栈，依次弹出stack元素到help并打印，
	// 然后再还原stack 
	public static void printFromTtoE(Stack<Integer> stack) {
		Stack<Integer> help = new Stack<>();
		Iterator<Integer> it = stack.iterator();
		int tem = 0;
		while (it.hasNext()) {
			tem = stack.pop();
			help.push(tem);
			System.out.print(tem+" ");
		}
		System.out.println();
		while (!help.isEmpty()) {
			stack.push(help.pop());
		}
	}

【测试】