算法系列之栈和队列(一):设计一个栈,可以获取栈中最大值以及最小值

本文阅读 3 分钟
首页 代码,Java 正文

引言

从本篇开始,会持续写一点关于笔试算法题目的博客,主要是一些笔试题中关于算法的部分,这些题目来自于网络以及书籍中。博文会进行题目的分析以及编码实现。之所以是想写这些,因为觉得算法是程序的灵魂,日常工作中大都是一些业务代码的实现,较少会涉及到算法部分。

一、题目

实现一个获取栈中最小值的栈,除了需要实现栈的基本功能,还需要可以获取栈中最小值以及最大值的功能。

二、分析

栈的基本功能就是先入后出,基本功能的话一个栈就可以实现了。但是如果需要另外实现获取栈中最小值以及最大值,则需要另外两个栈,一个栈存储栈中最小值,另一个栈存储最大值,而且每次出现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();
    }

}
本文为互联网自动采集或经作者授权后发布,本文观点不代表立场,若侵权下架请联系我们删帖处理!文章出自:https://blog.csdn.net/Diamond_Tao/article/details/82313024
-- 展开阅读全文 --
大白话讲解JDK源码系列:从头到尾再讲一遍ThreadLocal
« 上一篇 01-30
KillDefender 的 Beacon 对象文件 PoC 实现
下一篇 » 02-09

发表评论

成为第一个评论的人

热门文章

标签TAG

最近回复