Java数据结构--顺序栈

一时失言乱红尘 2023-10-06 09:32 13阅读 0赞

## `一、简介` ##

#### 1.1 概念 ####

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

> `顺序栈:`由于栈是运输受限的线性表，除了操作不同外，线性表的存储结构对栈也是适用的。  
> 利用顺序存储方式实现的栈称为顺序栈。

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

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

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

public class InitStack{
        
    
        private int [] stack = null;  　　　　//存储元素
    
        private int top = 0;  　　　　　　　　　//指示栈顶元素在顺序栈中的位置
    
        public InitStack(int max) {
          　　　　　//初始化自定义大小的顺序栈
            this.stack = new int[max];
        }
        
    	/**
    	* 清除栈
    	*/
        public void clearStack() {
        
        	this.top = 0;  　　　　　　　　//直接令栈顶指针指向栈底即可
    	}
    	
    	/**
    	* 检查顺序栈是否为空
    	*/
    	public boolean stackEmpty() {
        
    	    if(this.top == 0) {
          　　　　　　//检测栈顶指针是否指向栈底即可
    	        return true;
    	    }else {
        
    	        return false;
    	    }
    	}
    	
    	/**
    	* 返回顺序栈中元素个数
    	*/
    	public int stackLength() {
        
    		return this.top;  　　　　　　//栈顶指针的值即代表了元素个数
    	}
    	
    	/**
    	* 返回顺序栈的栈顶元素，不修改栈顶指针
    	*/
    	public int [] getTop() {
        
    	    if (this.top == 0) {
          　　　　　　//如果顺序栈为空，则返回空
    	        return null;
    	    }
    	
    	    int [] i = new int[1];
    	    i[0] = stack[this.top - 1]; 　  //获取栈顶元素
    	
    	    return i;
    	}
    	
    	/**
    	* 向顺序栈中压入元素
    	*/
    	public boolean push(int value) {
        
    	    if(this.top == this.stack.length) {
          　　//判断顺序栈是否已满
    	        return false;
    	    }
    	
    	    this.stack[this.top] = value;  　　　　　 //压入元素
    	    this.top++;  　　　　　　　　　　　　　　　　//栈顶指针加一
    	    return true;
    	}
    	
    	/**
    	* 从顺序栈顶中弹出元素
    	*/
       public int [] pop() {
        
    	    if (this.top == 0) {
          　　　　//判断顺序栈是否已空
    	        return null;
    	    }
    	
    	    int [] i = new int[1];
    	    this.top--;  　　　　　　　　　 //栈顶指针减一
    	    i[0] = stack[this.top];  　　//获取栈顶元素
    	    return i;
    	}
    
       /**
       * 从栈底到栈顶遍历顺序栈
       */
    	public String stackTraverse() {
          　　　　　　　　　　//通过输出顺序栈元素来表示遍历
    	    String s = "";  　　　　　　　　　　　　　　　　　 //存储要输出的元素
    	
    	    for (int i = 0; i < this.top; i++) {
          　　　　//循环遍历
    	        s += this.stack[i] + "、";
    	    }
    	
    	    if(s.length() == 0) {
          　　　　　　　　　　　　　//如果未获取到元素，返回空字符串
    	        return s;
    	    }
    	
    	    return s.substring(0,s.length() - 1);  　　　//除去最后一个顿号后返回
    	}
    
    }

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