Java实现一个简单的栈结构---Strack

电玩女神 2022-06-06 10:08 206阅读 0赞

栈是数据结构的一种，其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。

之前我觉得栈是一个非常难于理解的数据结构，其实不然，很多的时候真的是自己对于定义不清不楚，遇到想不通的问题便放弃了，对于实现一个简单的栈结构，我们首先要明白采用什么顺序表结构作为底层的实现，笔者这里采用的是基于数组的栈结构。实现一个栈，我们要从定义入手：

（1）仅允许在表的一端进行插入和删除，这意味着我们需要一个指针变量，用来代表这一端。

（2）我们采用的是基于数据的栈，那么我还还需要定义一个数组来包裹我们的数据对象

（3）栈的初始大小，最大值等等

清楚了上面的步骤，我觉得就可以自己思考怎么去实现了，下面我们通过代码来看看：

public class Stack<E> {
    	
    	private int max_size = 16;//栈容量(最大值)
    	
    	private int top = -1;//栈顶指针
    	
    	private Object[] data;//栈数据
    	
    	private double opcatity = 0.75;//负载因子
    	
    	public Stack(){
    		this(10);
    	}
    	public Stack(int size){
    		if(size<0){
    			throw new IllegalArgumentException("栈的初始大小不能小于0"+size);
    		}
    		if(size>max_size){
    			max_size = max_size + (int)(max_size*opcatity);
    		}
    		max_size = size;
    		data = new Object[max_size];
    	}
    	public E push(E e){
    		if(top>this.max_size-1){
    			throw new RuntimeException("栈已满");
    		}
    		E obj = e;
    		data[++top] = e;
    		return obj;
    	}
    	public E pop(){
    		if(top==-1){
    			throw new RuntimeException("栈为空");
    		}
    		return (E) data[top--];
    	}
    	public E search(int index){
    		if(index>this.max_size-1||index<0){
    			throw new RuntimeException("查找不在范围之内");
    		}
    		int i = 0;
    		while(index!=i){
    			i++;
    		}
    		return (E) data[i];
    	}
    }

然后我们来测试一下：

public class Main {
    	public static void main(String[] args) {
    		Stack stack = new Stack(10);
    		
    		 for(int i=0;i<10;i++)  
    	        {  
    			 	stack.push(i);  
    	        }  
    		 for(int i=0;i<10;i++){
    			 System.out.println(stack.pop());
    		 }
    	        
    	}
    }

结果：

9  
8  
7  
6  
5  
4  
3  
2  
1  
0  
就这样就实现了一个简单的栈，是不是很简单，其实关键在于理解好定义。