目录
二叉树的实现
链表的实现
栈的实现
堆的实现
堆的数组实现
堆的集合实现
两个栈实现堆
二叉树的实现
package binarytree;
public class TreeNode {
public int value;
public TreeNode leftTreeNode;
public TreeNode rightTreeNode;
public TreeNode(int value) {
this.value = value;
}
public String toString() {
return "TreeNode{value=" + this.value + ", leftTreeNode=" + this.leftTreeNode + ", rightTreeNode=" + this.rightTreeNode + '}';
}
}
package binarytree;
public class Test {
public static void main(String[] args) {
TreeNode node1 = new TreeNode(5);
TreeNode node2 = new TreeNode(4);
TreeNode node3 = new TreeNode(7);
TreeNode node4 = new TreeNode(6);
node1.leftTreeNode = node2;
node1.rightTreeNode = node3;
node3.leftTreeNode = node4;
System.out.println(node1);
}
}
测试结果
TreeNode{value=5, leftTreeNode=TreeNode{value=4, leftTreeNode=null, rightTreeNode=null}, rightTreeNode=TreeNode{value=7, leftTreeNode=TreeNode{value=6, leftTreeNode=null, rightTreeNode=null}, rightTreeNode=null}}
Process finished with exit code 0
链表的实现
package link;
public class ListNode {
int value;
ListNode next;
public ListNode(int value) {
this.value = value;
}
public String toString() {
return "ListNode{value=" + this.value + ", next=" + this.next + '}';
}
}
package link;
public class Test {
public static void main(String[] args) {
ListNode node1 = new ListNode(1);
ListNode node2 = new ListNode(5);
ListNode node3 = new ListNode(9);
node1.next = node2;
node2.next = node3;
System.out.println(node1);
}
}
测试结果
ListNode{value=1, next=ListNode{value=5, next=ListNode{value=9, next=null}}}
Process finished with exit code 0
栈的实现
栈的数组实现
package stack;
public class StackArray {
private E[] arr = (E[])(new Object[12]);
private int flag = 0;
public StackArray() {
}
public void add(E x) {
this.arr[this.flag] = x;
++this.flag;
if (flag == arr.length) { //扩容之后
E[] brr = (E[])(new Object[arr.length * 2]);
for(int i = 0; i < flag; ++i) {
arr[i] = brr[i];
}
arr = brr;
System.out.println("栈已满，不能放入");
}
}
public E get() {
if (flag == 0) {
System.out.println("栈已空");
return null;
} else {
E result = arr[flag - 1];
--flag;
return result;
}
}
}
package stack;
public class TestArray {
public static void main(String[] args) {
StackArray x1 = new StackArray();
Integer i;
for(i = 0; i < 10; i = i + 1) {
x1.add(i);
}
for(i = 0; i < 15; i = i + 1) {
System.out.print(x1.get() + " ");
}
}
}
9 8 7 6 5 4 3 2 1 0 栈已空
null 栈已空
null 栈已空
null 栈已空
null 栈已空
null
Process finished with exit code 0
栈的链表实现
package stack;
public class StackNode {
class Node {
private T t;
private Node next;
}
private Node head;
//构造函数初始化头指针
Stacklink() {
head = null;
}
//入栈
public void push(T t) {
if (t == null) {
throw new NullPointerException("参数不能为空");
}
if (head == null) {
head = new Node();
head.t = t;
head.next = null;
} else {
Node temp = head;
head = new Node<>();
head.t = t;
head.next = temp;
}
}
//出栈
public T pop() {
T t = head.t;
head = head.next;
return t;
}
}
package stack;
public class Testlink {
public static void main(String[] args) {
StackNode stack = new StackNode();
stack.push("useful");
stack.push("is ");
stack.push("Java ");
System.out.print(stack.pop());
System.out.print(stack.pop());
System.out.print(stack.pop());
}
}
Java is useful
Process finished with exit code 0
堆的实现
堆的数组实现
package queue;
public class QueueArray {
int[] a = new int[5];
int i = 1; //数组下标
//入队
public void in(int m) {
a[i++] = m;
}
//出队
public int out() {
int index = 0;
int temp = a[1];
for (int j = 1; j < i; j++) {
a[j - 1] = a[j];
index++;
}
i = index;
return temp;
}
}
package queue;
public class TestArray {
public static void main(String[] args) {
//测试队列
System.out.println("数组测试队列：");
QueueArray queue = new QueueArray();
queue.in(1);
queue.in(2);
queue.in(3);
System.out.println(queue.out());
System.out.println(queue.out());
queue.in(4);
System.out.println(queue.out());
System.out.println(queue.out());
queue.in(5);
System.out.println(queue.out());
}
}
9 8 7 6 5 4 3 2 1 0 栈已空
null 栈已空
null 栈已空
null 栈已空
null 栈已空
null
Process finished with exit code 0
Java is useful
Process finished with exit code 0
堆的数组实现
package queue;
public class QueueArray {
int[] a = new int[5];
int i = 1; //数组下标
//入队
public void in(int m) {
a[i++] = m;
}
//出队
public int out() {
int index = 0;
int temp = a[1];
for (int j = 1; j < i; j++) {
a[j - 1] = a[j];
index++;
}
i = index;
return temp;
}
}
package queue;
public class TestArray {
public static void main(String[] args) {
//测试队列
System.out.println("数组测试队列：");
QueueArray queue = new QueueArray();
queue.in(1);
queue.in(2);
queue.in(3);
System.out.println(queue.out());
System.out.println(queue.out());
queue.in(4);
System.out.println(queue.out());
System.out.println(queue.out());
queue.in(5);
System.out.println(queue.out());
}
}
测试结果
数组实现测试队列：
1
2
3
4
5Process finished with exit code 0
堆的集合实现
package queue;
import java.util.ArrayList;
import java.util.List;
public class QueueList {
List list = new ArrayList();
int index = 0; //下标
//入队
public void in(int n){
list.add(n);
index++;
}
//出队
public int out(){
if(!list.isEmpty()){
index--;
return list.remove(0);
}
return -1;
}
}
package queue;
public class TestList {
public static void main(String[] args) {
//测试队列
System.out.println("集合实现测试队列：");
QueueList queue = new QueueList();
queue.in(1);
queue.in(2);
queue.in(3);
System.out.println(queue.out());
System.out.println(queue.out());
queue.in(4);
System.out.println(queue.out());
System.out.println(queue.out());
queue.in(5);
System.out.println(queue.out());
}
}
测试结果
集合实现测试队列：
1
2
3
4
5Process finished with exit code 0
两个栈实现堆
队列的主要操作有两个入队操作和出队操作，先进先出
入队的操作和入栈的操作类似，而出队操作则是先进去的元素先出队，而栈则是栈顶元素先出，即后入栈的先出栈
假设两个栈A和栈B，A主要用来处理入队操作，B用于处理出队操作。入队操作和入栈操作类似，
直接将元素压入栈即可。出队的时候，实现我们假设栈B为空，则要把栈A的第一个元素（即栈底元素）弹出，需要将A中元素逆转过来，所以要先把栈A的元素全部出栈，并按顺序压入栈B中，这样每次栈B弹出的栈顶元素就是栈A相对应的栈底元素，就是出队操作。
若B不为空，则代表之前从A复制过来的元素还没有完全出栈，要出栈的时候直接弹出即可。若栈B的元素都弹出来了，就需要从A中补充。
入队：将元素压入栈A
出队：判断栈B是否为空，如果为空，则将栈A中所有元素pop，并push进栈B，栈B出栈；如果不为空，栈B将剩余元素出栈。
package queue;
import java.util.Stack;
public class QueueStack {
Stack stackA = new Stack();
Stack stackB = new Stack();
//入队
public void in(int n) {
stackA.push(n);
}
//出队
public int out() {
if(stackB.isEmpty()){
while (stackA.size() > 0) {
stackB.push(stackA.pop());
}
}
return stackB.pop();
}
}
package queue;
public class TestStack {
public static void main(String[] args) {
System.out.println("两个堆栈实现一个队列：");
QueueStack queue = new QueueStack();
queue.in(1);
queue.in(2);
queue.in(3);
System.out.println(queue.out());
System.out.println(queue.out());
queue.in(4);
System.out.println(queue.out());
System.out.println(queue.out());
queue.in(5);
System.out.println(queue.out());
}
}
测试结果
两个堆栈实现一个队列：
1
2
3
4
5Process finished with exit code 0
