栈的简单解释和实现

        JVM(虚拟机)在启动后，会在内存较低位置建立一块区域，作为堆。并有默认的大校当不够时，自动向下延伸。会在内存较高位置建立一块区域，作为栈，当不够时，自动向上延伸。当堆和栈延伸到一起时，就会引发内存溢出错误。

        堆栈是一种数据结构，特点是堆栈中的数据先进后出，或者说后进先出。与队列相反，队列是先进先出，你可以想象堆栈是个子弹夹，先压入的子弹放在弹夹下面，后压入的子弹会在弹夹的上面，打枪或者卸子弹的时候先出上面的子弹，下面的子弹才能出来。

class ArrayStack {
	
	private int top = -1;
	private int[] stack;
	private int maxSize;

	
	public ArrayStack(int maxSize) {
		this.maxSize = maxSize;
		stack = new int[maxSize];
	}

	
	public boolean isFull() {
		return top == maxSize - 1;
	}

	
	public boolean isEmpty() {
		return top == -1;
	}

	
	public void push(int value) {
		// 先判断栈是否满了
		if (isFull()) {
			System.out.println("栈满了");
			return;
		}
		// 指针后移 添加数据
		top++;
		stack[top] = value;
	}

	
	public int pop() {
		// 先判断是否是空栈
		if (isEmpty()) {
			throw new RuntimeException("栈空");
		}
		// 返回最后一个数 让指针向前走
		int value = stack[top];
		top--;
		System.out.println("移除了" + value);
		return value;
	}

	
	public void list() {
		// 判断数组是否为空
		if (isEmpty()) {
			System.out.println("栈空");
			return;
		}
		// 让i=top 帮助去遍历 top的值不用变
		for (int i = top; i > -1; i--) {
			System.out.println(stack[i]);
		}
	}
}

class Boy {
	private int no;
	private String name;
	private Boy next;

	public Boy(int no, String name) {
		this.no = no;
		this.name = name;
	}

	public int getNo() {
		return no;
	}

	public void setNo(int no) {
		this.no = no;
	}

	public Boy getNext() {
		return next;
	}

	public void setNext(Boy next) {
		this.next = next;
	}

	@Override
	public String toString() {
		return "Boy [no=" + no + ", name=" + name + "]";
	}

}

class LinkedListStack {
	//创建节点头
	private Boy head = new Boy(0, "");

	//判断链表是否为空
	public boolean isEmpty() {
		//头节点的下一个节点为空代表链表为空
		return head.getNext() == null;
	}
	
	//去除链表的最后一个元素
	public void pop() {
		//链表为空则不执行
		if (isEmpty()) {
			System.out.println("链表为空");
			return;
		}
		//创建遍历列表的辅助节点
		Boy curBoy = head;
		//创建循环寻找最后一个节点
		while (true) {
			//当前节点的下一个节点的下一个节点为空
			//则证明 当前节点的下一个节点是最后一个节点
			if (curBoy.getNext().getNext() == null) {
				break;
			}
			//辅助节点后移
			curBoy = curBoy.getNext();
		}
		//移除当前节点的下一个节点
		//将当前节点的下一个节点设置为空
		System.out.println("移除的是"+curBoy.getNext());
		curBoy.setNext(null);
	}

	
	public void add(Boy boy) {
		//创建辅助节点来遍历链表
		Boy curBoy = head;
		//通过循环遍历找到最后一个节点添加
		while (true) {
			//加入当前节点的下一个节点为空 则这个节点为最后的节点
			if (curBoy.getNext() == null) {
				break;
			}
			//让辅助节点后移继续遍历列表
			curBoy = curBoy.getNext();
		}
		//将需要添加的男孩加到最后一个节点的后面完成添加效果
		curBoy.setNext(boy);
	}
	
	public void list() {
		// 通过辅助变量 循环遍历链表
		
		// 判断链表是否为空
		if (isEmpty()) {
			System.out.println("链表为空");
			return;
		}
		//当num != 0时 说明里面有num个男孩
		while (num != 0) {
			//男孩每次去把最后一个拿出来然后让男孩等于头结点
			Boy curBoy = head;
			//用i表示后移多少次能找到最后一个
			int i =num;
			while(i!=0) {
				curBoy = curBoy.getNext();
				i--;
			}
			//每次拿到最后一个就让num-1 去拿倒数第二个 第三个 .....
			System.out.println(curBoy);
			num--;
		}
	}
}