数据结构&算法

package pers.chenjiahao.algorithm.quick;

/**
* 选定每个数组种最后的数字作为轴，
* 数组从前往后开始遍历，
* 如果比轴小，就不动，
* 如果大于轴承，就和轴前面的数字进行交换，
* 用换回来的数字再跟轴比，如果比轴小，就不动，
* 如果大于轴，继续跟轴前面没有交换过的数字进行交换
* 以此类推
*/
public class SimpleQuickSort {
public static void main(String[] args) {
// int[] arr ={1,6,2,9,10,11,5,8,7};
// int[] arr ={1,6,9,10,11,5,8,7};
// int[] arr ={1,6,9,10,2,5,8,7};
int[] arr ={1,6,10,8,2,5,9,7};
sort(arr,0,arr.length - 1);
print(arr);
}

static void sort(int[] arr,int start,int end){
if (start == end + 1) return;
// 排序
int retAxis = quick(arr,start,end);
if (retAxis == -1) return;
sort(arr,start,retAxis - 1);
sort(arr,retAxis + 1,end);
}

static int quick(int[] arr,int startIndex,int axisIndex) {
if (startIndex == axisIndex) return -1;
// 数组的轴
int axis = arr[axisIndex];
// 轴的前一个位置的索引
int axisBeforeIndex = axisIndex - 1;
while (startIndex != axisBeforeIndex){
if (arr[startIndex] > axis){
swap(arr,startIndex,axisBeforeIndex);
// axisBeforeIndex前移一位
axisBeforeIndex--;
// 重新校验这个数字
startIndex--;
}
startIndex++;
}
// 交换轴和axisBeforeIndex位置的数
axisBeforeIndex = arr[startIndex] > axis ? axisBeforeIndex : axisBeforeIndex + 1;
swap(arr,axisIndex,axisBeforeIndex);
// 返回现在轴的位置
return axisBeforeIndex;
}

/**
* 将轴的位置交换到合适的位置
* @param arr 传入的数组
* @param axisIndex 轴的位置
* @param axisBeforeIndex 轴在数组中合适的位置
*/
private static void swap(int[] arr, int axisIndex, int axisBeforeIndex) {
int temp = arr[axisIndex];
arr[axisIndex] = arr[axisBeforeIndex];
arr[axisBeforeIndex] = temp;
}

static void print(int[] arr){
for (int i : arr) {
System.out.print(i + " ");
}
System.out.println();
}
}

package pers.chenjiahao.algorithm.counting;

/**
* 解决问题
* 如果从100~150开始就浪费了(因为索引都是从0开始的)
*/
public class MySelfCountSortUpdate {
public static void main(String[] args) {
int[] arr = {105,105,104,101,101,100,100,103,100,102,100,104};
int min = findMin(arr);
sort(arr,min);
}

private static int findMin(int[] arr) {
int min = arr[0];
for (int i = 1; i < arr.length; i++) {
if (min > arr[i]) min = arr[i];
}
return min;
}

static void sort(int[] arr,int min){
countSort(arr,min);
}

private static void countSort(int[] arr,int min) {
// 创建一个计数数组,因为数的范围是100~105 所以计数数组的长度为6
int[] countArr = new int[6];

// 将arr中的数字全部减去做小的数
for (int i = 0; i < arr.length; i++) {
arr[i] -= min;
}
// 开始遍历数据
for (int i = 0; i < arr.length; i++) {
countArr[arr[i]]++;
}

// 创建一个与原来数组等长的数组，用来存储计数后的结果
int[] newArr = new int[arr.length];
// 将计数数组存储到新数组中
int k = 0;
int j = 0;
while (k < newArr.length){
for (int i = 0; i < countArr[j]; i++) {
newArr[k++] = j + min;
}
j++;
}
for (int i : newArr) {
System.out.print(i + " ");
}
}
}

package pers.chenjiahao.algorithm.counting;

import java.util.Arrays;

/**
* 不稳定，
* 如果从100~150开始就浪费了(因为索引都是从0开始的)
*/
public class CountSort {
public static void main(String[] args) {
int[] arr = {2,4,2,3,7,1,1,0,0,5,6,9,8,5,7,4,0,9};
System.out.println(Arrays.toString(arr));
int[] result = sort(arr);
System.out.println(Arrays.toString(result));
}

static int[] sort(int[] arr){
int[] result = new int[arr.length];

int[] count = new int[10];

for (int i = 0; i < arr.length; i++) {
count[arr[i]]++;
}

System.out.println(Arrays.toString(count));

// for (int i = 0,j = 0; i < count.length; i++) {
// while (count[i]-- > 0) result[j++] = i;
// }

// 对count数组进行累加
for (int i = 1; i < count.length; i++) {
count[i] = count[i] + count[i - 1];
}

System.out.println(Arrays.toString(count));

for (int i = arr.length - 1;i >= 0; i--) {
result[--count[arr[i]]] = arr[i];
}
return result;
}
}

// 返回元素的个数
@Override
public int getSize() {
return size;
}

// 判断线性表是否为空
@Override
public boolean isEmpty() {
return size == 0;
}

// 在线表的i位置插入元素e
@Override
public void insert(int i, Object e) {
// 判断索引值i是否越界
if (i < 0 || i > size){
throw new IndexOutOfBoundsException(i + "越界");
}
// 如果数组已满，对数组进行扩容
if (size >= elements.length){
// 数组扩容
expandSpace();
}
// 从i开始，把元素依次后移
for (int j = size; j > i; j--) {
elements[j] = elements[j-1];
}
// 把元素e存储到i位置
elements[i] = e;
// 元素的个数增加1
size++;
}

// 判断当前线性表中是否包含元素e
@Override
public boolean contains(Object e) {
return indexOf(e) >= 0;
}

