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)，不會出現數組中的元素移動位置，而使用棧每個數據還有進行封裝成節點，所以時間比數組長。