Java実装Stack,Queue,BinaryTree
5966 ワード
1、配列でStackを実現する:
2、配列でQueueを実現する:
3、再帰実現BinaryTree:
public class MyStack {
private int maxSize;
private Integer[] array;
private int top;
public MyStack(int maxSize) {
this.maxSize = maxSize;
this.array = new Integer[maxSize];
this.top = -1;
}
public void push(int item) {
if (isFull()) {
System.out.println("Stack is full");
} else {
array[++top] = item;
}
}
public Integer peek() {
if (isEmpty()) {
System.out.println("Stack is empty");
return null;
} else {
return array[top];
}
}
public Integer pop() {
if (isEmpty()) {
System.out.println("Stack is empty");
return null;
} else {
return array[top--];
}
}
public boolean isEmpty() {
return top == -1;
}
public boolean isFull() {
return top == maxSize - 1;
}
public static void main(String[] args) {
MyStack myStack = new MyStack(10);
myStack.push(1);
myStack.push(3);
System.out.println("peek: " + myStack.peek());
myStack.push(5);
System.out.println("pop: " + myStack.pop());
System.out.println("peek: " + myStack.peek());
myStack.push(6);
System.out.println("peek: " + myStack.peek());
System.out.println("pop: " + myStack.pop());
System.out.println("pop: " + myStack.pop());
System.out.println("pop: " + myStack.pop());
System.out.println("pop: " + myStack.pop());
}
}
2、配列でQueueを実現する:
public class MyQueue {
private int maxSize;
private Integer[] array;
private int front;
private int rear;
private int itemCount;
public MyQueue(int maxSize) {
this.maxSize = maxSize;
this.array = new Integer[maxSize];
this.front = 0;
this.rear = -1;
this.itemCount = 0;
}
public void insert(int item) {
if (isFull()) {
System.out.println("Queue is full");
} else {
if (rear == maxSize - 1) {
rear = -1;
}
array[++rear] = item;
itemCount++;
}
}
public Integer remove() {
if (isEmpty()) {
System.out.println("Queue is empty");
return null;
} else {
int temp = array[front++];
if (front == maxSize) {
front = 0;
}
itemCount--;
return temp;
}
}
public Integer peek() {
if (isEmpty()) {
System.out.println("Queue is empty");
return null;
} else {
return array[front];
}
}
public boolean isEmpty() {
return itemCount == 0;
}
public boolean isFull() {
return itemCount == maxSize;
}
public static void main(String[] args) {
MyQueue myQueue = new MyQueue(5);
myQueue.insert(1);
myQueue.insert(2);
myQueue.insert(3);
myQueue.insert(4);
myQueue.insert(5);
myQueue.insert(6);
System.out.println("peek: " + myQueue.peek());
myQueue.insert(5);
System.out.println("remove: " + myQueue.remove());
System.out.println("peek: " + myQueue.peek());
myQueue.insert(6);
System.out.println("peek: " + myQueue.peek());
System.out.println("remove: " + myQueue.remove());
System.out.println("remove: " + myQueue.remove());
System.out.println("peek: " + myQueue.peek());
System.out.println("remove: " + myQueue.remove());
System.out.println("remove: " + myQueue.remove());
}
}
3、再帰実現BinaryTree:
public class MyBinaryTree {
private static class Node {
int data;
Node left;
Node right;
public Node(int data) {
this.data = data;
this.left = null;
this.right = null;
}
}
public Node root;
public MyBinaryTree() {
root = null;
}
private Node insert(Node node, int data) {
if (node == null) {
node = new Node(data);
} else {
if (data <= node.data) {
node.left = insert(node.left, data);
} else {
node.right = insert(node.right, data);
}
}
return node;
}
public void insert(int data) {
root = insert(root, data);
}
public void insert(int[] data) {
for (int i : data) {
insert(i);
}
}
public void preOrder(Node node) {
if (node == null) {
return;
}
System.out.println(node.data);
preOrder(node.left);
preOrder(node.right);
}
public void inOrder(Node node) {
if (node == null) {
return;
}
preOrder(node.left);
System.out.println(node.data);
preOrder(node.right);
}
public void postOrder(Node node) {
if (node == null) {
return;
}
preOrder(node.left);
preOrder(node.right);
System.out.println(node.data);
}
public static void main(String[] args) {
MyBinaryTree binaryTree = new MyBinaryTree();
int[] data = { 4, 8, 7, 2, 9, 3, 1, 6, 5 };
binaryTree.insert(data);
System.out.println("preOrder:");
binaryTree.preOrder(binaryTree.root);
System.out.println("inOrder:");
binaryTree.inOrder(binaryTree.root);
System.out.println("postOrder:");
binaryTree.postOrder(binaryTree.root);
}
}