首页 > 代码库 > 队列实现max操作，要求尽量提高效率。
队列实现max操作，要求尽量提高效率。
结合之前实现的 maxStack 和 用两个stack 实现一个Queue， 实现 MaxQueue
import java.util.Stack;public class MaxQueue { MaxStack in = new MaxStack(); MaxStack out = new MaxStack(); public void enqueue(Integer a) { in.push(a); } public Integer dequeue() { shiftItems(); return out.pop(); } public Integer peek() { shiftItems(); return out.peek(); } public Integer max() { return Math.max(in.isEmpty() ? Integer.MIN_VALUE : in.max(), out.isEmpty() ? Integer.MIN_VALUE : out.max()); } private void shiftItems() { if (!out.isEmpty()) return; while (!in.isEmpty()) { out.push(in.pop()); } } public static void main(String[] args) { MaxQueue queue = new MaxQueue(); queue.enqueue(1); System.out.println(queue.max()); queue.enqueue(2); System.out.println(queue.max()); queue.enqueue(3); System.out.println(queue.max()); queue.enqueue(4); System.out.println(queue.max()); queue.dequeue(); System.out.println(queue.max()); queue.dequeue(); System.out.println(queue.max()); queue.dequeue(); System.out.println(queue.max()); }}class MaxStack { Stack<Integer> val = new Stack<Integer>(); Stack<Integer> max = new Stack<Integer>(); public boolean isEmpty() { return val.isEmpty(); } public void push(Integer a) { val.push(a); if (max.isEmpty() || a >= max.peek()) max.push(a); } public Integer pop() { Integer out = val.pop(); if (out == max.peek()) max.pop(); return out; } public Integer peek() { return val.peek(); } public Integer max() { return max.peek(); }}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。