引言
从本篇开始，会持续写一点关于笔试算法题目的博客，主要是一些笔试题中关于算法的部分，这些题目来自于网络以及书籍中。博文会进行题目的分析以及编码实现。之所以是想写这些，因为觉得算法是程序的灵魂，日常工作中大都是一些业务代码的实现，较少会涉及到算法部分。
一、题目
实现一个获取栈中最小值的栈，除了需要实现栈的基本功能，还需要可以获取栈中最小值以及最大值的功能。
二、分析
栈的基本功能就是先入后出，基本功能的话一个栈就可以实现了。但是如果需要另外实现获取栈中最小值以及最大值，则需要另外两个栈，一个栈存储栈中最小值，另一个栈存储最大值，而且每次出现push以及pop操作的时候都需要将最小值以及最大值进行更新。因为当出现push以及pop操作的时候，栈中的最小值以及最大值可能会发生变化。
三、代码实现
package com.algorithm; import java.util.Stack; import com.exception.ProgramException; /** * @author taomeng * @Date 2018年9月2日 * @Discription : 获取栈中的最小值 */ public class NewStack { /** * 存储数据 */ private Stack<Integer> dataStack; /** * 存储栈中最小值 */ private Stack<Integer> minDataStack; /** * 存储栈中最大值 */ private Stack<Integer> maxDataStack; public NewStack(Stack<Integer> dataStack, Stack<Integer> minDataStack, Stack<Integer> maxDataStack) { this.dataStack = dataStack; this.minDataStack = minDataStack; this.maxDataStack = maxDataStack; } /** * * 函数功能描述：栈的数据插入 * @date 2018年9月2日上午11:17:15 * @param newData void * @author taomeng */ public void push(int newData) { if (minDataStack.isEmpty()) { minDataStack.push(newData); } else if (newData <= getMin()) { minDataStack.push(newData); } if (maxDataStack.isEmpty()) { maxDataStack.push(newData); } else if (newData >= getMax()) { maxDataStack.push(newData); } dataStack.push(newData); } /** * * 函数功能描述：数据弹出 * @date 2018年9月2日上午11:23:50 * @return int * @author taomeng */ public int pop() { if (dataStack.isEmpty()) { throw new ProgramException("stack is empty"); } int value = dataStack.pop(); if (value == getMin()) { minDataStack.pop(); } if (value == getMax()) { maxDataStack.pop(); } return value; } /** * * 函数功能描述：获取栈中最小值 * @date 2018年9月2日上午11:24:07 * @return int * @author taomeng */ public int getMin() { if (minDataStack.isEmpty()) { throw new ProgramException("stack is empty"); } return minDataStack.peek(); } /** * * 函数功能描述：获取栈中最大值 * @date 2018年9月2日下午12:00:58 * @return int * @author taomeng */ public int getMax() { if (maxDataStack.isEmpty()) { throw new ProgramException("stack is empty"); } return maxDataStack.peek(); } }
