数据结构与算法（一） 链表、栈与队列Java实现_队列 栈 链表 java实现

一、链表基本操作

1.单链表
（I）结点定义：单链表中的结点由两部分组成，数据域和指针域。指针域里面存放的是指向下一结点的地址，数据域保存该结点的数据值。单链表结构如图所示：

（II）用Java来定义结点类如下：

class Node{      //结点类
    Node next=null;     //存储指向后继节点的指针
    int data;          //存储结点的数据值
    public Node(int data){
        this.data=data;
    }
}
1
2
3
4
5
6
7

（III）单链表的增删操作图解说明：

       增加结点算法思路：假设需要将新值为x的结点插入链表第i个位置，步骤如下：
     （1）先找到第i-1个位置的结点p；
     （2）生成一个数据域为x的新结点s；
     （3）设置x=s.data；
     （4）设置s.next=p.next ；
     （5）设置p.next=s
      增加结点操作示意图如下所示：

删除结点算法思路：假设需要删除单链表第i个位置的结点，步骤如下：
（1）先找到第i-1个位置的结点p ;
（2）设置第i-1个位置结点的指针域指向第i+1个位置结点：p.next=p.next.next
删除结点操作示意图如下所示：

（IV）单链表的基本操作Java实现：

public class MyLinkedList{
    static Node head=null;       //链表头的引用
	/*
     * *    头插法新增节点
     */
    public static void addNodeHead(int data){
        if(head==null){
            Node newNode=new Node(data);
            head=newNode;
            return;
        }
        Node newNode=new Node(data);
        Node tmp1=head;
        Node tmp2=tmp1.next;    //头节点的下一个节点
        tmp1.next=newNode;
        newNode.next=tmp2;
    }
    /*
     * *       尾插法新增节点
     */
    public static void addNodeTail(int data){
        if(head==null){            //如果没有头节点则创建头节点
            Node newNode=new Node(data);
            head=newNode;
            return;
        }
        Node newNode=new Node(data);
        Node tmp=head;
        while (tmp.next!=null){   //遍历找到最后一个节点
            tmp=tmp.next;
        }
        tmp.next=newNode;
    }
    /*
    * *     在链表中第i个位置插入节点
     */
    public static void insertNode(int i,int data){
        Node newNode=new Node(data);
        Node tmp=head;
        if(i==2){  //如果插入的节点位置是第2个
            Node node=tmp.next;
            tmp.next=newNode;
            newNode.next=node;
        }else{
            int j=1;
            while (j<=i-2){  //找到第i-1个节点
                tmp=tmp.next;
                j++;
            }
            Node node=tmp.next;   //第i个节点
            tmp.next=newNode;
            newNode.next=node;
        }
	}
	/*
     *    删除第i个位置的节点
     */
    public static void deleteNode(int i){
        if(i<1||i>getLength()){
            System.out.println("删除节点元素的位置不合理");
        }
        Node tmp=head;
        if(i==1){
            head=head.next;
        }else if(i==2){          //如果删除结点的位置是第2个
            Node tmp1=head.next;
            Node tmp2=tmp1.next;   //第i+1个节点的位置
            head.next=tmp2;
        }else if(i>2){
            int j=1;
            while (j<=i-2){  //找到第i-1个节点
                tmp=tmp.next;
                j++;
            }
            Node tmp3=tmp.next.next;  //找到第i+1个节点的位置
            tmp.next=tmp3;
        }
    }

    /*
     *  *  计算链表的长度
     */
    public static int getLength(Node head){
        Node tmp=head;
        int length=0;
        while (tmp!=null){
            length++;
            tmp=tmp.next;
        }
        return length;
    }
    /*
     *    对链表进行排序
     */
    public static void orderLinkedList(){
        Node nextNode=null;
        Node curNode=head;
        while (curNode!=null){
            nextNode=curNode.next;
            while (nextNode!=null){
                if(curNode.data>nextNode.data){
                    int temp=curNode.data;
                    curNode.data=nextNode.data;
                    nextNode.data=temp;
                }
                nextNode=nextNode.next;
            }
            curNode=curNode.next;
        }
    }
    /*
     *  *  单链表操作测试程序
     */
    public static void main(String[] args) {
        addNode(5);
        addNode(1);
        addNode(3);
        Node tmp=head;
        insertNode(2,8);
        insertNode(2,6);
        System.out.println("LinkedListLength:"+getLength());
        while (tmp!=null){    //遍历链表元素
            System.out.print(tmp.data+" ");
            tmp=tmp.next;
        }
        orderLinkedList();
        Node tmp1=head;
        System.out.println();
        System.out.print("--------------排序后---------------");
        System.out.println();
        while (tmp1!=null){
            System.out.print(tmp1.data+" ");
            tmp1=tmp1.next;
        }

    }
}
class Node{      //声明节点类
    int data;  //数据域
    Node next;  //指针域
	public Node(){

    }
	public Node(int data){
        this.data=data;
    }
}
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
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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147

