本帖最后由 biu波儿了罢 于 2019-10-31 15:25 编辑
实现栈、队列、链表数据结构
1. 数组实现栈 [Java] 纯文本查看 复制代码 public class MyStack {
// 栈的底层使用数组来存储数据
int[] elements;
public MyStack() {
elements = new int[0];
}
// 压入元素
public void push(int element) {
//创建一个新的数组
int[] newArr = new int[elements.length + 1];
// 把数组中的元素复制到新数组中
for (int i = 0; i < elements.length; i++) {
newArr = elements;
}
// 把添加的元素放入新的数组中
newArr[elements.length] = element;
// 使用新数组替换旧数组
elements = newArr;
}
public int pop() {
// 栈中没有元素
if (elements.length == 0) {
throw new RuntimeException("stack is empty");
}
// 取出数组的最后一个元素
int element = elements[elements.length - 1];
// 创建一个新的数组
int[] newArr = new int[elements.length - 1];
// 原数组中除了最后一个元素的其它元素放入新的数组中
for (int i = 0; i < elements.length - 1; i++) {
newArr = elements;
}
// 替换数组
elements = newArr;
// 返回栈顶元素
return element;
}
// 查看栈顶元素
public int peek() {
// 栈中没有元素
if (elements.length == 0) {
throw new RuntimeException("stack is empty");
}
return elements[elements.length - 1];
}
// 判断栈是否为空
public boolean isEmpty() {
return elements.length == 0;
}
//test
public static void main(String[] args) {
MyStack ms = new MyStack();
// ms.push(9);
// ms.push(8);
// ms.push(7);
System.out.println(ms.peek());
// System.out.println(ms.pop());
System.out.println(ms.isEmpty());
// System.out.println(ms.pop());
// System.out.println(ms.pop());
}
}
2.数组实现队列 [Java] 纯文本查看 复制代码 public class MyQueue {
int[] elements;
public MyQueue() {
elements=new int[0];
}
//入队
public void add(int element) {
//创建一个新的数组
int[] newArr = new int[elements.length + 1];
// 把数组中的元素复制到新数组中
for (int i = 0; i < elements.length; i++) {
newArr = elements;
}
// 把添加的元素放入新的数组中
newArr[elements.length] = element;
// 使用新数组替换旧数组
elements = newArr;
}
//出队
public int poll() {
//把数组中的第0个元素取出来
int element = elements[0];
//创建一个新的数组
int[] newArr = new int[elements.length-1];
//复制原数组中的元素到新的数组中
for(int i=0;i<newArr.length;i++) {
newArr=elements[i+1];
}
//替换数组
elements=newArr;
return element;
}
//判断队列是否为空
public boolean isEmpty() {
return elements.length==0;
}
//test
public static void main(String[] args) {
MyQueue mq=new MyQueue();
mq.add(9);
mq.add(8);
mq.add(7);
System.out.println(mq.poll());
mq.add(6);
System.out.println(mq.poll());
}
}[Java] 纯文本查看 复制代码 public class Node {
//节点内容
int data;
//下一个节点
Node next;
public Node(int data) {
this.data=data;
}
//为节点追加节点
public Node append(Node node) {
//当前节点
Node currentNode=this;
//循环向后找
while(true) {
//取出下一个节点
Node nextNode=currentNode.next;
//如果下一个节点为null，当前节点已经是最后一个节点
if(nextNode==null) {
break;
}
//赋给当前节点
currentNode=nextNode;
}
//把需要追回的节点追加为找到的当前节点的下一个节点
currentNode.next=node;
return this;
}
//插入一个节点作为当前节点的下一个节点
public void after(Node node) {
//取出下一个节点，作为下下一个节点
Node nextNext=next;
//把新节点作为当前节点的下一个节点
this.next=node;
//把下下一个节点设置为新节点的下一个节点
node.next=nextNext;
}
//显示所有节点信息
public void show() {
Node currentNode = this;
while(true) {
System.out.print(currentNode.data+" ");
//取出下一个节点
currentNode=currentNode.next;
//如果是最后一个节点
if(currentNode==null) {
break;
}
}
System.out.println();
}
//删除下一个节点
public void removeNext() {
//取出下下一个节点
Node newNext = next.next;
//把下下一个节点设置为当前节点的下一个节点
this.next=newNext;
}
//获取下一个节点
public Node next() {
return this.next;
}
//获取节点中的数据
public int getData() {
return this.data;
}
//当前节点是否是最后一个节点
public boolean isLast() {
return next==null;
}
//test
public static void main(String[] args) {
Node n1=new Node(1);
Node n2=new Node(2);
Node n3=new Node(3);
n1.append(n2).append(n3).append(new Node(4));
// System.out.println(n1.next().next().next().getData());
// System.out.println(n1.next().next().isLast());
n1.show();
n1.next().removeNext();
n1.show();
}
}
5.双向循环链表
[Java] 纯文本查看 复制代码 public class DoubleNode {
// 上一个节点
DoubleNode pre = this;
// 下一个节点
DoubleNode next = this;
// 节点数据
int data;
public DoubleNode(int data) {
this.data = data;
}
// 新增节点
public void after(DoubleNode node) {
// 原来的下一个节点
DoubleNode nextNext = next;
// 把新节点作为当前节点的下一个节点
this.next = node;
// 把当前节点作为新节点的前一个节点
node.pre = this;
// 让原来的下一个节点作为新节点的下一个节点
node.next = nextNext;
// 让新节点作为原来的下一个节点的前一个节点
nextNext.pre = node;
}
// 下一个节点
public DoubleNode next() {
return this.next;
}
// 上一个节点
public DoubleNode pre() {
return this.pre;
}
//获取数据
public int getData() {
return this.data;
}
}
文章摘自：https://blog.csdn.net/hnu_zzt/article/details/90742026 | 
收藏
淘帖
踩
