服务器之家

服务器之家 > 正文

java数据结构基础:循环链表和栈

时间:2021-11-01 11:07     来源/作者:去吧猫头夜鹰

循环链表:

与单链表的最后一个节点的指针域为null不同,循环链表的最后一个节点的指针指向头结点

实现思路:

初始化时将头结点指向自身,添加节点到链表末尾时,将新节点的指针指向头结点

在遍历链表时,判断是否遍历到链表末尾,需要判断当前指针的下一个节点是否为头结点

代码实现:

节点类CircleNode:

?
1
2
3
4
5
6
7
8
9
10
11
public class CircleNode {
    public int data;
    public CircleNode next;
    public CircleNode(int data) {
        this.data = data;
    }
    @Override
    public String toString() {
        return "CircleNode{" + "data=" + data + '}';
    }
}

循环链表类CircleLinkedList:

?
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
public class CircleLinkedList {
    public CircleNode head = new CircleNode(0);
    public CircleLinkedList() {
        head.next = head;
    }
    //添加节点
    public void add(CircleNode circleNode) {
        CircleNode temp = head;
        //找到链表最后一个节点
        while (temp.next != head) {
            temp = temp.next;
        }
        temp.next = circleNode;
        circleNode.next = head;
    }
    //删除节点
    public void delete(int data) {
        CircleNode temp = head;
        boolean flag = false;    //标志是否找到待删除节点的前一个节点
        while (true) {
            if (temp.next == head) {
                //已经遍历到链表最后了
                break;
            } else if (temp.next.data == data) {
                //找到待删除节点的前一个节点
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            temp.next = temp.next.next;
        } else {
            System.out.println("要删除的节点不存在");
        }
    }
    //输出链表
    public void show() {
        //判断链表是否为空
        if (head.next == head) {
            System.out.println("链表为空");
            return;
        }
        CircleNode temp = head.next;
        while (temp != head) {
            System.out.println(temp);
            temp = temp.next;
        }
    }
}

栈:

栈是一种受限制的线性表,只允许在表的一端进行插入,另一端进行删除,具有“先入先出”的特性

栈是一种受限制的线性表

只允许在表的一端进行插入和删除,这一端称作栈顶

具有先进后出的特性

实现思路:

栈底层数据采用数组存储

设置栈顶指针top指向栈顶的元素

判满:top = maxSize - 1

判空: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
public class ArrayStack {
    private int maxSize;    //数组的最大容量
    private int[] stack;    //存放数据
    private int top = -1;    //栈顶指针
    public ArrayStack(int maxSize) {
        this.maxSize = maxSize;
        stack = new int[this.maxSize];
    }
    //判断栈是否满
    public boolean isFull() {
        return top == maxSize - 1;
    }
    //判断栈是否空
    public boolean isEmpty() {
        return top == -1;
    }
    //入栈
    public void push(int value) {
        //判断是否栈满
        if (isFull()) {
            System.out.println("栈满");
            return;
        }
        top++;
        stack[top] = value;
    }
    //出栈
    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("栈空");
        }
        int value = stack[top];
        top--;
        return value;
    }
    //输出栈,从栈顶开始显示
    public void show() {
        if (isEmpty()) {
            System.out.println("栈空");
            return;
        }
        for (int i = top; i >= 0; i--) {
            System.out.printf("stack[%d] = %d\n", i, stack[i]);
        }
    }
}

总结

本篇文章就到这里了,希望能给你带来帮助,也希望您能够多多关注服务器之家的更多内容!

原文链接:https://blog.csdn.net/qq_25274377/article/details/119278487

标签:

相关文章

热门资讯

yue是什么意思 网络流行语yue了是什么梗
yue是什么意思 网络流行语yue了是什么梗 2020-10-11
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全 2019-12-26
背刺什么意思 网络词语背刺是什么梗
背刺什么意思 网络词语背刺是什么梗 2020-05-22
2021年耽改剧名单 2021要播出的59部耽改剧列表
2021年耽改剧名单 2021要播出的59部耽改剧列表 2021-03-05
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总 2020-11-13
返回顶部