最大栈跟最大队列

最大栈和最大队列

最大栈

?

具有栈的功能，并且提供O(1)的时间复杂度来获取最大值max。

?

思路：使用一个辅助栈assist来维护最大值，最大值为assist的栈顶元素。当入栈的值大于最大值时，将该值压入assist栈，相当于更新了最大值。当有元素出栈时，检查该元素是否为最大值，如果是，则assist出栈，即更新了最大值。

?

import java.util.Stack;public class MaxStack {private Stack<Integer> s;private Stack<Integer> assist;public MaxStack() {s = new Stack<Integer>();assist = new Stack<Integer>();assist.push(Integer.MIN_VALUE);}public int pop() throws Exception {if (isEmpty()) throw new Exception("empty stack");int result = s.pop();if (result == assist.peek())assist.pop();return result;}public void push(int i) {s.push(i);if (i > max()) {assist.push(i);}}public int peek() {return s.peek();}public boolean isEmpty() {return s.isEmpty();}public int max() {return assist.peek();}}

?

?

最大队列

?

具有队列的功能，并提供O(1)的时间复杂度获取最大值。

?

思路：使用两个最大栈来构成一个队列。入队的元素从s1进栈，当有元素出队时，如果s2非空，则从s2出栈。否则，将s1中的元素出栈并从s2中入栈。最大值为s1的最大值和s2的最大值中的较大值。

?

public class MaxQueue {MaxStack s1;MaxStack s2;public MaxQueue() {s1 = new MaxStack();s2 = new MaxStack();}public int max() {int result = s1.max() > s2.max() ? s1.max() : s2.max();return result;}public boolean isEmpty() {if (s1.isEmpty() && s2.isEmpty())return true;return false;}public void enqueue(int i) {s1.push(i);}public int dequeue() throws Exception {if (isEmpty())throw new Exception("is empty");if (s2.isEmpty()) {while (!s1.isEmpty()) {s2.push(s1.pop());}}return s2.pop();}}