submit homework.875325254.2-26

Greastate · Greastate · commit cae5cf88c47e · 2017-02-25T22:57:38.000+08:00
diff --git a/group08/875325254/2-26/ArrayList.java b/group08/875325254/2-26/ArrayList.java
@@ -0,0 +1,37 @@
+import java.util.Arrays;
+
+/**
+ * Created by Great on 2017/2/25.
+ */
+public class ArrayList {
+    private final int DEFAULT_SIZE = 20;
+    int[] array = new int[DEFAULT_SIZE];
+    int size = 0;
+    public void add(int e) {
+        if (size == array.length) {
+            array = Arrays.copyOf(array, array.length + DEFAULT_SIZE);
+        }
+        array[size] = e;
+        ++size;
+    }
+
+    public Integer get(int i) {
+        if(i < 0 || i >= size) return null;
+        return array[i];
+    }
+
+    public int size() {
+        return size;
+    }
+
+    public void remove(int i) {
+        if (i < 0 || i >= size) return;
+        for (int j = i; j < size; j++) {
+            array[j] = array[j + 1];
+        }
+        --size;
+    }
+    public boolean isEmpty() {
+        return size == 0;
+    }
+}
diff --git a/group08/875325254/2-26/LinkList.java b/group08/875325254/2-26/LinkList.java
@@ -0,0 +1,73 @@
+/**
+ * Created by Great on 2017/2/24.
+ */
+public class LinkList {
+    private class Node{
+        Node next;
+        int data;
+    }
+    private Node rear;
+    private Node top;
+    private int size = 0;
+    public void add(int e) {
+        if (rear == null) {
+            rear = new Node();
+            top = rear;
+        }else {
+            rear.next = new Node();
+            rear = rear.next;
+        }
+        rear.data = e;
+        ++size;
+    }
+
+    public Integer getReciprocal(int count) {
+        if (top == null || count < 1) return null;
+        Node node = top;
+        int size = 0;
+        while( node.next != null) {
+            node = node.next;
+            size++;
+        }
+        if (size+1 < count) return null;
+        return get(size+1-count);
+    }
+
+    public Integer get(int i) {
+        if (i < 0 || i >= size) return null;
+        return getNode(i).data;
+    }
+
+    public void remove(int i) {
+        if (i < 0 || i >= size) return;
+        if (i == 0 ) {
+            top = top.next;
+            return;
+        }
+        if (i == size - 1) {
+            getNode(i - 1).next = null;
+        }
+        Node front = getNode(i - 1);
+        Node back = getNode(i + 1);
+        front.next = back;
+        --size;
+    }
+
+    private Node getNode(int i) {
+        if (i < 0 || i >= size) return null;
+        Node node = top;
+        for (int j = 0; j < size; j++) {
+            if (j == i) return node;
+            node = node.next;
+        }
+        return null;
+    }
+
+    public int size() {
+        return size;
+    }
+
+    public boolean isEmpty() {
+        return size == 0;
+    }
+}
diff --git a/group08/875325254/2-26/Queue.java b/group08/875325254/2-26/Queue.java
@@ -0,0 +1,41 @@
+import java.util.Arrays;
+
+/**
+ * Created by Great on 2017/2/23.
+ */
+public class Queue {
+    private class Node{
+        Node next;
+        int data;
+    }
+    private int size;
+    private Node front;
+    private Node rear;
+    public void add(int e) {
+        if (front == null) {
+            front = new Node();
+            rear = front;
+        }else {
+            front.next = new Node();
+            front = front.next;
+        }
+        front.data = e;
+        ++size;
+    }
+
+    public Integer poll() {
+        if (rear == null) return null;
+        int data = rear.data;
+        rear = rear.next;
+        --size;
+        return data;
+    }
+
+    public boolean isEmpty() {
+        return size == 0;
+    }
+
+    public int size() {
+        return size;
+    }
+}
diff --git a/group08/875325254/2-26/Stack.java b/group08/875325254/2-26/Stack.java
@@ -0,0 +1,29 @@
+import java.util.Arrays;
+
+/**
+ * Created by Great on 2017/2/23.
+ */
+public class Stack {
+    private final int DEFAULT_SIZE = 20;
+    private int base;
+    private int top;
+    private int[] array = new int[DEFAULT_SIZE];
+    public void push(Integer e) {
+        if (top == array.length){
+            array = Arrays.copyOf(array, array.length + DEFAULT_SIZE);
+        }
+        array[top] = e;
+        ++top;
+    }
+    public Integer pop(){
+        if (top == 0) return null;
+        top--;
+        return array[top];
+    }
+    public int size() {
+        return top;
+    }
+    public boolean isEmpty(){
+        return top == 0;
+    }
+}
diff --git a/group08/875325254/2-26/Test.java b/group08/875325254/2-26/Test.java
@@ -0,0 +1,35 @@
+import java.util.List;
+
+/**
+ * Created by Great on 2017/2/23.
+ */
+public class Test {
+    public static void main(String[] args) {
+        ArrayList arrayList = new ArrayList();
+        LinkList linkList = new LinkList();
+        Queue queue = new Queue();
+        Stack stack = new Stack();
+        for (int i = 0; i < 10; i++) {
+            arrayList.add(i);
+            linkList.add(i);
+            queue.add(i);
+            stack.push(i);
+        }
+        System.out.println("ArrayList:");
+        for (int i = 0; i < arrayList.size(); i++) {
+            System.out.println(arrayList.get(i));
+        }
+        System.out.println("LinkList:");
+        for (int i = 0; i < linkList.size(); i++) {
+            System.out.println(linkList.get(i));
+        }
+        System.out.println("Queue:");
+        while (!queue.isEmpty()) {
+            System.out.println(queue.poll());
+        }
+        System.out.println("Stack:");
+        while (!stack.isEmpty()) {
+            System.out.println(stack.pop());
+        }
+    }
+}
