【Java实现栈】压栈，弹栈，扩容，降容...

落日映苍穹つ 2021-09-25 05:24 299阅读 0赞

import java.util.Arrays;
    
    /** * @Description: 手动实现栈 压栈 弹栈 判空 判满 * * top=1 2 * top=-1 top=0 1 top=0 1 * @Author: juwei * @Date: 2021/3/1 19:12 * @Version: 1.0 * */
    public class MyStack { 
    	private int top;   //栈顶
    	private int[] array;  //栈
    	private int capacity; //容量
    
    	/** * 初始化 * @param initCapacity */
    	MyStack(int initCapacity) { 
    		if (initCapacity > 0) { 
    			this.array = new int[initCapacity];
    			capacity = initCapacity;
    			top = -1;
    		} else if (initCapacity == 0) { 
    			this.array = new int[0];
    		} else { 
    			throw new IllegalArgumentException("Illegal param: " + initCapacity);
    		}
    	}
    
    	/** * 压栈 * @param x */
    	public void push(int x) { 
    		if (isFull()) { 
    			System.out.println("栈溢出...");
    			// System.exit(1); 准备扩容，扩容因子可以自己指定
    			System.out.println("ready resize...");
    			resize(2);
    		}
    		array[++top] = x;
    		System.out.println("压栈: " + x);
    	}
    
    	/** * 弹栈, * @return */
    	public int pop() { 
    		if (isEmpty()) { 
    			System.out.println("栈是空的...");
    			System.exit(1);
    		} else if (top < (capacity >> 1)) { 
    	    	// 当前栈顶小于容量的一半时，降容
    			downSize(1);
    		}
    		return array[top--];
    
    	}
    
    	/** * 判满 * @return */
    	public boolean isFull() { 
    		return top == capacity - 1;
    	}
    
    	/** * 判空 * @return */
    	public boolean isEmpty() { 
    		return top == -1;
    	}
    
    	/** * 栈大小 * @return */
    	public int size() { 
    		return top + 1;
    	}
    
    	/** * 扩容 */
    	public void resize(int loadFactor) { 
    		System.out.println("扩容前容量：" + this.array.length+ "," + Arrays.toString(array));
    		capacity = capacity * loadFactor;
    		this.array = Arrays.copyOf(array, capacity);
    		System.out.println("扩容后容量：" + this.array.length+ "," + Arrays.toString(array));
    	}
    
    	/** * 降容(2倍降) */
    	public void downSize(int loadFactor) { 
    		System.out.println("降容前容量：" + this.array.length + "," + Arrays.toString(array));
    		capacity = capacity >> loadFactor;
    		this.array = Arrays.copyOf(array, capacity);
    		System.out.println("降容后容量：" + this.array.length + "," + Arrays.toString(array));
    	}
    
    	/** * 打印栈内容 */
    	public void printMyStack() { 
    		for (int i = 0; i < top; i++) { 
    			System.out.print(array[i] + ",");
    		}
    	}
    
    	public static void main(String[] args) { 
    		// 初始化
    		MyStack myStack = new MyStack(5);
    
    		myStack.push(5);
    		myStack.push(6);
    		myStack.push(7);
    		System.out.println(myStack.size());
    		myStack.push(8);
    		myStack.push(9);
    		myStack.push(10);
    		myStack.push(11);
    		myStack.push(12);
    		myStack.push(13);
    		myStack.push(14);
    		myStack.pop();
    		myStack.pop();
    		myStack.pop();
    		myStack.pop();
    		myStack.pop();
    		myStack.pop();
    	}
    
    }