java手写栈

在数组中，若知道数据项的下标，便可立即访问该数据项，或者通过顺序搜索数据项，访问到数组中的各个数据项。但是栈和队列不同，它们的访问是受限制的，即在特定时刻只有一个数据项可以被读取或者被删除。众所周知，栈是先进后出，只能访问栈顶的数据，队列是先进先出，只能访问头部数据。这里不再赘述。

栈的主要机制可以用数组来实现，也可以用链表来实现，下面用数组来实现栈的基本操作：

package com.cn.test.Stack;


public class ArrayStack {

	private long[] a;//定义一个数组
    
    private int size;//栈数组的大小
    
    private int top;//栈顶
    
    //带参构造函数
    public ArrayStack(int maxSize){
    	this.size=maxSize;
    	this.a=new long[size];
    	this.top=-1; //表示空栈
    }
    
    //判断栈是否为空
    public boolean isEmpty(){
    	return (top == -1);
    }
    
    //判断栈是否已满
    public boolean isFull(){
    	return (top== size-1);
    }
    
    //入栈
    public void push(long value){
    	if(isFull()){
    		System.out.println("栈已满！");
    		return;
    	}
    	a[++top] =value;
    }
    
    //出栈 删除
    public long pop(){
    	if(isEmpty()){
    		System.out.println("栈中没有数据！");
    		return 0;
    	}
    	return a[top--];
    }
    
    //返回栈顶内容，但不删除
    public long peek(){
    	if(isEmpty()){
    		System.out.println("栈中没有数据！");
    		return 0;
    	}
    	return a[top];
    }
    
    //打印（从栈顶到栈底）
    public void display(){
    	for(int i=top; i>=0;i--){
    		System.out.println(a[i] +" ");
    	}
    	System.out.println(" ");
    }
    
    //测试
    public static void main(String[] args) throws Exception
    {
    	ArrayStack arrayStack=new ArrayStack(30);
    	arrayStack.push(3);
    	arrayStack.push(6);
    	arrayStack.push(9);
 
        System.out.println("入栈打印输出： ");
        arrayStack.display();
 
        int top=(int)arrayStack.peek();
        System.out.println("栈顶： "+top);
 
        arrayStack.pop();
        System.out.println("弹出栈顶，打印输出： ");
        arrayStack.display();

    }
}

输出结果： 数据项入栈和出栈的时间复杂度均为O(1)。这也就是说，栈操作所消耗的时间不依赖于栈中数据项的个数，因此操作时间很短。栈不需要比较和移动操作。

参考自：https://mp.weixin.qq.com/s/CEMJV9muvQDoydGHYqogWw