链表、栈、队列_链表 队列 和栈

链表

• 在内存空间中，数组和链表都是基本的数据结构，都是【表】，或者叫【线性表】。
• 线性表是一个线性结构，它是一个含有n≥0个结点的有限序列，对于其中的结点，有且仅有一个开始结点没有前驱但有一个后继结点，有且仅有一个终端结点没有后继但有一个前驱结点，其它的结点都有且仅有一个前驱和一个后继结点，说人话，就是有头有尾一条线。

还不明白再来一张图

代码实现：
写链表首先要封装一个保存数据和引用的节点，我们俗称node

public class Node {
       // 数据
    private Integer data;
       // 该节点的下一个节点
    private Node next;

    public Integer getData() {
        return data;
    }

    public void setData(Integer data) {
        this.data = data;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

public class SuperLinked {

    // 链表的长度
    private int size;
    // 维护一个头节点
    private Node first;
    // 维护一个尾节点
    private Node last;

    // 无参构造器
    public SuperLinked(){

    }

    //添加元素至链表尾部
    public boolean add(Integer data){
        Node node = new Node(data,null);
        if (first == null){
            first = node;
        } else {
            last.setNext(node);
        }
        last = node;
        size++;
        return true;
    }

    //在指定下标添加元素
    public boolean add(int index,Integer data){
        Node node = getNode(index);
        Node newNode = new Node(data,null);

        if (node != null){
            newNode.setNext(node.getNext());
            node.setNext(newNode);
        } else {
            first = newNode;
            last = newNode;
        }

        size++;
        return true;
    }

    // 删除头元素
    public boolean remove(){
        if (size < 0){
            return false;
        }

        if (first != null ){
            first = first.getNext();
            size--;
        }
        return true;
    }

    // 删除指定元素
    public boolean remove(int index){
        if (size < 0){
            return false;
        }
        if(size == 1){
            first = null;
            last = null;
        } else {
            Node node = getNode(index-1);
            node.setNext(node.getNext().getNext());
        }
        size--;
        return true;
    }

    // 修改指定下标的元素
    public boolean set(int index,Integer data){
        // 找到第index个
        Node node = getNode(index);
        node.setData(data);
        return true;
    }

    // 获取指定下标的元素
    public Integer get(int index){
        return getNode(index).getData();
    }

    //查看当前有多少个数字
    public int size(){
        return size;
    }

    //添加元素
    private Node getNode(int index){

        // 边界判断
        if(index <= 0){
            index = 0;
        }
        if(index >= size-1){
            index = size-1;
        }

        // 找到第index个
        Node cursor = first;
        for (int i = 0; i < index; i++) {
            cursor = cursor.getNext();
        }
        return cursor;
    }

    public static void main(String[] args) {
        SuperLinked linked = new SuperLinked();
        linked.add(1);
        linked.add(2);
        linked.add(4);
        linked.add(6);
        linked.add(3);
        linked.add(2);
        linked.add(7);
        linked.add(6);
        linked.remove();
        linked.remove(2);
        linked.set(0,3);
        for (int i = 0; i < linked.size(); i++) {
            System.out.println(linked.get(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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128

封装一个栈和队列

栈（Stack）和队列（Queue）是两种操作受限的线性表。

这种受限表现在：栈的插入和删除操作只允许在表的尾端进行（在栈中成为“栈顶”），满足“FILO：First In Last Out”；队列只允许在表尾插入数据元素，在表头删除数据元素,满足“First In First Out”。

栈与队列的相同点：

• 都是线性结构。
• 插入操作都是限定在表尾进行。
• 都可以通过顺序结构和链式结构实现。、

栈与队列的不同点：

• 队列先进先出，栈先进后出。

栈

/**
 * 数组实现栈称之为静态栈
 */
public class ArrayStack {

     // 栈大小
    private int maxStack;

     // 数组用来模拟栈
    private int[] stack;

    // 表示栈顶所在的位置，默认情况下如果没有数据时，使用-1
    private int top;

    public ArrayStack(int maxStack){
        this.maxStack = maxStack;
        stack = new int[maxStack];
    }

    /**
     * 1. 压栈
     * 2. 弹栈
     * 3.判断是否是空栈
     * 4. 当前栈中是否是满栈
     */

    // 判断是否已经满栈
    public boolean isFull(){
       return this.top == this.maxStack-1;
    }

    // 判断是否是空栈
    public boolean isEmpty(){
        return this.top == -1;
    }


    /**
     * 压栈
     */
    public void push(int val){
        // 是否已经满栈
        if (isFull()){
            throw new RuntimeException("栈已经满了");
        }
        top++;
        stack[top] = val;
    }


    /**
     * 弹栈
     */
    public int pop(){
        // 如果栈中时空
        if (isEmpty()){
            throw new RuntimeException("空栈，未找到数据");
        }

        int value = stack[top];
        top--;
        return value;
    }


    /**
     * 查看栈中所有元素
     */
    public void list(){

        //是否是空栈
       if (isEmpty()){
           throw new RuntimeException("空栈，未找到数据");
       }
       for (int i = 0;i<stack.length;i++){
           System.out.printf("stack[%d]=%d\n",i,stack[i]);
       }

    }

    /**
     * 获取栈中元素存在的个数
     */
    public int length(){
        return this.top+1;
    }

}

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

需求:使用栈判断数据是否是回文数据

public class TestApp {
    public static void main(String[] args) {

        /**
         * 回文数据
         * 回文： aba,   racecar 意思就是从左往右和从右往左是一样的数据称之为回文数据
         * 需求: 通过上面以数组模拟栈来判断一个字符串是否是一个回文数据
         *
         */
        delecation("hello");
        delecation("aba");


    }

    public static boolean delecation(String val){

        /**
         * 初始化栈对向、象
         */
        ArrayStack arrayStack = new ArrayStack(10);

        // 获取传递进来的字符串的长度
        int length = val.length();

        for (int i = 0; i <length ; i++) {
            arrayStack.push(val.charAt(i));
        }


        /**
         * 获取弹出来的数据
         */
        String newVal = "";
        int length1 = arrayStack.length();
        for (int i = 0; i <length1; i++) {
            // 如果不是一个空栈
            if (!arrayStack.isEmpty()){
                char pop =(char) arrayStack.pop();
                newVal = newVal+pop;
            }
        }

        if (val.equals(newVal)){
            return true;
        }

        return false;

    }
}

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

队列

public class Queue {

    private SuperLinked superLinked = new SuperLinked();

    // 出队的方法
    public Integer poll(){
        if(empty()){
            return null;
        }
        Integer integer = superLinked.get(0);
        superLinked.remove();
        return integer;
    }
    
    // 返回队首，不出队
    public Integer peek(){
        if(empty()){
            return null;
        }
        return superLinked.get(0);
    }

    // 入队的方法
    public void add(Integer item){
        superLinked.add(item);
    }

    // 判断这个队列是否为空
    public boolean empty(){
        return superLinked.size() == 0;
    }

    public static void main(String[] args) {
        Queue queue = new Queue();
        queue.add(1);
        queue.add(2);
        queue.add(3);

        System.out.println(queue.poll());
        System.out.println(queue.poll());
        System.out.println(queue.poll());
        System.out.println(queue.poll());
        System.out.println(queue.poll());
    }

}
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