学步园

链表式：插入头部构造链表

代码如下：

package nuaa.ds;

import java.util.NoSuchElementException;

//插入头部的链表实现Stack
public class LinkedStack<T> {
	private Node<T> top;

	private int size;//current size
	public void push(T t){
		if(null==t){
			throw new IllegalArgumentException();
		}
		if(size==0){
			top = new Node<T>(t);
			size++;
		}else{
			Node<T> p = new Node<T>(t);
			p.next = top;
			top = p;
			size++;
		}
		
	}
	
	public T pop(){
		if(size==0){
			throw new NoSuchElementException();
		}
		Node<T> p = top;
		top = top.next;
		size--;
		return p.t;
	}
	
	public LinkedStack(){
		this.size = 0;
	}
	public int size(){
		return this.size;
	}
	public boolean isEmpty(){
		return size==0 ? true : false;
	}
	class Node<U>{
		U t;
		Node<U> next;
		public Node(U t) {
			super();
			this.t = t;
		}
		
	}
}

动态数组式：每次满了就double size，没什么含金量

代码如下：

package nuaa.ds;

public class Stack<T>{
	//top指示Stack最上面元素
	//Stack顶可以是数组最低项也可以是最高项
	//集合类存放的是引用或者原始类型
	//链表实现一定得头插入
	//括号匹配，左入栈，右对比然后出栈
	private int size;//总大小
	private int top;//栈顶下标
	private Object[] arrays; 
	
	public boolean push(T a){
		if(this.top==this.size-1){
			this.size = this.size*2;
			Object[] orignal = arrays;
			arrays = new Object[this.size];
			for(int i=0;i<size/2;i++)
				arrays[i] = orignal[i];
			}
		top = top+1;
		arrays[top] = a;
		return true;
		}
	
	public T pop(){
		if(top==-1)
			return null;
			top = top-1;
		return (T)arrays[top+1];
		}
	public T peek(){
		if(top==-1)
			return null;
		
		return (T)arrays[top+1];
		}
	public boolean isEmpty(){
		return top==-1 ? true : false;
	}
	public Stack(){
		this(2);
		}
	public  Stack(int size){
		this.size = size;
		this.top = -1;
		arrays =  new Object[this.size];
		}
	public int size(){
		return this.size;
		}
	
	}