Java数据结构--链栈

迷南。 2023-10-06 09:32 23阅读 0赞

## `一、简介` ##

#### 1.1 概念 ####

> `栈:`又称为堆栈，是限制在表的一端进行插入和删除的线性表。其限制是仅允许在表的一端进行插入和删除操作，不允许在其他任何位置进行插入、查找、删除等操作。  
> 表中进行插入、删除操作的一端称为栈顶、栈顶保存的元素称为栈顶元素。相对的，表的另一端称为栈底。当栈中没有数据元素时，称为空栈；向一个栈中插入元素又称为进栈或入栈；从一个栈中删除元素又称为出栈或退栈。  
> 由于栈的插入和删除操作都仅在栈顶进行，后进栈的元素必定先出栈，所以又把堆栈称为后进先出表。

> `链栈--`用链式存储结构实现的栈称为链栈；其结构特点与单链表的结构相同，链式堆栈也是由一个个结点组成的，每个结点由两个域组成，一个是存放数据元素的数据元素域，另一个是存放指向向下一个节点的对象的引用域；因为栈中主要是在栈顶进行操作，所以在链表的头部做栈顶是最方便的，而且不用添加头结点。

#### 1.2 结构图 ####

> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx_size_16_color_FFFFFF_t_70]

## `二、简单实现` ##

/*链栈的java实现*/
    public class Stack{
        
    
        /*定义两个指针目的是分别指向栈底和栈顶*/
        private Element base ;
        private Element top ;
    
        /*栈中的数据模型*/
        class Element{
        
            public Object data ;                     //栈中元素
            Element next ;                           //下一个元素
        }
    
        /*初始化*/
        public void init(){
        
            Element elem = new Element() ;           //开辟一个元素的空间作为栈底
            base = elem ;                            //top指针和base指针初始化
            top =  elem ;
            base.data = null ;
            //System.out.println("栈已初始化");
        }
    
        /*压栈操作*/
        public void push(Object obj){
        
            Element elem = new Element() ;           // 入栈元素分配空间
            elem.data = obj ;                        // 将元素放入
            elem.next = top ;                        // 元素指针指向当前top所指元素
            top = elem ;                             // 修改top指针
            //System.out.println(top.data+" 压栈成功");
        }
    
        /*退栈操作*/
        public Object pop(){
        
            if(this.isEmpty()){
        
                System.out.println("退栈失败，栈为空！");
                return null ;
            }
            Object obj = top.data ;                   //取出对象的值
            top = top.next ;                          //修改top指针
            //System.out.println(obj+" 退栈成功");
            return obj ;                              //返回元素
        }
    
        /*判断栈是否为空*/
        public boolean isEmpty(){
        
            if(base == top)                           //若栈顶栈底指针相同，则为空否则非空
                return true ;
            else
                return false ;
        }
    
        /*清空栈*/
        public void clear(){
        
            while(!this.isEmpty()){
        
                this.pop() ;
            }
            System.out.println("栈已清空");
        }
    
        /*获取栈的大小*/
        public int size(){
        
            int n = 0 ;
            Element flag = top ;
            while(flag!=base){
        
                flag = flag.next ;
                n++ ;
            }
            return n ;
        }
    
        /*获取栈顶元素*/
        public Element getTop(){
        
            return top ;
        }
    
        /*遍历栈，输出栈的元素*/
        public void print(){
        
            if(this.isEmpty()){
                                //若栈空
                System.out.println("输出失败，栈为空！");
            }else{
        
                Element flag = top ;
                System.out.print("栈中元素为：");
                while(flag != base){
        
                    System.out.print(flag.data+" ");
                    flag = flag.next ;
                }
            }
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200525224040303.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx,size_16,color_FFFFFF,t_70