// 返回元素e在线性表中第一次出现位置的索引值，如果不存在返回-1
@Override
public int indexOf(Object e) {
// 判断e是否为空
if (e == null){
// 如果线性表中，用户可能添加了null
for (int i = 0; i < size; i++) {
if (elements[i] == null){
return i;
}
}
}else {
// 遍历数组
for (int i = 0; i < size; i++) {
if (e.equals(elements[i])){
return i;
}
}
}
// 能走到这里说明元素不存在
return -1;
}

// 在线性表中删除第一个与e相同的元素
@Override
public Object remove(Object e) {
// 获取e在线性表中的索引值
int index = indexOf(e);
if (index < 0){
// 线性表中不存在元素e
return null;
}
return remove(index);
}

// 在线性表中删除指定索引值的元素
@Override
public Object remove(int i) {
// 判断i是否越界
if (i < 0 || i >= size){
throw new IndexOutOfBoundsException(i + "越界");
}
// 把要删除的元素保存起来
Object old = elements[i];
// 把i+1开始的元素，依次前移
for (int j = i; j < size - 1; j++) {
elements[j] = elements[j + 1];
}
// 把最后的元素放置为null
elements[size - 1] = null;
// 修改元素的个数
size--;
return old;
}

// 把索引值为i的元素替换为e
@Override
public Object replace(int i, Object e) {
// 判断是否越界
if (i < 0 || i >= size){
throw new IndexOutOfBoundsException(i + "越界");
}
// 保存原来的值
Object old = elements[i];
// 替换
elements[i] = e;
// 把原来的元素值返回
return old;
}

// 返回指定位置的元素
@Override
public Object get(int i) {
// 判断是否越界
if (i < 0 || i >= size){
throw new IndexOutOfBoundsException(i + "越界");
}
return elements[i];
}

// 在指定的元素前插入元素
@Override
public boolean insertBefore(Object p, Object e) {
// 先确定元素p在线性表中的位置
int index = indexOf(p);
if (index < 0){
// p元素不存在，插入不成功
return false;
}
// 插入元素
insert(index,e);
return true;
}

// 在指定的元素后插入元素
@Override
public boolean insertAfter(Object p, Object e) {
// 先确定元素p在线性表中的位置
int index = indexOf(p);
if (index < 0){
// p元素不存在，插入不成功
return false;
}
// 插入元素
insert(index + 1,e);
return true;
}

// 重写toString方法
@Override
public String toString() {
// 把线性表中每个元素连接起来，便利数组中已添加的元素
StringBuilder sb = new StringBuilder();
sb.append("[");
for (int i = 0; i < size; i++) {
sb.append(elements[i]);
if (i < size - 1){
sb.append(",");
}
}
sb.append("]");
return sb.toString();
}

// 数组扩容
private void expandSpace() {
// 定义一个更大的数组,默认按2倍大小扩容
Object[] newElements = new Object[elements.length * 2];
// 把原来数组的内容复制到新的数组中
for (int i = 0; i < elements.length; i++) {
newElements[i] = elements[i];
}
// 让原来的数组名指向新的数组
elements = newElements;
}

不需要移动元素

图解

package pers.chenjiahao.linearity.singlelinkimpl;

import pers.chenjiahao.linearity.operator.MyList;

public class MySingleLink implements MyList {
// 表示头节点
private Node head;
// 保存元素的个数
private int size;

// 返回元素的个数
@Override
public int getSize() {
return size;
}

// 判断线性表是否为空
@Override
public boolean isEmpty() {
return size == 0;
}

// 在线性表中插入元素
@Override
public void insert(int i, Object e) {
// 判断索引值是否越界
if (i < 0 || i > size){
throw new IndexOutOfBoundsException(i + "越界");
}
// 创建结点
Node newNode = new Node(e,null);
// 头节点为null的情况，线性表还没被创建,刚添加的结点就是头结点
if (head == null){
head = newNode;
}else {
// 在0位置插入结点
if (i == 0){
// 修改新节点的next 域，指向原来的头节点
newNode.next = head;
// 刚插入的节点就是新的头节点
head = newNode;
}else {
// 在其余的位置插入结点,先找到i-1这个结点
Node pNode = head;
for (int j = 1; j < i; j++) {
pNode = pNode.next;
}
// 给新结点的next先赋值 i 结点 也就是pNode的next
newNode.next = pNode.next;
// 改变i-1位置结点的next，让pNode的next结点指向newNode
pNode.next = newNode;
}
}
// 元素个数+1
size++;
}

// 判断线性表中是否包含指定的元素
@Override
public boolean contains(Object e) {
return indexOf(e) >= 0;
}

// 返回元素e在线性表中第一次出现的索引值
@Override
public int indexOf(Object e) {
// 保存元素e的索引值
int index = 0;
Node pNode = head;
while (pNode != null){
if (e == null && pNode.data == null){
return index;
}else if (e != null && e.equals(pNode.data)){
return index;
}
index++;
pNode = pNode.next;
}
return -1;
}

// 从线性表中删除第一个与e相同的元素
@Override
public Object remove(Object e) {
// 找到元素e第一次出现的位置
int index = indexOf(e);
if (index < 0){
// 元素不存在
return null;
}
return remove(index);
}

// 从线性表中删除指定索引的元素
@Override
public Object remove(int i) {
// 判断是否越界
if (i < 0 || i >= size){
throw new IndexOutOfBoundsException(i + "越界");
}
Node pNode = head;
// 删除头结点(i为0时候)
if (i == 0){
head = head.next;
size--;
return pNode.data; // 返回删除头结点的数据
}
// 删除的是中间的元素，找到i-1结点
for (int j = 1; j < i; j++) {
pNode = pNode.next;
}
// 保存删除结点的数据
Object old = pNode.next.data;
// 将i - 1 结点的next指针与改变一下(让i-1的next指向i+1结点，相当于删除了i)
pNode.next = pNode.next.next;
size--;
return old;
}

// 把线性表中i索引值位置的元素替换为e
@Override
public Object replace(int i, Object e) {
// 判断是否越界
checkIndex(i);
// 找到i结点
Node pNode = getNode(i);
// 保存一下旧的数据
Object old = pNode.data;
// 替换
pNode.data = e;
return old;
}

// 返回线性表中i索引值的元素
@Override
public Object get(int i) {
// 判断是否越界
Node pNode = getNode(i);
return pNode.data;
}

// 定义一个方法来检查索引值是否越界
private void checkIndex(int i){
if (i < 0 || i >= size){
throw new IndexOutOfBoundsException(i + "越界");
}
}

// 定义一个方法返回i索引值的元素
private Node getNode(int i){
if (i < 0 || i>= size){
return null;
}
if (i == 0){
return head;
}
// 找到i结点
Node pNode = head;
for (int j = 0; j < i; j++) {
pNode = pNode.next;
}
return pNode;
}
// 在指定的元素p的前面插入元素e
@Override
public boolean insertBefore(Object p, Object e) {
// 找p的索引位置
int index = indexOf(p);
if (index < 0){
// 元素p不存在
return false;
}
insert(index,e);
return true;
}

@Override
public boolean insertAfter(Object p, Object e) {
// 找p的索引位置
int index = indexOf(p);
if (index < 0){
// 元素p不存在
return false;
}
insert(index + 1,e);
return true;
}

// 重写toString()方法
@Override
public String toString() {
// 把链表中各个结点的数据与连接起来
StringBuilder sb = new StringBuilder();
sb.append("[");
Node pNode = head;
while (pNode != null){
sb.append(pNode.data);
// 使用逗号分割
if (pNode.next != null){
sb.append(",");
}
// 指针向后移动
pNode = pNode.next;
}
sb.append("]");
return sb.toString();
}

// 定义一个内部类表示单向链表中的结点
private class Node{
// 保存数据
Object data;
// 保存下一个结点的引用
Node next;
// 构造
public Node(Object data, Node next) {
this.data = data;
this.next = next;
}
}
}

