数据结构线性表初学--单链表、队列、栈的java使用数组实现

21.04.19java小计

数据结构线性表初学–单链表、队列、栈的java使用数组j实现
如何在java中通过数组作为容器 实现线性表的单链表、队列和栈

单链表

不同于数组，在链表在内存中并不是物理连续的，可以说是逻辑连续，每个节点含有一个data，通过每个节点的next指向下一个节点的地址。因为这个原因，使得我们的链表在进行增删操作时效率大大超出数组，但是查询（也就是数组的寻址）效率会降低。
具体实现过程：

1.创建泛型类MyLink
(1)属性 int size 标识链表长度
(2)Node head 赋值为null 初始化一个首节点变量为空

2.创建泛型类 Node类
(1)T element 记录节点要保存的数据
(2) Node next; 指向下一个节点
(3)设置构造函数 setter getter

3.通过索引值 获取对应节点的 泛型方法node(int index)
4.判断索引是否越界的方法 rangIndexCheck(int index)
5.增:向链表的末尾加上新节点 泛型方法 add(T element)
6.增：向链表的某个索引输出加上新节点 方法add(T element, int index)
7.删：删除index对应位置的节点方法remove(int index)

下面展示 单链表具体实现代码。

// public class MyQueue {
    private int size;//容器大小
    private int[] queue;//queue数组作为容器存放队列数据
    private int head;//队头位置
    private int end;//队尾位置

    public MyQueue(int size) {
        this.size = size;
        queue = new int[size];
        head = end = 0;
    }

    //判断队列是否是满的方法
    public boolean isFull() {
        return next(end) == head;
    }

    //判断队列是否为空的方法
    public boolean isEmpty() {
        return end == head;
    }

    //入队方法
    public void offer(int element) {
        if (isFull()) {
            throw new IllegalStateException("队列已满，不能添加新数据");
        }
        queue[end] = element;
        end = next(end);
    }

    //出队方法
    public int poll() {
        if (isEmpty()) {
            throw new IllegalStateException("队列是空的，不能拿出数据");
        }
        int value = queue[head];
        head = next(head);
        return value;

    }

    //向下一位移动的方法
    public int next(int value) {
        return (value + 1) % size;
    }

    //打印输出方法
    public void print() {
        if (isEmpty()) {
            return;
        }
        int cur = head;
        while (cur != end) {
            System.out.println(queue[cur]);
            cur = next(cur);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

//public class MyQueue {
    private int size;//容器大小
    private int[] queue;//queue数组作为容器存放队列数据
    private int head;//队头位置
    private int end;//队尾位置

    public MyQueue(int size) {
        this.size = size;
        queue = new int[size];
        head = end = 0;
    }

    //判断队列是否是满的方法
    public boolean isFull() {
        return next(end) == head;
    }

    //判断队列是否为空的方法
    public boolean isEmpty() {
        return end == head;
    }

    //入队方法
    public void offer(int element) {
        if (isFull()) {
            throw new IllegalStateException("队列已满，不能添加新数据");
        }
        queue[end] = element;
        end = next(end);
    }

    //出队方法
    public int poll() {
        if (isEmpty()) {
            throw new IllegalStateException("队列是空的，不能拿出数据");
        }
        int value = queue[head];
        head = next(head);
        return value;

    }

    //向下一位移动的方法
    public int next(int value) {
        return (value + 1) % size;
    }

    //打印输出方法
    public void print() {
        if (isEmpty()) {
            return;
        }
        int cur = head;
        while (cur != end) {
            System.out.println(queue[cur]);
            cur = next(cur);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

栈

栈都有啥？ 一个栈顶 top 一个栈底 BOTTOM
我们都知道栈的特点：先入后出 后入先出
具体实现过程：

1.栈类MyStack
(1)属性 int[] stack; 用于保存栈数据的数组
(2)属性 栈底 栈顶 int BOTTOM=0 int top=0
(3)属性 元素数量 int size
(4)构造方法 需要传size参数
(5)压栈方法 push(int element){}
(6)弹栈方法 pop(){}
(7)是否满栈方法 isFull(){}
(8)是否空栈方法 isEmpty(){}
(9)打印输出方法 print(){}
①方法中定义一个cur
下面展示 栈具体实现代码。

public class MyStack {
    private int top = 0;//栈顶
    private int BOTTOM = 0;//栈底
    private int[] stack;//用于保存栈数据的数组
    private int size;

    public MyStack(int size) {
        this.size = size;
        stack=new int[size];
    }

    //判断是否是满栈的方法
    public boolean isFull() {
        return top == size;
    }

    //判断是否是空栈的方法
    public boolean isEmpty() {
        return top == BOTTOM;
    }

    //压栈方法
    public void push(int element) {
        if (isFull()) {
            throw new IllegalStateException("栈已满，不能继续压栈");
        } else {
            stack[top] = element;
            top++;
        }
    }
    //弹栈方法
    public int pop(){
        if (isEmpty()) {
            throw new IllegalStateException("栈是空的，不能弹出数据");
        }else{
            top--;
            return stack[top];
        }
    }
    //打印输出方法
    public void print(){
        int cur=top;
        for (int i = cur-1; i >=BOTTOM ; i--) {
            System.out.println(stack[i]);
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

public class MyStack {
    private int top = 0;//栈顶
    private int BOTTOM = 0;//栈底
    private int[] stack;//用于保存栈数据的数组
    private int size;

    public MyStack(int size) {
        this.size = size;
        stack=new int[size];
    }

    //判断是否是满栈的方法
    public boolean isFull() {
        return top == size;
    }

    //判断是否是空栈的方法
    public boolean isEmpty() {
        return top == BOTTOM;
    }

    //压栈方法
    public void push(int element) {
        if (isFull()) {
            throw new IllegalStateException("栈已满，不能继续压栈");
        } else {
            stack[top] = element;
            top++;
        }
    }
    //弹栈方法
    public int pop(){
        if (isEmpty()) {
            throw new IllegalStateException("栈是空的，不能弹出数据");
        }else{
            top--;
            return stack[top];
        }
    }
    //打印输出方法
    public void print(){
        int cur=top;
        for (int i = cur-1; i >=BOTTOM ; i--) {
            System.out.println(stack[i]);
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

队列

一个队列中包含着 一个队头 一个队尾
特点先进先出
具体实现过程：
下面展示 环形队列具体实现代码。

public class MyQueue {
    private int size;//容器大小
    private int[] queue;//queue数组作为容器存放队列数据
    private int head;//队头位置
    private int end;//队尾位置

    public MyQueue(int size) {
        this.size = size;
        queue = new int[size];
        head = end = 0;
    }

    //判断队列是否是满的方法
    public boolean isFull() {
        return next(end) == head;
    }

    //判断队列是否为空的方法
    public boolean isEmpty() {
        return end == head;
    }

    //入队方法
    public void offer(int element) {
        if (isFull()) {
            throw new IllegalStateException("队列已满，不能添加新数据");
        }
        queue[end] = element;
        end = next(end);
    }

    //出队方法
    public int poll() {
        if (isEmpty()) {
            throw new IllegalStateException("队列是空的，不能拿出数据");
        }
        int value = queue[head];
        head = next(head);
        return value;

    }

    //向下一位移动的方法
    public int next(int value) {
        return (value + 1) % size;
    }

    //打印输出方法
    public void print() {
        if (isEmpty()) {
            return;
        }
        int cur = head;
        while (cur != end) {
            System.out.println(queue[cur]);
            cur = next(cur);
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

public class MyQueue {
    private int size;//容器大小
    private int[] queue;//queue数组作为容器存放队列数据
    private int head;//队头位置
    private int end;//队尾位置

    public MyQueue(int size) {
        this.size = size;
        queue = new int[size];
        head = end = 0;
    }

    //判断队列是否是满的方法
    public boolean isFull() {
        return next(end) == head;
    }

    //判断队列是否为空的方法
    public boolean isEmpty() {
        return end == head;
    }

    //入队方法
    public void offer(int element) {
        if (isFull()) {
            throw new IllegalStateException("队列已满，不能添加新数据");
        }
        queue[end] = element;
        end = next(end);
    }

    //出队方法
    public int poll() {
        if (isEmpty()) {
            throw new IllegalStateException("队列是空的，不能拿出数据");
        }
        int value = queue[head];
        head = next(head);
        return value;

    }

    //向下一位移动的方法
    public int next(int value) {
        return (value + 1) % size;
    }

    //打印输出方法
    public void print() {
        if (isEmpty()) {
            return;
        }
        int cur = head;
        while (cur != end) {
            System.out.println(queue[cur]);
            cur = next(cur);
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

上述拙见 有不对之处 欢迎各位大佬指出