Java实现栈。

定义一个接口MyStack接口：

package Stack;

public interface MyStack<T> { boolean isEmpty(); int length(); boolean push(T date); T pop();}

数组实现：

package Stack;

public class ArrayStack<T> implements MyStack<T>{ private Object[] objs = new Object[16]; // size相当于游标 private int size = 0; public boolean isEmpty() { return size==0; }

@Override public int length() { // TODO Auto-generated method stub return size; }

@Override public boolean push(T date) { if(size>=objs.length){ resize(); } objs[size]=date; size++; return true; }

@Override public T pop() { if(size==0){ return null; } return (T) objs[--size]; } public void resize(){ Object[] temp = new Object[objs.length*3/2+1]; for(int i=0;i<size;i++){ temp[i]=objs[i]; objs[i] = null; } objs=temp; } public String toString(){ StringBuffer sb= new StringBuffer(); sb.append("ArrayStack:["); for(int i =0;i<size;i++){ sb.append(objs[i]); if(i!=size-1){ sb.append(","); } } sb.append("]"); return sb.toString(); }}

链表实现：

package Stack;

public class LinkStack<T> implements MyStack<T> { Node top=null; int size=0;

@Override public boolean isEmpty() { // TODO Auto-generated method stub return top==null; }

@Override public int length() { return size; }

@Override public boolean push(T date) { Node node = new Node(); node.date = date; node.node = top; top=node; size++; return true; }

@Override public T pop() { if(size!=0){ Node node = top; top=node.node; size--; return node.date; } return null; } class Node{ private Node node; private T date; }}

测试：

/** * */package Stack;

import org.junit.Test;

/** * @author zjj19960106 * */public class TestSpeed { class Person{ public Person(String name, int age) { this.name=name; this.age=age; } private String name; private int age; } @Test public void testSpeed() { MyStack<Person> stack = new ArrayStack<Person>(); int num = 10000000; long start = System.currentTimeMillis(); for (int i = 0; i < num; i++) { stack.push(new Person("xing", 25)); } long temp = System.currentTimeMillis(); System.out.println("push time: " + (temp - start)); while (stack.pop() != null) ; System.out.println("pop time: " + (System.currentTimeMillis() - temp)); } }

结果：链表的时间大于数组，栈的操作是对栈顶进行，所以使用数组也是O(1)，不会出现数组中的元素移动位置，而使用栈每个数据还有进行封装成节点，所以时间比数组长。

转载于:https://www.cnblogs.com/52zjj/p/4532604.html