模拟栈的底层实现（用数组线性表实现）

桃扇骨 2024-02-18 21:04 8阅读 0赞

由于栈只允许在栈顶进行插入与删除操作，所以用数组线性表来实现栈比用链表来实现效率更高：

接口：

package shixian;
    
    public interface MyStack<E> {
        /**返回栈的大小*/
    	public int size();
    	/**出栈操作*/
    	public E pop();
    	/**进栈操作*/
    	public void push(E e);
    	/**获得栈顶元素*/
    	public E peek();
    	/**判断栈是否为空*/
    	public boolean isEmpty();
    	/**清空栈*/
    	public void clear();
    }

抽象类：

package shixian;
    
    public abstract class MyAbstractStack<E> implements MyStack<E>{
       protected int size = 0;  //元素个数
       
       protected MyAbstractStack() {
    	
       }
       
       protected MyAbstractStack(E[] objects) {
    		for(int i = 0; i < objects.length; i++)
    			push(objects[i]);
       }   
       
       @Override
       public int size() {
    	   return size;
       }
       
       @Override
       public boolean isEmpty() {
    	   return size == 0;
       }
    }

实现：

package shixian;
    
    import java.util.ArrayList;
    
    /**数组实现栈操作*/
    public class MyStackImpl<E> extends MyAbstractStack<E>{
    	private java.util.ArrayList<E> list = new ArrayList<>();
        
        public MyStackImpl() {
    		// TODO Auto-generated constructor stub
    	}
        
        public MyStackImpl(E[] objects) {
        	//super(objects);    //想想为什么换成这样不行？ 因为list为null，调用父类构造方法时，用到了子类成员变量list，此时子类成员还未初始化。
        	for(int i = 0; i < objects.length; i++)
        		push(objects[i]);
        }
        
        /**删除栈顶元素，并返回*/
    	@Override
    	public E pop() {
    		if(size == 0) return null;
    		
    		E e = list.get(size - 1);
    		list.remove(size - 1);
    		size--;
    		return e;
    	}
    
    	/**添加元素*/
    	@Override
    	public void push(E e) {
    		list.add(e);
    		size++;
    	}
    
    	/**获得栈顶元素*/
    	@Override
    	public E peek() {
    		if(size == 0) 
    			return null;
    		else 
    		    return list.get(size-1);
    	}
    
    	/**清空栈*/
    	@Override
    	public void clear() {
    		list.clear();
    	}
    
    	@Override
    	public String toString() {
    		return list.toString();
    	}
    }

测试：

package shixian;
    
    public class TestStack {
    
    	public static void main(String[] args) {
    		MyStackImpl<String> stack = new MyStackImpl<>();
    		
    		stack.push("Apple");
    		System.out.println("(1) "+stack);
    /*		System.out.println(stack.pop());
    		System.out.println(stack.size);*/
    		stack.push("Manual");
    		System.out.println("(2) "+stack);
    		System.out.println("(3) size:"+stack.size);
    		
    		stack.push("People");
    		System.out.println("(4) "+stack);
    		System.out.println("(5) "+stack.pop());
    		System.out.println("(6) "+stack);
    
    		System.out.println("-------------------");
    		
    		Integer[] integers = {new Integer(2),new Integer(1),new Integer(4),new Integer(5),new Integer(-2)};
    		MyStackImpl<Integer> stack2 = new MyStackImpl<>(integers);
    		System.out.println("(1) isEmpty:"+stack2.isEmpty());
    		System.out.println("(2) "+stack2);
    	}
    
    /**
     * 输出
    (1) [Apple]
    (2) [Apple, Manual]
    (3) size:2
    (4) [Apple, Manual, People]
    (5) People
    (6) [Apple, Manual]
    -------------------
    (1) isEmpty:false
    (2) [2, 1, 4, 5, -2]
    
     * */
    }