java: 数据结构--栈(数组)

怼烎@ 2022-05-20 02:39 195阅读 0赞

栈:   规则\[ 先进来的数据,   必须最后出来\]

实现方式: ==> 新的数据, 追加到数组后面, 取数据时, 从最后的索引开始

![70][]

/**
     * 栈: 数组
     * @author wang
     *
     */
    
    public class MyStack {
    	//属性
    	int[] arr;
    	int index;
    	
    	//构造
    	public MyStack( int size) {
    		arr=new int[size];
    	}
    	
    	//方法: push()压栈 , pop()弹栈
    	public void push(int data) {
    		if(index==arr.length-1) {//数组满了
    			extArr();//数组扩容: 2倍
    		}
    		arr[index++]=data;
    	}
    	public int pop() throws Exception {
    		int popIndex=--index;
    		if(popIndex<0) {
    			throw new Exception("nothing in stack....");
    		}else {
    			int res=arr[popIndex];//取出最后一个数据
    			return res;
    		}
    	}
    	//数组扩容: 2倍
    	private void extArr() {
    		int newSize=2*arr.length;
    		int[] arr2=new int[newSize];
    		//数据转移
    		for(int i=0;i<arr.length;i++) {
    			arr2[i]=arr[i];
    		}
    		int[] tmp=arr;
    		arr=arr2;
    		tmp=null;//删除原数组
    	}
    }

测试类:

public class Test {
    	public static void main(String[] args) throws Throwable {
    		MyStack stack = new MyStack(3);
    		
    		stack.push(1);
    		stack.push(2);
    		stack.push(3);
    		stack.push(4);
    		
    		System.out.println(stack.pop());//4
    		System.out.println(stack.pop());//3
    		System.out.println(stack.pop());//2
    		System.out.println(stack.pop());//1
    		//System.out.println(stack.pop());//java.lang.Exception: nothing in stack....
    			
    		stack.push(5);
    		stack.push(6);
    		stack.push(7);
    		stack.push(8);
    		stack.push(9);
    		System.out.println(stack.pop());//9
    		System.out.println(stack.pop());//8
    		System.out.println(stack.pop());//7
    		System.out.println(stack.pop());//6
    		System.out.println(stack.pop());//5
    		
    		
    	}
    }

[70]: /images/20220520/6f9da66f3a3a48afbb661e3972560908.png