服务器之家

服务器之家 > 正文

Java栈之链式栈存储结构的实现代码

时间:2020-09-21 17:10     来源/作者:Java教程网

Java栈之链式栈存储结构实现

一、链栈

采用单链表来保存栈中所有元素,这种链式结构的栈称为链栈。

二、栈的链式存储结构实现

?
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
package com.ietree.basic.datastructure.stack;
 
/**
 * 链栈
 *
 * Created by ietree
 * 2017/4/29
 */
public class LinkStack<T> {
 
  // 定义一个内部类Node,Node实例代表链栈的节点
  private class Node {
 
    // 保存节点的数据
    private T data;
    // 指向下个节点的引用
    private Node next;
    // 无参构造器
    public Node() {
    }
    // 初始化全部属性的构造器
    public Node(T data, Node next) {
 
      this.data = data;
      this.next = next;
 
    }
 
  }
  // 保存该链栈的栈顶元素
  private Node top;
  // 保存该链栈中已包含的节点数
  private int size;
  // 创建空链栈
  public LinkStack() {
    // 空链栈,top的值为null
    top = null;
 
  }
 
  // 以指定数据元素来创建链栈,该链栈只有一个元素
  public LinkStack(T element) {
 
    top = new Node(element, null);
    size++;
 
  }
 
  // 返回链栈的长度
  public int length() {
 
    return size;
 
  }
 
  // 进栈
  public void push(T element) {
 
    // 让top指向新创建的元素,新元素的next引用指向原来的栈顶元素
    top = new Node(element, top);
    size++;
 
  }
 
  // 出栈
  public T pop() {
 
    Node oldTop = top;
    // 让top引用指向原栈顶元素的下一个元素
    top = top.next;
    // 释放原栈顶元素的next引用
    oldTop.next = null;
    size--;
    return oldTop.data;
 
  }
 
  // 访问栈顶元素,但不删除栈顶元素
  public T peek(){
 
    return top.data;
 
  }
 
  // 判断链栈是否为空栈
  public boolean empty() {
 
    return size == 0;
 
  }
 
  // 请空链栈
  public void clear() {
 
    top = null;
    size = 0;
 
  }
 
  public String toString() {
 
    // 链栈为空栈时
    if (empty()) {
 
      return "[]";
 
    } else {
 
      StringBuilder sb = new StringBuilder("[");
      for (Node current = top; current != null; current = current.next) {
 
        sb.append(current.data.toString() + ", ");
 
      }
 
      int len = sb.length();
      return sb.delete(len - 2, len).append("]").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
package com.ietree.basic.datastructure.stack;
 
/**
 * Created by ietree
 * 2017/4/29
 */
public class LinkStackTest {
 
  public static void main(String[] args) {
 
    LinkStack<String> stack = new LinkStack<String>();
 
    stack.push("aaaa");
    stack.push("bbbb");
    stack.push("cccc");
    stack.push("dddd");
    System.out.println(stack);
 
    System.out.println("访问栈顶元素:" + stack.peek());
 
    System.out.println("第一次弹出栈顶元素:" + stack.pop());
 
    System.out.println("第二次弹出栈顶元素:" + stack.pop());
 
    System.out.println("两次pop之后的栈:" + stack);
 
  }
 
}

程序输出:

?
1
2
3
4
5
[dddd, cccc, bbbb, aaaa]
访问栈顶元素:dddd
第一次弹出栈顶元素:dddd
第二次弹出栈顶元素:cccc
两次pop之后的栈:[bbbb, aaaa]

感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!

原文链接:http://www.cnblogs.com/Dylansuns/p/6788961.html

标签:

相关文章

热门资讯

2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全 2019-12-26
Intellij idea2020永久破解,亲测可用!!!
Intellij idea2020永久破解,亲测可用!!! 2020-07-29
歪歪漫画vip账号共享2020_yy漫画免费账号密码共享
歪歪漫画vip账号共享2020_yy漫画免费账号密码共享 2020-04-07
电视剧《琉璃》全集在线观看 琉璃美人煞1-59集免费观看地址
电视剧《琉璃》全集在线观看 琉璃美人煞1-59集免费观看地址 2020-08-12
最新idea2020注册码永久激活(激活到2100年)
最新idea2020注册码永久激活(激活到2100年) 2020-07-29
返回顶部