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

循环链表：

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

实现思路：

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

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

代码实现：

节点类CircleNode：

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：

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

入栈：栈顶指针上移后写入数据

出栈：用临时变量保存栈顶数据，栈顶指针下移，返回栈顶数据

代码实现：

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