线性表之顺序存储

1.顺序表

package com.itheima.a_x;

public class MyArray {

	// 用于存储数据的数组
	private int[] elements;

	public MyArray() {
		elements = new int[0];
	}

	// 在数组末尾添加一个元素
	public void add(int element) {
		// 创建一个新数组
		int[] newArray = new int[elements.length + 1];
		// 把原数组的元素复制到新数组
		for (int i = 0; i < elements.length; i++) {
			newArray[i] = elements[i];
		}
		// 把添加的新元素放入新数组中
		newArray[elements.length] = element;
		// 使用新数组替换旧数组
		elements = newArray;
	}

	// 删除数组中的元素
	public void delete(int index) {
		// 判断下标是否越界
		if (index < 0 || index > elements.length - 1) {
			throw new RuntimeException("下标越界");
		}
		// 创建一个新的数组，长度为原数组的长度-1
		int[] newArray = new int[elements.length - 1];
		for (int i = 0; i < newArray.length; i++) {
			// 想要删除的元素前面的元素
			if (i < index) {
				newArray[i] = elements[i];
				// 想要删除元素后面的元素
			} else {
				newArray[i] = elements[i + 1];
			}
		}
		elements = newArray;
	}

	// 插入一个元素到指定位置
	public void insert(int index, int element) {
		// 创建一个新数组,长度为原数组+1
		int[] newArray = new int[elements.length + 1];
		for (int i = 0; i < newArray.length; i++) {
			// 目标位置之前的元素
			if (i < index) {
				newArray[i] = elements[i];
			} else {
				newArray[i + 1] = elements[i];
			}
			// 插入新元素
			newArray[index] = element;
		}

	}

	// 替换指定位置的元素
	public void set(int index, int element) {
		elements[index] = element;
	}

	// 取出指定元素
	public int get(int index) {
		return elements[index];
	}

	// 打印所有元素
	public void show() {
		for (int i = 0; i < elements.length; i++) {
			System.out.print(elements[i] + "  ");
		}
		System.out.println();
	}

	// 获取数组的长度
	public int size() {
		return elements.length;
	}

}

2.顺序栈

package com.itheima.a_x;

public class MyStack {
	// 栈的底层我们用数组存储数据
	int[] elements;

	public MyStack() {
		elements = new int[0];
	}

	// 入栈
	public void push(int element) {
		// 创建一个新数组
		int[] newArray = new int[elements.length + 1];
		// 把原数组中的元素复制到新数组中
		for (int i = 0; i < elements.length; i++) {
			newArray[i] = elements[i];
		}
		// 把添加的元素放入新数组中去
		newArray[newArray.length - 1] = element;
		// 使用新数组替换旧数组
		elements = newArray;
	}

	// 出栈
	public int pop() {
		if (elements.length == 0) {
			throw new RuntimeException("stack is empty");
		}
		// 创建一个新数组
		int[] newArray = new int[elements.length - 1];
		// 取出栈顶元素
		int element = elements[elements.length - 1];
		// 将原数组（除了最后一个元素）放入新数组
		for (int i = 0; i < newArray.length; i++) {
			newArray[i] = elements[i];
		}
		// 使用新数组替换原数组
		elements = newArray;
		// 返回栈顶元素
		return element;
	}

	// 查看栈顶元素
	public int peek() {
		return elements[elements.length - 1];
	}

	// 判断栈是否为空
	public boolean isEmpty() {
		return elements.length == 0;
	}

}

3.顺序队

package com.itheima.a_x;

public class MyQueue {

	// 队的底层我们用数组存储数据
	int[] elements;

	public MyQueue() {
		elements = new int[0];
	}

	// 入队
	public void push(int element) {
		// 创建一个新数组
		int[] newArray = new int[elements.length + 1];
		// 把原数组中的元素复制到新数组中
		for (int i = 0; i < elements.length; i++) {
			newArray[i] = elements[i];
		}
		// 把添加的元素放入新数组中去
		newArray[newArray.length - 1] = element;
		// 使用新数组替换旧数组
		elements = newArray;
	}

	// 出队
	public int poll() {
		if (elements.length == 0) {
			throw new RuntimeException("queue is empty");
		}
		// 创建一个新数组
		int[] newArray = new int[elements.length - 1];
		// 取出队顶元素
		int element = elements[0];
		// 将原数组（除了第一个元素）放入新数组
		for (int i = 0; i < newArray.length; i++) {
			newArray[i] = elements[i + 1];
		}
		// 替换数组
		elements = newArray;
		// 返回队顶元素
		return element;
	}

	// 长度
	public int size() {
		return elements.length;
	}

	// 判断栈是否为空
	public boolean isEmpty() {
		return elements.length == 0;
	}

}