Java数据结构与算法(最小栈)

前言

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

实现 MinStack 类:

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

实现原理

1.设计两个栈，第一个栈存放当前入栈元素，第二个栈数据入栈时的最小值。

2.最小值栈顶通过入栈数据与栈顶数据比较，将比较后最小的值再次压入栈顶。保障最小栈栈顶的值为最小。

具体代码实现

class MinStack {Deque<Integer> xStack;Deque<Integer> minStack;public MinStack() {xStack=new LinkedList();minStack=new LinkedList();minStack.push(Integer.MAX_VALUE);}public void push(int val) {xStack.push(val);minStack.push(Math.min(val,minStack.peek()));}public void pop() {xStack.pop();minStack.pop();}public int top() {return xStack.peek();}public int getMin() {return minStack.peek();}
}

QA:待定