2.双向链表与循环链表

（I）结点定义：双向链表是在单链表的基础之上扩展而来的，结点由3部分组成分别为前驱指针域、数据域、后继指针域；前驱指针保存上一个结点的地址信息，后继指针保存下一个结点的地址信息，数据域保存该结点的数据值。双向链表结构如图所示：


（II）用Java来定义结点类如下：

class Node2{
    private int data;     //数据域
    private Node2 next;  //后继指针
    private Node2 pre;   //前驱指针

    public Node2(int data){
        this.data=data;
    }

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public Node2 getNext() {
        return next;
    }

    public void setNext(Node2 next) {
        this.next = next;
    }

    public Node2 getPre() {
        return pre;
    }

    public void setPre(Node2 pre) {
        this.pre = pre;
    }
}
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

（III）双向链表的增删操作图解说明：

         增加结点算法思路：假设需要将新值为x的结点插入链表第i个位置，步骤如下：
       （1) 生成一个数据域为x的新结点s；
       （2）设置s.data=x；
       （3）遍历找到第i-1个结点的位置p1；
       （4）找到第i个结点的位置p2=p1.next;
        （5） 设置s.next=p2；
       （6）设置p1.next=s；
       （7）设置p1=s.pre;
       （8）设置s=p2.pre；
      增加结点操作示意图如下所示：

删除结点算法思路：假设需要删除双向链表第i个位置的结点，步骤如下：

（1）首先找到第i-1个结点的位置p；
（2）设置p.next=p.next.next;
（3）设置p=p.next.next.pre;
删除结点操作示意图如下所示：

（IV）双向链表的基本操作Java实现：

public class DLinkedList{
	/*
    * *   向双向链表中指定位置处新增节点
     */
    public static void addNode2(Node2 node,int i,int data){
        Node2 newNode=new Node2(12);
        Node2 head=node;     //获取头节点
        if(i<1||i>getLength(node)){
            System.out.println("插入的位置不合理");
        }
        //首先得到第i-1个位置
        Node2 tmp=head;
        int j=0;
        while (i>2){
            tmp=tmp.getNext();
            i--;
        }
        Node2 node2=tmp.getNext();   //得到第i个节点
        tmp.setNext(newNode);
        newNode.setNext(node2);
        node2.setPre(newNode);
        newNode.setPre(tmp);
    }

    /*
    * *   从双向链表指定位置中删除节点
     */
    public static void deleteNode2(Node2 node,int i){
        Node2 head=node;
        //首先得到第i-1个位置
        Node2 tmp=head;
        int j=0;
        while (i>2){
            tmp=tmp.getNext();
            i--;
        }
        //再得到第i+1个位置
        Node2 tmp1=tmp.getNext().getNext();
        tmp.setNext(tmp1);
        tmp1.setPre(tmp);
    }

    //计算双向链表的长度
    public static int getLength(Node2 node){
        Node2 tmp=node;
        int length=0;
        while (tmp!=null){
            length++;
            tmp=tmp.getNext();
        }
        return length;
    }
    /*
     * * 测试程序
     */
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        /*
         * *    创建双向链表
         */
        List<Node2> list=new ArrayList<>();
        for (int i = 0; i <5 ; i++) {
            int j=i+1;
            Node2 node=new Node2(j*10);
            list.add(node);
        }
        for (int i = 0; i <4 ; i++) {
            list.get(i).setNext(list.get(i+1));
        }
        for (int i = 4; i >0 ; i--) {
            list.get(i).setPre(list.get(i-1));
        }
//        list.get(0).setPre(list.get(4));
//        list.get(4).setNext(list.get(0));

