腾讯微信面试题--实现时间复杂度为O(1)的栈
package 腾讯面试题;public class Stack {private int itemCount = 0;private Item minItem = null;private Item[] nextMinItem;private Item stackTop = null;private int maxSize = 100;public Stack() {nextMinItem = new Item[maxSize];}class Item {int Data;Item nextItem;public Item(int data) {this.Data = data;}}public boolean push(Item item) {if (itemCount == maxSize) {System.out.println("栈已满");return false;}itemCount++;if (minItem == null) {minItem = item;} else {if (item.Data < minItem.Data) {nextMinItem[itemCount] = minItem;minItem = item;}}item.nextItem = stackTop;stackTop = item;return true;}public boolean pop() {if (itemCount == 0) {System.out.println("栈是空的，无法出栈");return false;}if (stackTop == minItem) {minItem = nextMinItem[itemCount];}stackTop = stackTop.nextItem;itemCount--;return true;}public Item min() {if (itemCount == 0) {System.out.println("栈是空的，无最小值");return null;}return minItem;}/** * @param args */public static void main(String[] args) {// TODO Auto-generated method stubStack stack = new Stack();stack.push(stack.new Item(5));System.out.println("push:min=" + stack.min().Data+" itemCount="+stack.itemCount);stack.push(stack.new Item(4));System.out.println("push:min=" + stack.min().Data+" itemCount="+stack.itemCount);stack.push(stack.new Item(3));System.out.println("push:min=" + stack.min().Data+" itemCount="+stack.itemCount);stack.push(stack.new Item(2));System.out.println("push:min=" + stack.min().Data+" itemCount="+stack.itemCount);stack.push(stack.new Item(1));System.out.println("push:min=" + stack.min().Data+" itemCount="+stack.itemCount);stack.pop();System.out.println("pop :min=" + stack.min().Data+" itemCount="+stack.itemCount);stack.pop();System.out.println("pop :min=" + stack.min().Data+" itemCount="+stack.itemCount);stack.pop();System.out.println("pop :min=" + stack.min().Data+" itemCount="+stack.itemCount);stack.pop();System.out.println("pop :min=" + stack.min().Data+" itemCount="+stack.itemCount);stack.pop();System.out.println("栈结构为：\n|____1_____|\n|____2_____|\n|____3_____|\n|____4_____|\n|____5_____|\n");}}
push:min=5 itemCount=1push:min=4 itemCount=2push:min=3 itemCount=3push:min=2 itemCount=4push:min=1 itemCount=5pop :min=2 itemCount=4pop :min=3 itemCount=3pop :min=4 itemCount=2pop :min=5 itemCount=1栈结构为：|____1_____||____2_____||____3_____||____4_____||____5_____|
Java代码??
Java代码??
Java代码??
class Node{ T data; Node min; Node pre; Node(T data, Node pre){ this.data = data; this.pre = pre; // 更新目前为止最小的元素（包括自己） if(pre!=null && pre.min.data <= data){ this.min = pre.min; }else{ this.min = this; } }}
使用top来保存顶点
Node top;
void push(T data){ top = new Node(data=data,pre=top);}T pop(){ assert top!= null; T result = top.data; top = top.pre; return result;}T min(){ assert top!=null; return top.min.data;}