简洁笔记-Java数据结构基础(3.线性结构栈和队列)

简洁笔记-Java数据结构基础(3.线性结构栈和队列) 什么是栈

栈相当于一个箱子，入栈像放书，先进后出（取第一本书出来的时候，要把上面的先取走）

栈的基本使用

自定义栈类和栈的基本使用

public class MyStack {
//	这里栈的底层使用数组来存储数据
	private int[] elements;
	
	public MyStack() {
		elements = new int[0];
	}
	
//	自定义方法1：压入元素,输入要压入的元素element
	public void push(int element) {
//		创建一个长度＋1新数组来存储旧数组的数据
		int[] newArr = new int[elements.length+1];
//		循环遍历elements赋值给newArr
		for(int i = 0;i < elements.length;i++) {
			newArr[i] = elements[i];
		}
//		newArr[elements.length]为压入的元素
		newArr[elements.length] = element;
//		把newArr地址赋给elements，完成旧数组elements的更新
		elements = newArr;
	}
	
//	自定义方法2：取出栈顶元素,返回栈顶元素
	public int pop() {
//		对栈顶元素去出的操作中，如果没有元素则抛出异常stack is empty
		if(elements.length == 0) {
			throw new RuntimeException("stack is empty");
		}
		
		//栈顶元素即是数组的最后一个元素,先用变量存储方便后面取出栈顶元素返回其值
		int element = elements[elements.length- 1];
		//创建长度-1的新数组来存储旧数组的数据，方便之后更新旧数组elements
		int[] newArr = new int[elements.length - 1];
		for(int i = 0;i < newArr.length;i++) {
			newArr[i] = elements[i];
		}
		//替换数组
		elements = newArr;
		return element;
	}
	
//	自定义方法3:查看栈顶元素
	public int peek() {
//		放回最后一个元素就是栈顶
		return elements[elements.length - 1];
	}
	
//	自定义方法4:判断栈是否为空
	public boolean isEmpty() {
		if(elements.length == 0) {
			return true;
		}
		return false;
	}
}

Test测试类用来测试MyStack

public class Test {
	public static void main(String[] args) {
//		创建一个空栈
		MyStack ms = new MyStack();
//		测试是否抛出空栈取出栈顶元素失败的异常
//		ms.pop();	//输出结果:stack is empty
		ms.push(1);	//第一入栈元素:1
		ms.push(3);	//第二个入栈元素:3
		ms.push(7);	//第三个入栈元素:7
		System.out.println(ms.pop());	//取出此时栈顶元素7
		System.out.println(ms.pop());	//取出此时栈顶元素3
		System.out.println("经过两次取出栈顶元素后,此时栈顶元素为"+ms.peek());
		System.out.println(ms.isEmpty());//判断栈是否为空
	}
}

什么是队列

队列，相当于排队买票一样，先进先出

 自定义队列类和队列的基本使用

public class MyQueue {
	private int[] elements;
	
	public MyQueue() {
		elements = new int[0];
	}
	
	//入队
	public void add(int element) {
		//创建一个长度+1的数组
		int[] newArr = new int[elements.length +1];
		for(int i = 0;i < elements.length;i++) {
			newArr[i] = elements[i];
		}
		newArr[elements.length] = element;
		//将newArr的地址值赋给elements，实现对elements的更新
		elements = newArr;
	}
	
	//出队思路：newArr[i] = elements[i+1]，把elemens[0]去掉，i+1错开赋值就行
	public int poll() {
		int element = elements[0];
		int[] newArr = new int[elements.length - 1];
		for(int i = 0;i < newArr.length;i++) {
			newArr[i] = elements[i+1];
		}
		elements = newArr;
		return element;
	}
	
//	判断队列是否为空
	public boolean isEmpty() {
		//如果数组elements长度length == 0，则为空
		return elements.length == 0;
	}
}

Test测试类用来测试MyQueue

public class Test {
	public static void main(String[] args) {
		MyQueue mq = new MyQueue();
		mq.add(11);
		mq.add(22);
		mq.add(33);	//此时11，22，33
		System.out.println(mq.poll());	//出队为11
		mq.add(44);	//此时22，33，44
		System.out.println(mq.poll());	//出队为22
		System.out.println(mq.isEmpty());	//此时为33，44
		mq.poll();
		mq.poll();
		System.out.println(mq.isEmpty());	//此时为空
	}	
}