JAVA练习54-最小栈

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

目录

前言

一、题目-最小栈

1.题目描述

2.思路与代码

2.1 思路

2.2 代码

总结

---

前言

提示：这里可以添加本文要记录的大概内容：

2月18日练习内容

---

提示：以下是本篇文章正文内容，下面案例可供参考

一、题目-最小栈

1.题目描述

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。

示例 1:

输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]输出：
[null,null,null,null,-3,null,0,-2]解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

提示：

-231 <= val <= 231 - 1
pop、top 和 getMin 操作总是在 非空栈 上调用
push, pop, top, and getMin最多被调用 3 * 104 次

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/min-stack
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2.思路与代码

2.1 思路

1.因为该题目可以使用链表来实现栈，则需要先建立一个内部类ListNode，该内部类的成员变量有链表的值val，该链表的最小值min，该链表的下一个结点next

2.创建最小栈类的成员变量ListNode head；

3.实现构造函数，将head置为空

4.实现一个成员方法IsEmpty，判断该栈是否为空‘

5.对于push方法，需要先判断该栈是否为空，如果栈为空，则创建一个新结点，其值和最小值等于输入的值，下一个结点为空；如果栈不为空，则创建一个新的结点，值为输入的值，最小值为输入的值与原本栈内的最小值比较之后的较小值，next为head（因为栈为先入后出，所以第一个结点为最后加入的结点），接着将新创建的结点赋值为head

6.对于pop方法，先判断栈是否为空，若栈为空，则创建一个栈为空的异常并抛出；若栈不为空，则删除头结点head=head.next

7.对于top方法，先判断是否为空，若空，抛出栈为空的异常；若不为空，则输出head.val;

8.对于getMin方法，先判断是否为空，若空，抛出栈为空的异常；若不为空，输出head.min

2.2 代码

代码如下（示例）：

class MinStack {//内部类class ListNode{private int val;private int min;    //最小值private ListNode next;public ListNode(int val,int min,ListNode next){this.val = val;this.min = min;this.next = next;}}//成员变量private ListNode head;public MinStack() {this.head = null;}public void push(int val) {//判断栈是否为空if(isEmpty()){//若栈为空，则创建一个新的结点，结点的值和最小值都为输入的值head = new ListNode(val,val,null);}else{//若栈不为空，因为栈为先入后出，则直接将新创建的新结点赋值给和蔼的即可head = new ListNode(val,Math.min(val,head.min),head);}}public void pop() {//判断链表是否为空if(isEmpty()){//当栈为空时，输出一个栈为空的异常throw new IllegalStateException("栈为空……");}else{head = head.next;}}public int top() {if(isEmpty()){//当栈为空时，输出一个栈为空的异常throw new IllegalStateException("栈为空……");}else{return head.val;}}public int getMin() {if(isEmpty()){//当栈为空时，输出一个栈为空的异常throw new IllegalStateException("栈为空……");}else{return head.min;}}//判断链表是否为空private boolean isEmpty(){return head == null;}}/*** Your MinStack object will be instantiated and called as such:* MinStack obj = new MinStack();* obj.push(val);* obj.pop();* int param_3 = obj.top();* int param_4 = obj.getMin();*/

---

总结

提示：这里对文章进行总结：