public interface MyStack<T> {

    public void push(T element);
    public T pop() throws  Exception;
    public int size();
    public boolean isEmpty();
}

1.用数组实现

/**
 * @author jy
 * @date 2018年6月1日
 * <p>Description: </p> 
 */
package datastruct;

import java.util.Stack;


/**
 * @author jy
 *FILO with array
 */

public class MyStackWithArray<T> implements MyStack<T>{
    private Object array[];
    private int n;//element num of stack 
    public MyStackWithArray(){
        n=0;
        array=new Object[3];
    }
    public boolean isEmpty(){
        return n==0;
    }
    public int size()
    {
        return n;
    }
    
    
    
    /**
     * @param array2
     *<p>Description: </p>  
     */
   private void resize() {
        Object temp[] = Arrays.copyOf(array, array.length * 2);

        array = temp;

    }
    
    /* (non-Javadoc)
     * @see datastruct.MyStack#push(java.lang.Object)
     */
    @Override
    public void push(T element) {
        if(n==array.length){
            resize();
        }
        array[n++]=element;
        
    }
    /* (non-Javadoc)
     * @see datastruct.MyStack#pop()
     */
    @Override
    public T pop() throws Exception {
        if(isEmpty()){
                throw new Exception("stack is empty");
        }
        T elem=(T) array[--n];
        array[n]=null;
        return elem;
    }
    
}

采坑日记，如果是数组类型，默认值是0，无法置为null

image.png

2.用链表实现

/**
 * @author jy
 * @date 2018年6月1日
 * <p>Description: </p> 
 */
package datastruct;

/**
 * @author jy
 * FILO
 *
 */
public class MyStackWithLinkedlist<T> implements MyStack<T> {
    private MyNode<T> head=null;//虚拟头部
    private int n;//element num of stack 

    public boolean isEmpty(){
        return n==0;
    }
    
    public int size(){
        return n;
    }
    /**
     * 每次都往头部的前面插入元素
     * @param e
     *<p>Description: </p>
     */
    
    public void push(T e){
        MyNode node =new MyNode();
        node.setData(e);
        node.setNext(head);
        head=node;
        n++;
        
    }
    /*
     * 弹出头部元素
     */
    public T pop() throws Exception{
        if(isEmpty()){
                throw new Exception("stack is empty");
        }
        T e=head.getData();
        head=head.getNext();
        n--;
        return e;
    }


}

Node

    

/**
 * @author jy
 * @date 2018年6月1日
 * <p>Description: </p> 
 */
package datastruct;

/**
 * @author jy
 * @param <T>
 *
 */
public class MyNode<T> {
    
    private MyNode next;
    private T data;
    
    public MyNode getNext() {
        return next;
    }
    public void setNext(MyNode next) {
        this.next = next;
    }
    public T getData() {
        return data;
    }
    public void setData(T data) {
        this.data = data;
    }
    
    

}

链表的头插法，每次往头结点的前面插入结点，并使新插入的结点为头结点。后进的先出。
测试：

/**
 * @author jy
 * @date 2018年6月4日
 * <p>Description: </p> 
 */
package datastruct;

import static org.junit.Assert.*;

import org.junit.Before;
import org.junit.BeforeClass;
import org.junit.Test;

/**
 * @author jy
 *
 */
public class MyStackWithArrayTest {
    MyStack stackWithArray;
    /**
     * @throws java.lang.Exception
     *<p>Description: </p>  
     */
    @BeforeClass
    public static void setUpBeforeClass() throws Exception {
    }

    /**
     * @throws java.lang.Exception
     *<p>Description: </p>  
     */
    @Before
    public void setUp() throws Exception {
         //stackWithArray=new MyStackWithArray();
        //stackWithArray=new MyStackWithLinkedlist();
        stackWithArray=new MyStackWithQueue();
    }



    /**
     * Test method for {@link datastruct.MyStackWithArray#push(java.lang.Object)}.
     */
    @Test
    public void testPush() {
        assertEquals(stackWithArray.isEmpty(),true);

        stackWithArray.push(1);
        assertEquals(stackWithArray.size(),1);
        stackWithArray.push(2);
        stackWithArray.push(3);
        stackWithArray.push(4);
        stackWithArray.push(5);
        assertEquals(stackWithArray.size(),5);

    }

    /**
     * Test method for {@link datastruct.MyStackWithArray#pop()}.
     */
    @Test
    public void testPop() {

        testPush();
        assertEquals(stackWithArray.pop(), 5);

        assertEquals(stackWithArray.pop(), 4);
        assertEquals(stackWithArray.pop(), 3);
        assertEquals(stackWithArray.pop(), 2);
        assertEquals(stackWithArray.pop(), 1);

        
        //stackWithArray.pop();
        
    }

}

3.用队列实现栈

/**
 * @author jy
 * @date 2018年6月4日
 * <p>Description: </p> 
 */
package datastruct;

/**
 * @author jy
 *
 */
public class MyStackWithQueue<T> implements MyStack<T> {

    MyQueue<T> queue=new MyQueueWithLinkedlist<T>();
    /* (non-Javadoc)
     * @see datastruct.MyStack#push(java.lang.Object)
     */
    @Override
    public void push(T element) {

        queue.push(element);
    }

    /* (non-Javadoc)
     * @see datastruct.MyStack#pop()
     *1->2->3  3->1->2  2->1
     */
    @Override
    public T pop() throws Exception {
        for(int i=1;i<queue.size();i++){
            queue.push(queue.pop());
        }
        return  queue.pop();
    }

    /* (non-Javadoc)
     * @see datastruct.MyStack#size()
     */
    @Override
    public int size() {
        return queue.size();
    }

    /* (non-Javadoc)
     * @see datastruct.MyStack#isEmpty()
     */
    @Override
    public boolean isEmpty() {
        return queue.isEmpty();
    }

}

push时，将队列直接入队放入队尾。pop时将队列中除了最后一个元素外的其他元素，逐个添加到队列的尾部。