        /*
         **   遍历双向链表
         */
        System.out.print("从前往后遍历结果为："+" ");
        Node2 tmp=list.get(0);
        while(tmp!=null){
            System.out.print(tmp.getData()+"  ");
            tmp=tmp.getNext();
        }
        System.out.println();
        System.out.print("从后往前遍历结果为："+" ");
        Node2 tmp1=list.get(4);
        while (tmp1!=null){
            System.out.print(tmp1.getData()+"  ");
            tmp1=tmp1.getPre();
        }
        System.out.println();
        System.out.println("原双向链表的长度为："+getLength(list.get(0)));
        System.out.println("请输入要插入元素的位置：");
        int i=scanner.nextInt();
        System.out.println("-------------------------------新增元素后的双向链表遍历结果为：---------------------------------");
        addNode2(list.get(0),i,12);
        Node2 head=list.get(0);
        System.out.print("从前往后遍历结果为："+" ");
        Node2 backNode=null;
        while (head!=null){
            if(head.getNext()==null){
                backNode=head;
            }
            System.out.print(head.getData()+"  ");
            head=head.getNext();
        }
        System.out.println();
        System.out.print("从后往前遍历结果为："+" ");
        while (backNode!=null){
            System.out.print(backNode.getData()+"  ");
            backNode=backNode.getPre();
        }
        System.out.println();
        System.out.println("请输入要删除的位置：");
        int j=scanner.nextInt();
        System.out.println("--------------------------------删除元素后的双向链表遍历结果为：----------------------------------");
        deleteNode2(list.get(0),j);
        Node2 head1=list.get(0);
        System.out.print("从前往后遍历结果为："+" ");
        while (head1!=null){
            System.out.print(head1.getData()+" ");
            head1=head1.getNext();
        }
        System.out.println();
        System.out.print("从后往前遍历结果为："+" ");
        Node2 backNode1=list.get(4);
        while (backNode1!=null){
            System.out.print(backNode1.getData()+" ");
            backNode1=backNode1.getPre();
        }
    }
}
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
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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133

（V）双向循环链表：
      双向循环链表操作非常简单，只需把尾结点的后继指针指向头节点，把头节点前向指针指向尾结点即可；示意图如下所示：

二、栈与队列基本操作

1.栈与队列的特点以及比较
（I）定义：栈与队列是在程序设计中被广泛使用的两种重要的线性数据结构，都是在一个特定范围的存储单元中存储数据。栈的特点是“先进后出，后进先出”，栈这种数据结构最重要并且需要理解的是栈顶指针，其压栈、出栈操作都是移动栈顶指针完成；队列的特点是“先进先出，后进后出”，队列这种数据结构最重要需要理解的是队头指针与队尾指针，其入队、出队操作都是移动队尾指针完成的。栈与队列的数据结构如下图所示：


（II）压栈与出栈操作图解说明：
压栈操作本质是移动栈顶指针的过程，假设需要进栈的元素为x。基于链表实现其步骤如下：
（1）新建一个数据域为x的新结点newNode；
（2）设置栈顶指针newNode.next=top;
（3）设置top=newNode;
压栈操作伪代码如下：

//压栈操作
public void push(E data){
	Node<E> newNode=new Node<E>(data);
	newNode.next=top;
	top=newNode;
}
1
2
3
4
5
6

出栈操作本质也是移动栈顶指针的过程。基于链表的实现其步骤如下：
（1）首先得到栈顶指针指向的结点；
（2）在移动栈顶指针；
出栈操作伪代码如下：

//出栈操作
public E pop(){
	if(isEmpty()){
		return null;
	}
	E data=top.data;
	top=top.next;
	return data;
}
1
2
3
4
5
6
7
8
9

（III）入队与出队操作图解说明如下：
入队操作本质是移动尾指针的过程。基于链表的实现其步骤如下： （1）首先创建一个需要入队的结点newNode;
（2）判断队列是否为空，如果为空 则设置head=tail=newNode；
（3）队列如果不为空则设置tail.next=newNode;
（4）tail=newNode;
入队操作伪代码如下：

//入队操作
public void put(E data){
	Node<E> newNode=new Node<E>(data);
	if(head==null && tail==null){
		head=tail=newNode;
	}else{
		tail.next=newNode;
		tail=newNode;
	}
}
1
2
3
4
5
6
7
8
9
10

出队操作本质是从队列头指针开始遍历链表的过程。基于链表的实现步骤如下：
（1）首先判断队列是否为空，如果为空则返回null；
（2）从头指针开始依次遍历。
出队操作伪代码如下：

//出队操作
public E pop(){
	if(isEmpty()){
		return null;
	}
	E data=head.data;
	head=head.next;
	return data;
}
1
2
3
4
5
6
7
8
9

（IV）栈的基本操作Java实现

package dataStructure;

/**
 *     Created by Air on 2019/6/29.
 *     用链表的方式实现栈
 */
public class Stack {
    static Node1 top=null;    //定义栈顶指针

    //判断栈是否为空
    public static boolean isEmpty(){
        return top==null;
    }

    //得到栈顶元素的值

    public int peek(){
        if(isEmpty()){
            return 0;
        }
        return top.data;
    }

    //压栈操作
    public static int push(int data){
        Node1 newNode=new Node1(data);
        newNode.next=top;
        top=newNode;
        int j=top.data;
        return data;
    }

    //出栈操作
    public static int pop(){
        if(!isEmpty()){
            int data=top.data;
            top=top.next;
            return data;
        }
        return 0;
    }

    //计算栈的长度
    public static int getLength(){
        int length=0;
        Node1 tmp=top;
        while (tmp!=null){
            length++;
            tmp=tmp.next;
        }
        return length;
    }


