链栈的java实现

2023-10-30 19:38

文章标签 java 实现链栈

本文主要是介绍链栈的java实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

链栈

栈的链式存储结构称为链栈。
在算法中要用到多个栈时，最好用链表作为栈的存储结构，即用指针来实现栈。用这种方式实现的栈也称为链栈。由于栈的插人和删除操作只在表头进行，因此用指针实现栈时没有必要像单链表那样设置一个表头单元。
一、链栈结构及数据类型
栈的链式存贮结构,也称为链栈，它是一种限制运算的链表，即规定链表中的插入和删除运算只能在链表开头进行。链栈结构见图。

链栈的java实现：

[java]  view plain copy  
 package study_02.test;  
   
   
 /** 
  * 链栈的实现 
  * @author WWX 
  * @param <T> 
  */  
 public class LinkStack<T> {  
     //定义节点数据结构  
     private class Node{  
         public T data;  
         public Node next;  
         //无参构造函数  
         public Node(){}  
           
         public Node(T data,Node next){  
             this.next=next;  
             this.data=data;  
         }  
     }  
     //栈顶元素  
     private Node top;  
     //元素个数  
     private  int size;  
     //插入数据  
     public void  push(T element){  
         top=new Node(element, top);  
         size++;  
     }  
       
     //出栈操作  
     public  T pop(){  
         Node  oldNode=top;  
         top=top.next;  
         //释放引用  
         oldNode.next=null;  
         size--;  
         return oldNode.data;  
     }  
     //返回栈顶的元素，但不出栈  
     public T peek(){  
         return top.data;  
           
     }  
     //堆栈长度  
     public int length(){  
         return  size;  
     }  
     // 判断链栈是否为空栈  
     public boolean empty() {  
         return 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();  
   
         }  
     }  
       
     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);  
     }  
 }  