当前位置：首页 > news >正文

长春朝阳网站建设/线上广告推广

news 2025/6/30 1:44:37

长春朝阳网站建设,线上广告推广,建设景区网站的目的,社区网站建设难点在上篇文章当中，我们实现了底层为数组的顺序栈。在我之前的文章中也提到过：以数组为数据结构基础在存储数据方面需要一整块连续的内存来存放数据，一旦遇到需要可以动态扩展的功能需求时如果数据量大可能会给虚拟机很大的压力导致频繁GC来获取…

　　在上篇文章当中，我们实现了底层为数组的顺序栈。在我之前的文章中也提到过：以数组为数据结构基础在存储数据方面需要一整块连续的内存来存放数据，一旦遇到需要可以动态扩展的功能需求时如果数据量大可能会给虚拟机很大的压力导致频繁GC来获取足够大的内存块。现在，为了避免这种问题的发生，我们通过另外一种方式实现栈的功能来避免这种问题。

　　首先我们定义定义Stack接口：

 1 package com.chen.arithmetic_test.stack_test;
 2 
 3 /**
 4  * Created by ChenMP on 2017/7/4.
 5  */
 6 public interface Stack {
 7     //入栈
 8     public void push(Object obj) throws Exception;
 9     //出栈
10     public Object pop() throws Exception;
11     //获得栈顶元素
12     public Object getTop() throws Exception;
13     //判断栈是否为空
14     public boolean isEmpty();
15 }

　　定义我们的节点元素类（当然，我们也可以将其定义为一个内部类）：

 1 package com.chen.arithmetic_test.stack_test;
 2 
 3 /**
 4  * Created by ChenMP on 2017/7/4.
 5  */
 6 public class Node {
 7     private Object nodeData; //该节点数据值
 8     private Node footNode;  //底部节点
 9 
10     public Node(Object nodeData) {
11         this.nodeData = nodeData;
12     }
13 
14     public Object getNodeData() {
15         return nodeData;
16     }
17 
18     public void setNodeData(Object nodeData) {
19         this.nodeData = nodeData;
20     }
21 
22     public Node getFootNode() {
23         return footNode;
24     }
25 
26     public void setFootNode(Node footNode) {
27         this.footNode = footNode;
28     }
29 
30     @Override
31     public String toString() {
32         return "Node{" +
33                 "nodeData=" + nodeData +
34                 '}';
35     }
36 }

　　编写LinkStack类：

 1 package com.chen.arithmetic_test.stack_test;
 2 
 3 /**
 4  * Created by ChenMP on 2017/7/4.
 5  */
 6 public class LinkStack implements Stack {
 7     private Node head; //栈顶元素
 8     private int size; //栈大小
 9     private int maxSize; //栈最大长度
10 
11     public LinkStack() {
12         this.head = null;
13         this.size = 0;
14         this.maxSize = 10; //设置栈默认大小为10
15     }
16 
17     public LinkStack(int maxSize) {
18         this.head = null;
19         this.size = 0;
20         this.maxSize = maxSize;
21     }
22 
23     @Override
24     public void push(Object obj) throws Exception {
25         if (size == maxSize)
26             throw new Exception("堆栈已满！");
27 
28         Node currentNode = new Node(obj);
29         currentNode.setFootNode(head);
30         this.head = currentNode;
31         size++;
32     }
33 
34     @Override
35     public Object pop() throws Exception {
36         if (0 == size)
37             throw new Exception("堆栈为空！");
38 
39         Node currentNode = this.head;
40         head = currentNode.getFootNode();
41         size--;
42         return currentNode;
43     }
44 
45     @Override
46     public Object getTop() throws Exception {
47         if (0 == size)
48             throw new Exception("堆栈为空！");
49 
50         return head;
51     }
52 
53     @Override
54     public boolean isEmpty() {
55         return size>0?false:true;
56     }
57 }

　　编写我们的测试类：

 1 package com.chen.arithmetic_test.stack_test;
 2 
 3 import java.util.Scanner;
 4 
 5 /**
 6  * Created by ChenMP on 2017/7/4.
 7  */
 8 public class TestStack {
 9     public static void main(String[] args) throws Exception {
10         // TODO Auto-generated method stub
11         LinkStack stack = new LinkStack(10);
12 
13         Scanner in = new Scanner(System.in);
14         int temp;
15         for(int i=0;i<10;i++)
16         {
17             System.out.println("请输入第"+(i+1)+"个整数：");
18             temp = in.nextInt();
19             stack.push(temp);
20         }
21 
22         while(!stack.isEmpty())
23         {
24             System.out.println(stack.pop());
25         }
26     }
27 }