1、数组
- 数组是用于储存有限个相同类型数据的集合。
- 数组中的各元素的存储是有先后顺序的,它们在内存中按照这个先后顺序连续存放在一起。
- 可通过数组名和下标进行数据的访问和更新。下标从0开始。
2、链表
- 链表是一种物理存储单元上非连续、非顺序的存储结构。
- 链表相较于数组,除了数据域,还增加了指针域。链表中每一个节点都包含此节点的数据和指向下一节点地址的指针。
- 对节点进行增加和删除时,只需要对涉及到的节点的指针地址进行修改,而无需变动其它的节点。
数组 | 链表 | |
内存地址 | 连续 | 不连续 |
数据长度 | 固定 | 可以动态变化 |
查询效率 | 高,随机访问 | 低,顺序访问 |
增删效率 | 低,需要移动被修改元素之后的元素 | 高,只需要修改涉及到的节点的指针 |
3、栈
java中,对栈的操作:
- 向栈中存放元素:stack.push();
- 获取栈顶元素:stack.peek();
- 删除栈顶元素:stack.pop();
栈分顺序栈和链式栈,顺序栈的实现如下:
1 public class MyStack { 2 public int[] arr;// 开辟一个栈的空间 3 public int arrSize;// 栈实际用的长度 4 5 public MyStack() { 6 this.arr = new int[10];// 设置栈的空间为10个元素的空间 7 } 8 9 // 栈中存放元素要判断栈是否为满 10 public boolean isFull() { 11 // 数据个数=长度 12 if (this.arrSize == this.arr.length) { 13 return true; 14 } 15 return false; 16 } 17 18 public void push(int item) { 19 // 如果栈满,扩容 20 if (isFull()) { 21 this.arr = Arrays.copyOf(this.arr, 3 * arr.length); 22 } 23 // 没满,存放到数组的最后位置 24 this.arr[this.arrSize] = item; 25 this.arrSize++; 26 } 27 28 // pop删除栈顶元素要判断栈是否为空 29 public boolean empty() { 30 // 数据个数为空时 31 return this.arrSize == 0; 32 } 33 34 public int pop() throws RuntimeException { 35 if (empty()) { 36 throw new RuntimeException("栈空"); 37 } 38 int val = this.arr[this.arrSize - 1]; 39 this.arrSize--; 40 return val; 41 } 42 43 // 获取栈顶元素 44 public int peek() { 45 if (empty()) { 46 throw new RuntimeException("栈空"); 47 } 48 return this.arr[this.arrSize - 1]; 49 } 50 51 public static void main(String[] args) { 52 // TODO Auto-generated method stub 53 MyStack myStack = new MyStack(); 54 System.out.println(myStack.arrSize);// 栈实际长度 55 System.out.println(myStack.arr.length);// 数组长度 56 myStack.push(1); 57 myStack.push(2); 58 myStack.push(3); 59 System.out.println(myStack.peek());// 获取栈顶元素 但是不删除 结果为3 60 System.out.println(myStack.pop());// 弹出栈顶元素 删除 结果为3 61 System.out.println(myStack.peek());// 获取栈顶元素 但是不删除 结果为2 62 System.out.println(myStack.empty());// 结果为false 63 System.out.println(myStack.pop());// 2 64 System.out.println(myStack.pop());// 1 65 System.out.println(myStack.pop());// 证明为空报异常 66 } 67 68 }
4、队列
- 一个先入先出(FIFO)的数据结构
- 只允许在队尾插入数据,在队头删除数据
4.1顺序队列
- 静态分配或动态申请一片连续的存储空间,并设置两个指针进行管理。一个是队头指针front,它指向队头元素;另一个是队尾指针rear,它指向下一个入队元素的存储位置。
- 每次在队尾插入一个元素是,rear增1;每次在队头删除一个元素时,front增1。随着插入和删除操作的进行,队列所占的存储空间也在为队列结构所分配的连续空间中移动。
- 当rear增加到指向分配的连续空间之外时,队列无法再插入新元素,但这时往往还有大量可用空间未被占用。
4.2循环队列
为了使队列空间能重复使用,往往对顺序队列稍加改进:无论插入或删除,一旦rear指针增1或front指针增1 时超出了所分配的队列空间,就让它指向这片连续空间的起始位置。
可用取余运算rear%MaxSize和front%MaxSize来实现。
在循环队列中,当队列为空时,有front=rear,而当所有队列空间全占满时,也有front=rear。为了区别这两种情况,规定循环队列最多只能有MaxSize-1个元素,当循环队列中只剩下一个空存储单元时,队列就已经满了。因此,队列判空的条件时front=rear,而队列判满的条件时front=(rear+1)%MaxSize。
Java对队列的操作:
Queue是java中实现队列的接口,它总共只有6个方法,如下:
1)压入元素(添加):add()、offer()
相同:未超出容量,从队尾压入元素,返回压入的那个元素。
区别:在超出容量时,add()方法会对抛出异常,offer()返回false
2)弹出元素(删除):remove()、poll()
相同:容量大于0的时候,删除并返回队头被删除的那个元素。
区别:在容量为0的时候,remove()会抛出异常,poll()返回false
3)获取队头元素(不删除):element()、peek()
相同:容量大于0的时候,都返回队头元素。但是不删除。
区别:容量为0的时候,element()会抛出异常,peek()返回null。
标签:arr,删除,队列,元素,链表,myStack,数据结构,public From: https://www.cnblogs.com/coooookie/p/17411477.html