设计包含max函数的栈
package org.jf.alg;/** * * 算法描述：一个栈stack，具有push和pop操作，其时间复杂度皆为O(1)。设计算法max操作，求栈中的最大值，该操作的时间复杂度也要求为O(1)。可以修改栈的存储方式，push，pop的操作，但是要保证O(1)的时间复杂度，空间时间复杂度无要求。链表存储， 当然数组存储也可以 * @author junfeng.chen * */public class Pstack<T extends Comparable> {private Node head;private int size ;public void push(T data){Node node = new Node();node.data = data;if(head==null){head = node;head.max = data;}else{if(head.max.compareTo(data)>0)node.max = head.max;elsenode.max = data;node.next = head;head = node;}size++;}public T pop(){if(head==null)throw new RuntimeException("Stack is empty");T data = head.data;if(size==1)head = null;elsehead = head.next;size --;return data;}public boolean isEmpty(){return size==0;}public int size(){return size;}public T peek(){if(size==0)return null;return head.data;}public T peekMax(){if(size == 0)return null;return head.max;}class Node{T data;T max;Node next;}}