数据结构—栈 Java版

￡神魔★判官ぃ 2023-05-28 05:20 52阅读 0赞

说到栈，我们肯定会先想到后进先出（LIFO）。  
入栈：先进入的数据压入栈底，栈顶存放的是最新压入的数据。  
出栈：当需要读取数据时，从栈顶弹出数据。  
插入即为入栈（push），删除即为退栈(pop)。

不考虑内存不够以及内存大量浪费的情况时

public static void main(String[] args){ 
    	Stack stack = new Stack();
    	stack.push(23);
    	stack.push(34);
    	stack.pop();       //取出一个数据
    	stack.push(45);
    	stack.pop();
    }

public class Stack{ 
    	private int[] curr = new int[10];
    	private int num = 0;
    	public void push(int add){ 
    		curr[num] = add;
    		num++;
    	}
    	public Integer pop(){ 
    		int result = curr[num - 1];
    		num--;
    		return result;
    	}
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQxOTIwMDY1_size_16_color_FFFFFF_t_70]考虑内存不够以及内存大量浪费的情况

public class Stack{ 
    	private int[] curr = new int[20];
    	private int num = 0;
    	public void push(int add){ 
    		if(num >= curr.length){ 
    			int[] newcurr = new int[curr.length * 2];
    			for(int i = 0; i < num; i++)
    				newcurr[i] = curr[i];
    			curr = newcurr;
    		}
    		curr[num] = add;
    		num++;
    	}
    	public Integer pop(){ 
    		if(curr.length == 0)
    			return null;
    		if(num * 4 <= curr.length){ 
    			int length = curr.length / 2;
    			int[] newcurr = new int[length];
    			for(int i = 0; i < num; i++)
    				newcurr[i] = curr[i];
    			curr = newcurr;
    		}
    		int result = curr[num - 1];
    		num--;
    		return result;
    	}
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQxOTIwMDY1_size_16_color_FFFFFF_t_70 1]  
需要新申请一个合适空间，将数据压入newcurr，让curr指向新开辟的空间，回收无用空间，最终达到图一的效果。

注意：  
**栈中信息在出栈时就会被回收，  
堆里面的信息在没有指向时才会被回收，  
方法区的信息就是类的定义，程序停止才会被回收**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQxOTIwMDY1_size_16_color_FFFFFF_t_70]: /images/20230528/7e789116f2d149bc9d7de5a8f4b7b390.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQxOTIwMDY1_size_16_color_FFFFFF_t_70 1]: /images/20230528/c9636679126b443c9b9c5735288c000f.png