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

网友投稿 255 2022-10-08


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

目录循环链表:实现思路:代码实现:栈:实现思路:代码实现:总结

循环链表:

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

实现思路:

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

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

代码实现:

节点类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 ArraymWmYDStack {

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]);

}

}

}

总结

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


版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。

上一篇:SQL注入笔记(SQL注入例子)
下一篇:下一代防火墙---“毕安云盾”为网络安全保驾护航!(网盾安全学院)
相关文章

 发表评论

暂时没有评论,来抢沙发吧~