您的位置: 首页  >  文章  >  实现栈、队列、链表数据结构（java）

实现栈、队列、链表数据结构（java）

分类: 文章 • 2023-11-17 20:41:58


                                                     实现栈、队列、链表数据结构

1. 数组实现栈
[Java] 纯文本查看 复制代码
01
02
03
04
05
06
07
08
09
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
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] 纯文本查看 复制代码
01
02
03
04
05
06
07
08
09
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 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());               
                }       
}


3.单链表实现
[Java] 纯文本查看 复制代码
01
02
03
04
05
06
07
08
09
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
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();
        }
         
}



4.循环链表
实现栈、队列、链表数据结构（java） 


5.双向循环链表
[Java] 纯文本查看 复制代码
01
02
03
04
05
06
07
08
09
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
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.****.net/hnu_zzt/article/details/90742026

更多学习资料可关注：gzitcast

相关推荐