用Java实现栈（Stack）之链表实现

ゞ浴缸里的玫瑰 2022-07-12 08:52 230阅读 0赞

**使用链表实现栈**  
下面是节点类：

package com.yang.review;
    /**
     * 节点类
     * @author 阳
     *使用单链表实现栈
     */
    public class Node {
    	//值
    	Object value;
    	//指向下一个节点
    	Node next;
    	/**
    	 * 构造函数
    	 * @param value
    	 */
    	public Node(Object value){  
            this(value,null);  
        }  
    	/** 
         * 创建一个新的节点 
         * 让它的next指向，参数中的节点 
         * @param value 
         * @param n 
         */  
        public Node(Object value,Node n){  
            this.value=value;  
            next=n;  
        }  
       
    }

栈实现及测试类：

package com.yang.review;
    /**
     *-----------栈-------------
     * 下面的是使用链表实现栈        *
     * @author 阳                                     * 
     *栈是一种后进先出的数据结构 *
     *----------LIFO------------
     */
    public class Stack {
    	//栈顶元素
    	 Node top;
    	 int valueCount;//栈元素个数  
    	 int size;//栈大小 
    	 /*
    	  * 构造一个空栈
    	  */
    	 public Stack(){
    		 top = null;
    		 valueCount = 0;
    		 size = 0;
    	 }
    	 /*
    	  * 指定大小的栈
    	  */
    	 public Stack(int size){
    		 top = null;
    		 valueCount = 0;
    		 this.size = size;
    	 }
    	 /*
    	  * 初始化头节点
    	  */
    	 public void setTop(Node top) {  
    	        this.top=top;  
    	    }  
    	 /*
    	  * 判断栈是否已满
    	  */
    	 public boolean isFull() {  
    	        if (valueCount==size) {  
    	            return true;  
    	        }  
    	        return false;
    	 }
    	 /*
    	  * 判断栈是否为空
    	  */
    	 public boolean isEmpty() {  
    	        if (valueCount==0) {  
    	            return true;  
    	        }  
    	          
    	        return false;  
    	    }  
    	 /*
    	  * 返回栈顶元素
    	  */
    	 public Node peek(){
    		 if (this.isEmpty()) {  
    	            throw new RuntimeException("你操作的是空栈！");  
    	        }  
    	          
    	        return top ; 
    	 }
    	 /*
    	  * 出栈操作
    	  * 并且返回栈顶对象
    	  */
    	 public Node pop(){
    		 if (this.isEmpty()) {  
    	            throw new RuntimeException("你操作的是空栈！");  
    	        }  
    	        
    	          
    	        top=top.next;  
    	          
    	        valueCount--;  
    	          
    	        return top;  
    	 }
    	 /*
    	  * 入栈操作
    	  */
    	 public void push(Object value){
    		 if (this.isFull()) {  
    	            throw new RuntimeException("Stack is Full");  
    	        }  
    	        //注意这里面试将原来的header作为参数传入，然后以新new出来的Node作为header  
    	        top=new Node(value, top);  
    	        valueCount++;  
    	 }
    	public static void main(String[] args) throws Exception {
    		  //初始化栈大小
    	      Stack stack=new Stack(20);
    	      //测试入栈操作
    	      stack.push(new String("1"));        
    	      stack.push(new String("2"));        
    	      stack.push(new String("3"));        
    	      stack.push(new String("4"));        
    	      stack.push(new String("5"));
    	      //测试栈顶元素方法
    	      System.out.println("栈顶元素："+stack.peek().value);   
    	      //测试出栈操作
    	      while(stack.valueCount>1)        
    	      {        
    	          System.out.println("当前出栈元素："+stack.pop().value);        
    	      }   
    	}
    }

测试结果如下：  
![这里写图片描述][aHR0cDovL2ltZy5ibG9nLmNzZG4ubmV0LzIwMTcwMjE5MTUyNTUxNDAy]

[aHR0cDovL2ltZy5ibG9nLmNzZG4ubmV0LzIwMTcwMjE5MTUyNTUxNDAy]: /images/20220710/c9712d8e3a1048baa6e6925abb82ce63.png