[Java算法分析与设计]--链式堆栈的设计

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

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

package com.chen.arithmetic_test.stack_test;
 
 /**
  * Created by ChenMP on 2017/7/4.
  */
 public interface Stack {
     //入栈
     public void push(Object obj) throws Exception;
     //出栈
     public Object pop() throws Exception;
     //获得栈顶元素
     public Object getTop() throws Exception;
     //判断栈是否为空
     public boolean isEmpty();
 }

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

package com.chen.arithmetic_test.stack_test;
 
 /**
  * Created by ChenMP on 2017/7/4.
  */
 public class Node {
     private Object nodeData; //该节点数据值
     private Node footNode;  //底部节点
 
     public Node(Object nodeData) {
         this.nodeData = nodeData;
     }
 
     public Object getNodeData() {
         return nodeData;
     }
 
     public void setNodeData(Object nodeData) {
         this.nodeData = nodeData;
     }
 
     public Node getFootNode() {
         return footNode;
     }
 
     public void setFootNode(Node footNode) {
         this.footNode = footNode;
     }
 
     @Override
     public String toString() {
         return "Node{" +
                 "nodeData=" + nodeData +
                 '}';
     }
 }

编写LinkStack类：

package com.chen.arithmetic_test.stack_test;
 
 /**
  * Created by ChenMP on 2017/7/4.
  */
 public class LinkStack implements Stack {
     private Node head; //栈顶元素
     private int size; //栈大小
     private int maxSize; //栈最大长度
 
     public LinkStack() {
         this.head = null;
         this.size = 0;
         this.maxSize = 10; //设置栈默认大小为10
     }
 
     public LinkStack(int maxSize) {
         this.head = null;
         this.size = 0;
         this.maxSize = maxSize;
     }
 
     @Override
     public void push(Object obj) throws Exception {
         if (size == maxSize)
             throw new Exception("堆栈已满！");
 
         Node currentNode = new Node(obj);
         currentNode.setFootNode(head);
         this.head = currentNode;
         size++;
     }
 
     @Override
     public Object pop() throws Exception {
         if (0 == size)
             throw new Exception("堆栈为空！");
 
         Node currentNode = this.head;
         head = currentNode.getFootNode();
         size--;
         return currentNode;
     }
 
     @Override
     public Object getTop() throws Exception {
         if (0 == size)
             throw new Exception("堆栈为空！");
 
         return head;
     }
 
     @Override
     public boolean isEmpty() {
         return size>0?false:true;
     }
 }

编写我们的测试类：

package com.chen.arithmetic_test.stack_test;
 
 import java.util.Scanner;
 
 /**
  * Created by ChenMP on 2017/7/4.
  */
 public class TestStack {
     public static void main(String[] args) throws Exception {
         // TODO Auto-generated method stub
         LinkStack stack = new LinkStack(10);
 
         Scanner in = new Scanner(System.in);
         int temp;
         for(int i=0;i<10;i++)
         {
             System.out.println("请输入第"+(i+1)+"个整数：");
             temp = in.nextInt();
             stack.push(temp);
         }
 
         while(!stack.isEmpty())
         {
             System.out.println(stack.pop());
         }
     }
 }

通过上面的代码，我们学习到了通过节点来实现我们自己的堆栈结构，其实在java.util.Stack中，它的实现便是使用了数组为底层来实现的。但是在学习知识的过程中，我们最好能学会举一反三，这样我们才能更好的进步，你说对不对？