栈的数组实现方式

电玩女神 2021-11-29 07:22 290阅读 0赞

一，栈ADT（抽象数据类型）

栈是限制插入和删除只能在一个为位置上进行的表，该位置是表的末端，叫做栈的顶(top)

对栈的基本操作有Push(进栈) 和 Pop（出栈），前者相当插入，后者相当删除最后插入的元素

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nZG9uZ25paGFv_size_16_color_FFFFFF_t_70][]

二，  用一个数组实现栈是很简单的。每一个栈都有一个TopOfStack，对于空栈它是-1（这是空栈的初始化）

为了将某个元素X压入该栈，我们将TopOfStack加1，然后置stack\[TopOfStack\] =X,其stack是代表具体的栈的数据

为了弹出栈元素，我们置返回值为stack\[TopOfStack\] ，然后 TopOfStack减1.

栈的声明--数据实现

public class StackRecord {
    
       int capacity;//栈的容量
       int TopOfStack;//栈顶元素
       int[] array;//数组
    }

栈的创建

public static int EmptyTOs=-1;
        public static int MaxStackSize=5;
        
        public StackRecord CreateStack(int MaxStackSize){
        	StackRecord s;
        	
        	if(MaxStackSize <  MaxStackSize){
        		System.out.println(" stack size is too small");
        	}
        	s = new  StackRecord();
        	if(s==null){
        		System.out.println("create fail");
        	}
        	s.array=new int[MaxStackSize];
        	s.capacity=MaxStackSize;
        	MakeEmpty(s);
        	return s;
        }

创建一个空栈

public void MakeEmpty(StackRecord s){
        	s.TopOfStack=EmptyTOs;
        }

元素进栈

public void Push(int x, StackRecord s){
        	if(s == null){
        		System.out.println("full empty");
        	}else{
        		s.array[ ++s.TopOfStack ]=x;
        	}
        }

给出栈顶元素并从栈弹出

public int TopAndPop(StackRecord s){
            if(!ISEmpty(s)){
                return s.array[s.TopOfStack--];
            }
            System.out.println("Empty stack");
            return 0;
        }

判断栈为空

public  Boolean  ISEmpty(StackRecord s){
        	return s.TopOfStack == EmptyTOs;
        }

为释放栈，先释放栈结构，在释放数组

public void disposeStack(StackRecord s){
        	if(s!=null){
        		s.array=null;
        		System.gc();
        	}
        }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nZG9uZ25paGFv_size_16_color_FFFFFF_t_70]: /images/20211129/1dea3495946f4fb7bfe86e65e29960d8.png