1.getSize()

2.isEmpty()

3.insert(int i, Object e)

4.contains(Object e)

5.indexOf(Object e)

6.remove(Object e)

7.remove(int i)

8.replace(int i, Object e)

9.get(int i)

10.insertBefore(Object p, Object e)

11.insertAfter(Object p, Object e)

12.toString()

13.private void checkIndex(int i)

14.private Node getNode(int i)

*****15.private class Node

package pers.chenjiahao.linearity.singlelinkimpl.test;

import pers.chenjiahao.linearity.singlelinkimpl.MySingleLink;

/**
* 测试单向链表
*/
public class MySingleLinkTest {
public static void main(String[] args) {
// 创建链表
MySingleLink link = new MySingleLink();
// 判断链表是否为空
System.out.println(link.isEmpty()); // true
// 获取元素个数
System.out.println(link.getSize());
// 插入元素
link.insert(0,"aa");
link.insert(0,"bb");
link.insert(0,"cc");
link.insert(0,"dd");
// 直接打印输出
System.out.println(link); // [dd,cc,bb,aa]
// 判断元素是否存在
System.out.println(link.indexOf("dd")); // 0
System.out.println(link.indexOf("aa")); // 3
System.out.println(link.indexOf("xx")); // -1
System.out.println(link.contains("cc")); // true
// 删除结点
System.out.println(link.remove("xx")); // null
System.out.println(link.remove("bb")); // bb
System.out.println(link); // [dd,cc,aa]
System.out.println(link.remove(0));
System.out.println(link); // [cc,aa]
// 返回元素，元素替换
System.out.println(link.get(0)); // cc
System.out.println(link.replace(0,"CC")); // cc
System.out.println(link); // [CC,aa]
// 在指定元素的前面/后面插入元素
link.insertBefore("aa","bb");
link.insertAfter("bb","BB");
System.out.println(link); // [CC,bb,BB,aa]
MySingleLink link2 = new MySingleLink();
}
}

图解