    //测试程序
    public static void main(String[] args) {
        Stack stack=new Stack();
        for (int i = 0; i <5 ; i++) {
            stack.push(i+1);
        }
        System.out.println("栈的长度为："+getLength());
        System.out.print("出栈顺序为：");
        while (top!=null){
            System.out.print(top.data+"  ");
            top=top.next;
        }

    }
}

class Node1{
    Node1 next=null;  //结点的指针域
    int data; //结点的数据域
    public Node1(int data){
        this.data=data;
    }
}


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
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

（V）队列的基本操作Java实现

package dataStructure;

/**
 *     Created by Air on 2019/6/29.
 *     使用链表实现队列
 */
public class MyQueue<E> {
    Node2<E> head=null;   //定义头指针
    Node2<E> tail=null;   //定义尾指针

    //判断是否为空
    public boolean isEmpty(){
        if(head==null && tail==null){
            return true;
        }else{
            return false;
        }
    }

    //入队操作
    public void put(E data){
        Node2<E> newNode=new Node2<E>(data);
        if(isEmpty()){
            head=tail=newNode;
        }else{
            tail.next=newNode;
            tail=newNode;
        }
    }

    //出队操作
    public E pop(){
        if(isEmpty()){
            return null;
        }
        E data=head.data;
        head=head.next;
        return data;
    }

    //计算队列的长度
    public int size(){
        Node2<E> tmp=head;
        int length=0;
        while (tmp!=null){
            length++;
            tmp=tmp.next;
        }
        return length;
    }

    //测试程序
    public static void main(String[] args) {
        MyQueue<Integer> queue=new MyQueue<Integer>();
        for (int i = 0; i < 10; i++) {
            queue.put(i+1);
        }
        System.out.println("队列长度为："+ queue.size());
        System.out.println("出队顺序为：");

        for (int i = 0; i <10 ; i++) {
            System.out.print(queue.pop()+" ");
        }
    }
}

class Node2<E>{
    Node2<E> next=null;   //定义指针域
    E data;    //定义数据域
    public Node2(E data){
        this.data=data;
    }
}

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

（VI）如何用两个栈模拟队列，示例代码如下：

package dataStructure;

/**
 *    Created by Air on 2019/6/30.
 *   使用两个栈模拟队列操作
 */
public class Queue<E> {
    LStack<E> lStack1=new LStack<>();
    LStack<E> lStack2=new LStack<>();

    //对lStack1压栈
    public void put(E data){
        lStack1.push(data);
    }

    //出栈操作
    public E pop(){
        if(lStack2.isEmpty()){
            while (!lStack1.isEmpty()){
                lStack2.push(lStack1.pop());
            }
        }
        return lStack2.pop();
    }

    //判空操作
    public boolean isEmpty(){
        if(lStack1.isEmpty() && lStack2.isEmpty()){
            return true;
        }else{
            return false;
        }
    }

    /*
     * *   测试程序
     */
    public static void main(String[] args) {
        Queue<Integer> queue=new Queue<>();
        for (int i = 0; i <10 ; i++) {
            queue.put(i+1);
        }
        System.out.print("出队顺序为：");
        for (int i = 0; i <10 ; i++) {
            System.out.print(queue.pop()+"  ");
        }
    }
}

/*
 * *   使用链表实现栈
 */
class LStack<E>{
    Node3<E> top=null;  //定义栈顶指针

    /*
     * *    得到栈顶元素值
     */
    public E peek(){
        if(isEmpty()){
            return null;
        }
        return top.data;
    }

    /*
     * *  判空操作
     */
    public boolean isEmpty(){
        return top==null;
    }

    /*
     * * 压栈操作
     */
    public Node3<E> push(E data){
        Node3<E> newNode=new Node3<>(data);
        newNode.next=top;
        top=newNode;
        return newNode;
    }

    /*
     * *出栈操作
     */
    public E pop(){
        if(isEmpty()){
            return null;
        }
        E data=top.data;
        top=top.next;
        return data;
    }

    /*
     * *   计算栈的长度
     */
    public int getLength(){
        int length=0;
        Node3<E> tmp=top;
        while (tmp!=null){
            length++;
            tmp=tmp.next;
        }
        return length;
    }

    /*
     * *   测试栈是否创建成功
     */
    public static void main(String[] args) {
        LStack<Integer> lStack=new LStack<>();
        lStack.push(1);
        lStack.push(2);
        lStack.push(3);
        System.out.println("新创建的栈的长度为："+lStack.getLength());
        System.out.print("出栈顺序为：");
        for (int i = 0; i <3 ; i++) {
            System.out.print(lStack.pop()+" ");
        }

    }
}

/*
 * *  定义结点类
 */
class Node3<E>{
    Node3<E> next=null;   //定义结点的指针域
    E data;   //定义结点的数据域
    public Node3(E data){
        this.data=data;
    }
}




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
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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138