Java语言实现数据结构栈代码详解

时间:2022-09-11 08:22:03

近来复习数据结构,自己动手实现了。栈是一种限制插入和删除只能在一个位置上的表。最基本的操作是进栈和出栈,因此,又被叫作“先进后出”表。

首先了解下栈的概念:

栈是限定仅在表头进行插入和删除操作的线性表。有时又叫lifo(后进先出表)。要搞清楚这个概念,首先要明白”栈“原来的意思,如此才能把握本质。

"栈“者,存储货物或供旅客住宿的地方,可引申为仓库、中转站,所以引入到计算机领域里,就是指数据暂时存储的地方,所以才有进栈、出栈的说法。

实现方式是这样的:首先定义了一个接口,然后通过这个接口实现了线性栈和链式栈,代码比较简单,如下:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
package com.peter.java.dsa.interfaces;
/**
 * 栈操作定义
 *
 * @author peter pan
 */
public interface stack<t> {
    /* 判空 */
    boolean isempty();
    /* 清空栈 */
    void clear();
    /* 弹栈 */
    t pop();
    /* 入栈 */
    boolean push(t data);
    /* 栈的长度 */
    int length();
    /* 查看栈顶的元素,但不移除它 */
    t peek();
    /* 返回对象在栈中的位置 */
    int search(t 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
package com.peter.java.dsa.common;
import com.peter.java.dsa.interfaces.stack;
/**
 * 线性栈
 *
 * @author peter pan
 */
public class linearstack<t> implements stack<t> {
    @suppresswarnings("unchecked")
     private t[] t = (t[]) new object[16];
    private int size = 0;
    @override
     public boolean isempty() {
        // todo auto-generated method stub
        return size == 0;
    }
    @override
     public void clear() {
        // todo auto-generated method stub
        for (int i = 0; i < t.length; i++) {
            t[i] = null;
        }
        size = 0;
    }
    @override
     public t pop() {
        // todo auto-generated method stub
        if (size == 0) {
            return null;
        }
        t tmp = t[size - 1];
        t[size - 1] = null;
        size--;
        return tmp;
    }
    @override
     public boolean push(t data) {
        // todo auto-generated method stub
        if (size >= t.length) {
            resize();
        }
        t[size++] = data;
        return true;
    }
    @override
     public int length() {
        // todo auto-generated method stub
        return size;
    }
    @override
     public t peek() {
        // todo auto-generated method stub
        if (size == 0) {
            return null;
        } else {
            return t[size - 1];
        }
    }
    /* return index of data, return -1 if no data */
    @override
     public int search(t data) {
        // todo auto-generated method stub
        int index = -1;
        for (int i = 0; i < t.length; i++) {
            if (t[i].equals(data)) {
                index = i;
                break;
            }
        }
        return index;
    }
    @suppresswarnings("unchecked")
     private void resize() {
        t[] tmp = (t[]) new object[t.length * 2];
        for (int i = 0; i < t.length; i++) {
            tmp[i] = t[i];
            t[i] = null;
        }
        t = tmp;
        tmp = null;
    }
    /* from the left to the right is from the top to the bottom of the stack */
    @override
     public string tostring() {
        // todo auto-generated method stub
        stringbuffer buffer = new stringbuffer();
        buffer.append("linear stack content:[");
        for (int i = t.length - 1; i > -1; i--) {
            buffer.append(t[i].tostring() + ",");
        }
        buffer.append("]");
        buffer.replace(buffer.lastindexof(","), buffer.lastindexof(",") + 1, "");
        return buffer.tostring();
    }
}

链式栈:通过单链表进行实现。

?
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
package com.peter.java.dsa.common;
import com.peter.java.dsa.interfaces.stack;
public class linkedstack<t> implements stack<t> {
    private node top;
    private int size;
    @override
     public boolean isempty() {
        // todo auto-generated method stub
        return size == 0;
    }
    @override
     public void clear() {
        // todo auto-generated method stub
        top = null;
        size = 0;
    }
    @override
     public t pop() {
        // todo auto-generated method stub
        t topvalue = null;
        if (top != null) {
            topvalue = top.data;
            node oldtop = top;
            top = top.prev;
            oldtop.prev = null;
            size--;
        }
        return topvalue;
    }
    @override
     public boolean push(t data) {
        // todo auto-generated method stub
        node oldtop = top;
        top = new node(data);
        top.prev = oldtop;
        size++;
        return true;
    }
    @override
     public int length() {
        // todo auto-generated method stub
        return size;
    }
    @override
     public t peek() {
        // todo auto-generated method stub
        t topvalue = null;
        if (top != null) {
            topvalue = top.data;
        }
        return topvalue;
    }
    @override
     public int search(t data) {
        // todo auto-generated method stub
        int index = -1;
        node tmp = top;
        for (int i = size - 1; i > -1; i--) {
            if (tmp.data.equals(data)) {
                index = i;
                break;
            } else {
                tmp = tmp.prev;
            }
        }
        tmp = null;
        return index;
    }
    @override
     public string tostring() {
        // todo auto-generated method stub
        stringbuffer buffer = new stringbuffer();
        buffer.append("linked stack content:[");
        node tmp = top;
        for (int i = 0; i < size - 1; i++) {
            buffer.append(tmp.tostring() + ",");
            tmp = tmp.prev;
        }
        tmp = null;
        buffer.append("]");
        buffer.replace(buffer.lastindexof(","), buffer.lastindexof(",") + 1, "");
        return super.tostring();
    }
    private class node {
        t data;
        node prev;
        public node(t data) {
            // todo auto-generated constructor stub
            this.data = data;
        }
    }
}

学习还在进行中,以后会继续更新代码。

就是本文关于java语言实现数据结构栈代码详解的全部内容,希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题,如有不足之处,欢迎留言指出。感谢朋友们对本站的支持!

原文链接:http://www.cnblogs.com/littlepanpc/p/3436419.html