package pers.chenjiahao.linearity.duallinkedlistimpl; import pers.chenjiahao.linearity.operator.MyList; public class MyDualLinkedList implements MyList { // 指向头结点 private Node first; // 指向尾结点 private Node last; // 保存元素的个数 private int size; // 返回元素的个数 @Override public int getSize() { return size; } // 判断链表是否为空 @Override public boolean isEmpty() { return size == 0; } // 在指定的索引值插入元素 @Override public void insert(int i, Object e) { // 判断是否越界 if (i < 0 || i > size){ throw new IndexOutOfBoundsException(i + "越界"); } // 如果i==0，在头部添加元素 if (i == 0){ addFirst(e); }else if (i == size){ // 如果i==size，表示在尾部添加元素 addLast(e); }else{ // 找到i结点，在i结点的前面插入元素 Node pNode = getNode(i); Node prevNode = pNode.prev; // 生成新的结点 Node newNode = new Node(e,prevNode,pNode); // 修改前驱结点的next指向新节点 prevNode.next = newNode; // 修改后继结点的prev指向新节点 pNode.prev = newNode; // 元素加一 size++; } } // 返回索引值对应的结点 private Node getNode(int i) { Node pNode = first; for (int j = 0; j < i; j++) { pNode = pNode.next; } return pNode; } // 判断链表中是否包含指定的元素e，如果存在返回true @Override public boolean contains(Object e) { return indexOf(e) >= 0; } // 判断元素e在链表中第一次出现的位置，如果不存在该元素，返回-1 @Override public int indexOf(Object e) { // 保存元素e在链表中的索引值 int i = 0; // 依次遍历链表中的各个结点，比较结点的元素与指定的e是否一样 if (e == null){ for(Node pNode = first; pNode != null ; pNode = pNode.next){ if (pNode.data == null){ return i; } i++; } }else{ for(Node pNode = first; pNode != null ; pNode = pNode.next){ if (e.equals(pNode.data)){ return i; } i++; } } return -1; } // 从链表中删除指定的元素 @Override public Object remove(Object e) { // 先找到元素e对应的索引值 int index = indexOf(e); if (index < 0){ return null; } return remove(index); } // 从链表中删除指定索引值的元素，并返回删除的元素 @Override public Object remove(int i) { // 判断索引值是否越界 if (i < 0 || i >= size){ throw new IndexOutOfBoundsException(i + "越界"); } // 找到i对应的结点 Node pNode = getNode(i); // 删除结点的前驱 Node prevNode = pNode.prev; // 删除结点的后继 Node nextNode = pNode.next; // 如果前驱结点为null if (prevNode == null){ // 删除的就是头结点 first = nextNode; }else { // 将prevNode中的next指向nextNode prevNode.next = nextNode; } // 如果后继节点为null if (nextNode == null){ // 删除的就是尾结点 last = prevNode; }else { // 将nextNode中的prev指向prevNode nextNode.prev = prevNode; } // 修改元素的个数 size--; return pNode.data; } // 修改指定索引值的元素，将原来的元素返回 @Override public Object replace(int i, Object e) { // 检查索引值是否越界 checkIndex(i); // 找到索引值为i的结点 Node pNode = getNode(i); // 存储原来的元素 Object oldData = pNode.data; // 修改结点的元素 pNode.data = e; return oldData; } // 返回指定索引值的元素 @Override public Object get(int i) { // 检查索引值是否越界 checkIndex(i); // 找到索引值为i的结点 return getNode(i).data; } // 在指定的元素p前面插入元素e @Override public boolean insertBefore(Object p, Object e) { // 找到p元素在哪 int index = indexOf(p); if (index < 0 ){ return false; } // 在p元素的前面插入元素e insert(index,e); return true; } // 在指定的元素后面插入元素e @Override public boolean insertAfter(Object p, Object e) { // 找到p元素在哪 int index = indexOf(p); if (index < 0 ){ return false; } // 在p元素的前面插入元素e insert(index + 1,e); return true; } // 校验是否越界的方法 private void checkIndex(int i){ if (i < 0 || i >= size){ throw new IndexOutOfBoundsException(i + "越界"); } } // 在链表中，经常会有针对头元素与尾元素的操作 // 在尾部添加元素e public void addLast(Object e) { Node pNode = last; // 生成一个新的结点 Node newNode = new Node(e,last,null); if (pNode == null){ // 既是为结点，也是头结点 first = newNode; }else { pNode.next = newNode; } last = newNode; size++; } // 在头部添加元素e public void addFirst(Object e) { // 生成一个新的结点 Node newNode = new Node(e,null,first); /* 这种写法，如果first不存在，则会产生，空指针异常 // 将原先头结点的前驱指向这个新的结点 first.prev = newNode; // 将头节点的指针指向这个新的结点 first = newNode;*/ // 修改first指向新的结点 first = newNode; Node pNode = first.next; // 刚刚插入的头结点，既是头节点，也是尾节点 if (pNode == null){ last = newNode; }else { pNode.prev = newNode; } // 元素的个数+1 size++; } // 删除第一个元素，删除头元素 public Object removeFirst(){ return remove(0); } // 删除最后一个元素，删除尾元素 public Object removeLast(){ return remove(size - 1); } // 返回头元素 public Object getFirst(){ return get(0); } // 返回尾元素 public Object getLast(){ return get(size - 1); } // 重写toString @Override public String toString() { // 依次遍历各个节点，把元素转换为字符串 StringBuilder sb = new StringBuilder(); sb.append("["); for (Node node = first; node != null ; node = node.next) { sb.append(node.data); // 元素之间使用逗号分割 if (node != last){ sb.append(","); } } sb.append("]"); return sb.toString(); } // 定义一个内部类描述双向链表的结点 private class Node{ // 保存数据域 private Object data; // 保存前驱结点 private Node prev; // 保存后继结点 private Node next; public Node(Object data, Node prev, Node next) { this.data = data; this.prev = prev; this.next = next; } } }

1.getSize()

2.isEmpty()

3.insert(int i, Object e)

4.contains(Object e)

5.indexOf(Object e)

6.remove(Object e)

7.remove(int i)

8.replace(int i, Object e)

9.get(int i)

10.insertBefore(Object p, Object e)

11.insertAfter(Object p, Object e)

12.toString()

13.private void checkIndex(int i)

14.private Node getNode(int i)

*****15.private class Node

在链表中，经常会有针对头元素与尾元素的操作

package pers.chenjiahao.linearity.duallinkedlistimpl.test; import pers.chenjiahao.linearity.duallinkedlistimpl.MyDualLinkedList; public class MyDualLinkedListTest { public static void main(String[] args) { // 创建双向链表 MyDualLinkedList linkedList = new MyDualLinkedList(); System.out.println(linkedList.getSize()); System.out.println(linkedList.isEmpty()); linkedList.insert(0,"gg"); linkedList.insert(0,"jj"); linkedList.insert(1,"dd"); linkedList.insert(3,"mm"); System.out.println(linkedList); // 测试是否包含某个元素 System.out.println(linkedList.indexOf("jj")); System.out.println(linkedList.indexOf("mm")); System.out.println(linkedList.indexOf("DD")); System.out.println(linkedList.contains("xx")); System.out.println(linkedList.contains("gg")); // 删除指定的结点 System.out.println(linkedList.remove(0)); System.out.println(linkedList); System.out.println(linkedList.remove("mm")); System.out.println(linkedList); linkedList.replace(0,"xx"); System.out.println(linkedList.get(1)); System.out.println(linkedList); linkedList.insertBefore("xx","yy"); linkedList.insertBefore("xx","oo"); System.out.println(linkedList); // [yy,oo,xx,gg] linkedList.addFirst("TT"); linkedList.addLast("MM"); System.out.println(linkedList); System.out.println(linkedList.getFirst()); System.out.println(linkedList.getLast()); System.out.println(linkedList.removeFirst()); System.out.println(linkedList.removeLast()); System.out.println(linkedList); } }

直接通过索引值访问每个元素，实现了数组元素的随机访问

每次都要从头结点或尾结点开始依次查找

需要移动大量的元素

只需要修改结点的前驱和后继指针即可，不需要移动元素

优先选择顺序存储

优先选择链式存储

package pers.chenjiahao.linearity.arraystack;

import pers.chenjiahao.linearity.stackoperator.MyStack;

/**
* 栈的顺序实现
*/
public class MyArrayStack implements MyStack {
// 定义数组来保存栈的元素
private Object[] elements;
// 栈的默认容量
private static final int DEFAULT_CAPACITY = 16;
// 栈顶指针
private int top;

// 无参构造中，对数组默认初始化
public MyArrayStack() {
elements = new Object[DEFAULT_CAPACITY];
}

// 有参构造中，指定栈的初始化大小
public MyArrayStack(int initialCapacity) {
elements = new Object[initialCapacity];
}

// 返回元素的个数
@Override
public int getSize() {
return top;
}

// 判断栈中是否为空
@Override
public boolean isEmpty() {
return top <= 0;
}

// 入栈/压栈
@Override
public void push(Object e) {
// 判断栈是否已满，如果已满，数组需要扩容
if (top >= elements.length){
// 定义一个更大的数组
Object[] newData = new Object[elements.length * 2];
// 将原来的数组的内容复制到大的数组中
for (int i = 0; i < elements.length; i++) {
newData[i] = elements[i];
}
// 让原来的数组名指向新的数组
elements = newData;
}
// 把元素存储到栈顶指针指向的位置
elements[top] = e;
// 栈顶指针上移
top++;
}

// 出栈/弹栈
@Override
public Object pop() {
// 判断栈是否为空
if (top <= 0){
throw new StackOverflowError("栈已空");
}
top--; // 栈顶指针下移
return elements[top];
}

// 返回栈顶元素,不删除
@Override
public Object peek() {
// 判断栈是否为空
if (top <= 0){
throw new StackOverflowError("栈已空");
}
return elements[top - 1];
}

// 重写toString()，从栈顶到占底输出
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("[");
// 从栈顶到占地的顺序添加各个元素
for (int i = top - 1; i >= 0; i--) {
sb.append(elements[i]);
// 元素之间用逗号分割
if (i > 0){
sb.append(",");
}
}
sb.append("]");
return sb.toString();
}
}

1.getSize()

2.isEmpty()

3.push(Object e)

4.pop()

5.peek()

6.toString()

package pers.chenjiahao.linearity.arraystack.test;

import pers.chenjiahao.linearity.arraystack.MyArrayStack;

public class MyArrayStackTest {
public static void main(String[] args) {
// 创建栈
MyArrayStack stack = new MyArrayStack();
System.out.println(stack.isEmpty()); // true
System.out.println(stack.getSize()); // 0
// 压栈
stack.push("aa");
stack.push("bb");
stack.push("cc");
stack.push("dd");
System.out.println(stack.isEmpty()); // false
System.out.println(stack.getSize()); // 4
// 重写toString方法
System.out.println(stack); // [dd,cc,bb,aa]
// 弹出栈顶元素
System.out.println(stack.peek()); // dd
// 出栈
System.out.println(stack.pop()); // dd
System.out.println(stack);
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack);
}
}

package pers.chenjiahao.linearity.linkstack;

import pers.chenjiahao.linearity.stackoperator.MyStack;

/**
* 栈的链式存储
* 注：第一个定义的结点，相当于就是栈底
*/
public class MyLinkStack implements MyStack {
// 存储栈顶的引用
private Node top;
// 保存栈中元素的个数
private int size;

// 返回栈中元素的个数
@Override
public int getSize() {
return size;
}

// 判断栈是否为空
@Override
public boolean isEmpty() {
return size == 0;
}

// 入栈/压栈
@Override
public void push(Object e) {
// 根据元素生成结点，插入到链表的头部
Node pNode = new Node(e,top);
// 修改top栈顶指针,指向新的结点
top = pNode;
// 元素个数+1
size++;
}

// 出栈/弹栈
@Override
public Object pop() {
// 判断栈是否为空
if (size < 1){
throw new StackOverflowError("栈已空");
}
// 保存原来栈顶元素
Object oldData = top.data;
// 后移栈顶指针
top = top.next;
size--;
return oldData;
}

// 返回栈顶元素
@Override
public Object peek() {
// 判断栈是否为空
if (size < 1){
throw new StackOverflowError("栈已空");
}
return top.data;
}

// 重写toString方法
@Override
public String toString() {
// 将链表中各个结点的数据给返回
StringBuilder sb = new StringBuilder();
sb.append("[");
for (Node pNode = top; pNode != null; pNode = pNode.next){
sb.append(pNode.data);
// 数据元素之间使用逗号分割
if (pNode.next != null){
sb.append(",");
}
}
sb.append("]");
return sb.toString();
}

// 定义一个内部类，描述链表中的结点
private class Node{
// 存储数据
Object data;
// 存储下个结点的引用
Node next;

public Node() {
}

public Node(Object data, Node next) {
this.data = data;
this.next = next;
}
}
}

1.getSize()

2.isEmpty()

3.push(Object e)

4.pop()

5.peek()

6.toString()

*****private class Node

package pers.chenjiahao.linearity.linkstack.test; import pers.chenjiahao.linearity.linkstack.MyLinkStack; public class MyLinkStackTest { public static void main(String[] args) { // 创建链栈 MyLinkStack stack = new MyLinkStack(); System.out.println(stack.isEmpty()); // true System.out.println(stack.getSize()); // 0 // 压栈 stack.push("ppp"); stack.push("aaa"); stack.push("xxx"); stack.push("ooo"); System.out.println(stack); // [ooo,xxx,aaa,ppp] // 出栈 System.out.println(stack.pop()); System.out.println(stack.pop()); System.out.println(stack.pop()); System.out.println(stack.pop()); System.out.println(stack); } }

package pers.chenjiahao.linearity.stackapplication.baseconversion;

import pers.chenjiahao.linearity.arraystack.MyArrayStack;

/**
* 使用栈完成进制转换
*/
public class BaseConversion {
public static void main(String[] args) {
System.out.println(convert(100,2)); // 1100100
System.out.println(convert(100,8)); // 144
// 十六进制要转换到相应的abcdef
// System.out.println(convert(100,16));
}

/**
* 把一个十进制整数num转换decimal指定的进制
* @param num 接收的十进制整数
* @param decimal 指定进制
* @return 返回num这个整数对应的decimal进制的字符串
*/
public static String convert(int num,int decimal){
// 保存余数
MyArrayStack stack = new MyArrayStack();
// 余数
int remainder = num % decimal;
while (num != 0 ){
// 余数压栈
stack.push(remainder);
num = num / decimal;
remainder = num % decimal;
}
// 出栈，余数倒序
StringBuilder sb = new StringBuilder();
while(!stack.isEmpty()){
sb.append(stack.pop());
}
return sb.toString();
}
}

读取整个表达式，
如果是左括号就直接入栈，等待与它对应的右括号出现
如果是右括号，则与当前栈顶的左括号判断是否匹配
           如果不匹配，说明表达式不合法
如果是右括号，表示栈已空，表示不合法
读完整个表达式，堆栈不空，表示有左括号没匹配上，表达式不合法；
读完整个表达式，栈是空的表示所有括号都能匹配

package pers.chenjiahao.linearity.stackapplication.bracketmatching; import pers.chenjiahao.linearity.arraystack.MyArrayStack; /** * 检测表达式中的括号是否匹配 */ public class BracketMatch { public static void main(String[] args) { System.out.println(bracketMath("([{}])")); // true System.out.println(bracketMath("([{{])")); // false System.out.println(bracketMath("([{}}])")); // false } // 检测expression表达式中的括号是否匹配 public static boolean bracketMath(String expresion){ // 定义一个栈用来保存各种左括号 MyArrayStack stack = new MyArrayStack(); // 遍历整个表达式，如果是左括号就入栈，如果是右括号就出栈,进行判断是否匹配 for (int i = 0; i < expresion.length(); i++) { // 取出表达式的每个字符 char cc = expresion.charAt(i); switch (cc){ case '(': case '[': case '{': stack.push(cc);// 左括号入栈 break; case '}': if (!stack.isEmpty() && stack.pop().equals('{')){ break; }else { return false; } case ']': if (!stack.isEmpty() && stack.pop().equals('[')){ break; }else { return false; } case ')': if (!stack.isEmpty() && stack.pop().equals('(')){ break; }else { return false; } } } // 表达式遍历完后，如果栈是空的，表示括号匹配 if (stack.isEmpty()){ return true; }else { return false; } } }

先乘除后加减

先括号内，再括号外

从左到右进行运算

4+3+(6-10+2*3)*4

7+(6-10+2*3)*4

7+(-4+2*3)*4

7+(-4+6)*4

7+2*4

7+8

15

图解

定义两个栈，一个存储操作符operator,一个存储操作数operand

读取表达式

如果是操作数就存储到operand操作数栈中

如果是操作符

遍历完整个表达式，连个栈都不为空，依次弹出操作符栈中的操作符和操作数栈中的两个操作数进行计算，把结果再存储到操作数栈中

如果操作符栈不为空，或操作数栈中的数不止一个，则表达式错误

如果操作符栈为空，操作数栈中只有一个数字，返回这个数，即计算的答案

package pers.chenjiahao.linearity.stackapplication.calculateexpression; import pers.chenjiahao.linearity.arraystack.MyArrayStack; /** * 使用栈来计算算数表达式的值 */ public class CalculateExpression { public static void main(String[] args) { String expression = "4+3+(6-10+2*3)*4"; double result = calculate(expression); System.out.println(result); } // 定义方法计算指定表达式的值 4+3+(6-10+2*3)*4 private static double calculate(String expression) { // 定义一个栈用与存储操作符 MyArrayStack operatorStack = new MyArrayStack(); // 定义一个栈用与存储操作数 MyArrayStack operandStack = new MyArrayStack(); // 遍历表达式中的操作数与操作符 for (int i = 0; i < expression.length(); i++) { // 取出每个符号 char cc = expression.charAt(i); // 如果cc是数字 if (Character.isDigit(cc)){ // 取出操作数 StringBuilder sb = new StringBuilder(); // 只要是数字就是操作数的一部分 如果这里直接取出cc的话会有问题，比如说66+55 只会取走一个6 66被分割了，所以要处理一下 while (Character.isDigit(cc)){ sb.append(cc); i++; // 判断i++是否越界 if (i >= expression.length()){ // 说明表达式结束了 break; } // 如果没有到末尾，取出下一个字符 cc = expression.charAt(i); } // 操作数入栈 operandStack.push(sb.toString()); // 修正一下i，i在while中最后判断了一次，需要退回一次 i--; // 测试一下 System.out.println(sb); }else { // 如果是操作符 // 栈为空，直接将操作符入栈 if (operatorStack.isEmpty()){ operatorStack.push(cc); continue; } // 操作符栈不为空,取出栈顶的操作符 // 栈不为空的时候需要一直判断 while (!operatorStack.isEmpty()){ char op1 = (char) operatorStack.peek(); // 判断栈中操作符与当前操作符的优先级 if (compareOperator(op1,cc) < 0){ // 当前运算符的优先级高于栈顶运算符的优先级 直接入栈 operatorStack.push(cc); break; }else if (compareOperator(op1,cc) == 0){ // 当前操作符的优先级等于栈顶运算符的优先级,只有一种情况：左一半小括号遇到右一半小括号的情况 // 栈中左一半小括号出栈 operatorStack.pop(); break; }else { // 栈顶操作符优先级高 // 取出两个操作数 // 如果操作数栈为空，也表示表达式错误 if (operandStack.isEmpty()){ throw new RuntimeException("表达式错误"); } double num1 = Double.parseDouble(operandStack.pop().toString()); // 如果操作数栈为空，也表示表达式错误 if (operandStack.isEmpty()){ throw new RuntimeException("表达式错误"); } double num2 = Double.parseDouble(operandStack.pop().toString()); // 取出栈顶操作符 char operator = (char) operatorStack.pop(); // 计算 num2 operator num1 double result = compute(num2,operator,num1); // 把结果存储到操作数栈中 operandStack.push(result); // 如果当前操作符栈为空，新的操作符应该入栈 if (operatorStack.isEmpty()){ operatorStack.push(cc); break; } } } } } // 当表达式遍历完后，如果操作符栈不为空，需要继续计算 while (!operatorStack.isEmpty()){ // 取出一个操作符 char operator = (char) operatorStack.pop(); // 取出两个操作数 // 如果操作数栈为空，也表示表达式错误 if (operandStack.isEmpty()){ throw new RuntimeException("表达式错误"); } double num1 = Double.parseDouble(operandStack.pop().toString()); // 如果操作数栈为空，也表示表达式错误 if (operandStack.isEmpty()){ throw new RuntimeException("表达式错误"); } double num2 = Double.parseDouble(operandStack.pop().toString()); // 计算 double result = compute(num2,operator,num1); // 操作数入栈 operandStack.push(result); } // 能走到这里说明操作符栈已经为空了，如果操作数栈中多余一个数，说明表达式错误 if (operandStack.getSize() > 1){ throw new RuntimeException("表达式错误"); } return Double.parseDouble(operandStack.pop().toString()); } /** * 计算num1 operator num2 表达式的值 * @param num2 先入栈的操作数 * @param operator 操作符 * @param num1 后入栈的操作数 * @return num1 operator num2 的结果 */ private static double compute(double num2, char operator, double num1) { switch (operator){ case '+': return num2 + num1; case '-': return num2 - num1; case '*': return num2 * num1; case '/': return num2 / num1; } return 0; } /** * 判断两个操作符的优先级 * @param op1 栈顶中的操作符 * @param op2 从表达式中取出的操作符 * @return 如果op1优先级高 返回整数，如果op2优先级高 返回负数 */ private static int compareOperator(char op1, char op2) { // 第一个操作符是+- 第二个操作符是*/( if (op1 == '+' || op1 == '-'){ if (op2 == '*' || op2 == '/' || op2 == '('){ // 能走都这里说明 op1 优先级低 return -1; } } // 第一个操作符是* / 第二个操作符是( if (op1 == '*' || op1 == '/'){ if (op2 == '('){ return -1; } } if (op1 == '('){ if (op2 == ')'){ return 0; }else { return -1; } } return 1; } }

少用一个存储单元，当队尾指针rear的下一个单元是队首指针front时，停止入队

(rear+1)%capacity==front时表示队列已满

front==rear时表示队列为空

图解：表示队列已满

增设一个变量表示队列为空还是满，通常使用size变量表示元素的个数

当size==0时队列为空

当size==capacity时表示队列已满

package pers.chenjiahao.linearity.arrayqueue; import pers.chenjiahao.linearity.queueoperator.MyQueue; import pers.chenjiahao.linearity.queueoperator.exception.QueueEmptyException; /** * 队列的顺序存储实现 */ public class MyArrayQueue implements MyQueue { // 定义数组存储队列中的元素 private Object[] elements; // 设置初始化容量的默认值 private static final int DEFAULT_CAPACITY = 8; // 队首 private int front; // 队尾 private int rear; // 元素的个数 private int size; // 无参构造 public MyArrayQueue() { elements = new Object[DEFAULT_CAPACITY]; } // 指定初始化容量的构造 public MyArrayQueue(int initialCapacity) { elements = new Object[initialCapacity]; } // 返回元素的个数 public int getSize(){ return size; } // 判断队列是否为空 public boolean isEmpty(){ return size == 0; } // 入队 public void enQueue(Object e){ // 如果队列已满，可以对数组扩容 if (size >= elements.length){ expandQueue(); } // 把元素存储到rear指针指向的单元 elements[rear] = e; // rear指针后移 rear = (rear + 1) % elements.length; // 元素加一 size++; } // 出队 public Object deQueue(){ // 如果队列为空 if (size <= 0){ // 抛出队列为空异常 throw new QueueEmptyException("队列为空"); } // 队列不为空，把front指向的元素返回 Object old = elements[front]; // 将front指针后移 front = (front + 1) % elements.length; // 元素个数-1 return old; } // 返回队首元素 public Object peek(){ // 队列为空，抛出异常 if (size <= 0){ // 抛出队列为空异常 throw new QueueEmptyException("队列为空"); } return elements[front]; } // 队列的数组进行扩容 private void expandQueue() { // 定义一个更大的数组 Object[] newElements = new Object[elements.length * 2]; // 把原来的数组的内容赋值到新的数组中,这里需要注意，在旧的数组中，队首不一定是从0开始的 // 需要将旧数组放到新数组的0下标开始 for (int i = 0; i < size; i++) { newElements[i] = elements[front]; front = (front + 1) % elements.length; } // 让原来的数组名，指向新的数组 elements = newElements; // 调整新的队首和队尾指针 front = 0; rear = size; } }

1.getSize()

2.isEmpty()

3.enQueue(Object e)

4.deQueue()

5.peek()

private void expandQueue()

package pers.chenjiahao.linearity.arrayqueue.test; import pers.chenjiahao.linearity.arrayqueue.MyArrayQueue; import pers.chenjiahao.linearity.queueoperator.MyQueue; /** * 测试顺序队列 */ public class MyArrayQueueTest { public static void main(String[] args) { MyQueue queue = new MyArrayQueue(); // 入队 queue.enQueue("a"); queue.enQueue("b"); queue.enQueue("C"); queue.enQueue("d"); // 返回队首元素 System.out.println(queue.peek()); // 出队 System.out.println(queue.deQueue()); System.out.println(queue.deQueue()); System.out.println(queue.deQueue()); System.out.println(queue.deQueue()); // System.out.println(queue.deQueue()); queue.enQueue("1"); queue.enQueue("2"); queue.enQueue("3"); queue.enQueue("4"); queue.enQueue("5"); queue.enQueue("6"); queue.enQueue("7"); queue.enQueue("8"); queue.enQueue("J"); queue.enQueue("Q"); queue.enQueue("K"); } }

package pers.chenjiahao.linearity.linkqueue; import pers.chenjiahao.linearity.queueoperator.MyQueue; import pers.chenjiahao.linearity.queueoperator.exception.QueueEmptyException; /** * 队列的链式存储 */ public class MyLinkQueue implements MyQueue { // 队首 private Node front; // 队尾 private Node rear; // 元素的个数 private int size; // 返回元素的个数 @Override public int getSize() { return size; } // 判断队列是否为空 @Override public boolean isEmpty() { return size == 0; } // 入队 @Override public void enQueue(Object e) { // 生成一个结点 Node newNode = new Node(e,null); // 把结点连接到队列中 if (rear == null){ // 这是添加的第一个元素，既是头结点也是尾结点 rear = newNode; front = newNode; }else { // 把结点连接到队列的尾部 rear.next = newNode; // rear 指针指向新添加的元素 rear = newNode; } // 元素个数+1 size++; } // 出队 @Override public Object deQueue() { // 判断队列是否为空 if (size <= 0){ throw new QueueEmptyException("队列为空"); } // 保存要出队的数据 Object old = front.element; // 指针下移 front = front.next; // 如果出队后队列为空，调整尾指针 if (front == null){ rear = null; } // 元素-1 size--; return old; } // 返回队首元素 @Override public Object peek() { // 判断队列是否为空 if (size <= 0){ throw new QueueEmptyException("队列为空"); } return front.element; } // 内部类表示单向链表的结点 private class Node{ Object element; Node next; public Node(Object element, Node next) { this.element = element; this.next = next; } } }

1.getSize()

2.isEmpty()

3.enQueue(Object e)

4.deQueue()

5.peek()

private class Node

package pers.chenjiahao.linearity.linkqueue.test; import pers.chenjiahao.linearity.linkqueue.MyLinkQueue; import pers.chenjiahao.linearity.queueoperator.MyQueue; public class MyLinkQueueTest { public static void main(String[] args) { MyQueue queue = new MyLinkQueue(); System.out.println(queue.getSize()); System.out.println(queue.isEmpty()); queue.enQueue("a"); queue.enQueue("b"); queue.enQueue("c"); System.out.println(queue.getSize()); System.out.println(queue.getSize()); System.out.println(queue.peek()); queue.deQueue(); System.out.println(queue.getSize()); System.out.println(queue.isEmpty()); } }

可以定义一个线性表存储树种的所有结点的信息，称为结点表，每个结点建立一个孩子表，
孩子表只存储孩子结点在数组中的存储位置，由于每个结点的孩子结点的个数是不确定的，
经常使用一个链表表示孩子之间的关系，这就是孩子表示法

在这种表示法中需要设计两种结点，一个结点表数组中表头结点，包括数据域和指向第一个孩子的指针域

还需要设计一个孩子结点，存储孩子结点的数组的下标和指向下个孩子的指针

在这种结构中，可以方便查找某个结点的孩子，也可以方便查找某个结点的兄弟，只需要访问这个结点的孩子链表即可，
如果需要查找结点的父结点，还需要遍历整棵树，可以在结点表中，即数组中的结点增加一个指向父结点的指针，
如下图所示

叶子结点只能出现最下面的一层

非叶子结点的度一定是2

在同样深度的二叉树中, 满二叉树的结点是最多的, 叶子也是最多的

叶子结点只能出现在最下两层

最下层的叶子结点集中在左侧连续的位置

倒数第二层的叶子结点一定都在右边连接的位置

如果结点的度为 1, 该结点只有左孩子

同样结点数的二叉树, 完全二叉树的深度最小

改进：为了方便找到父结点, 可以在结点上增加一个指向父结点的的指针域, 这种结点组成的
链表称为三叉链表, 

二叉树结点的结构可以设计为上图所示

以上二叉树的三叉链表如上图所示

代码