java学习笔记(基础篇)—数组模拟实现栈

浅浅的花香味﹌ 2021-11-15 11:52 343阅读 0赞

## 栈的概念 ##

*  先进后出策略(LIFO)
 *  是一种基本数据结构
 *  栈的分类有两种：1.静态栈（数组实现） 2.动态栈（链表实现）
 *  栈的模型图如下：  
    ![栈模型][1561653-20190605205824729-933376158.jpg]

## 需求分析 ##

在编写代码之前，我习惯先对要实现的程序进行需求分析，比如用什么数据结构存储数据，需要实现哪些基本的功能等。这次是通过数组模拟实现栈，所以是一个静态栈，但是我在栈满时通过arraycopy函数自动扩容，后面会细说。  
我们要实现的功能至少应该包含以下功能：

public class Stack {
        private int[] array;//模拟栈
        private int length = 0;//栈总长度
        private int size = 0;//栈存在元素个数
        
        public Stack() {
            this(10);
        }
        public Stack(int length) {
            array = new int[length];
            this.length = length;
        }
        //入栈
        public void push(int num) {}
        
        //出栈
        public int pop() {}
        
        //栈是否为空
        public boolean isEmpty() {}
        
        //栈是否已满,已满则每次扩容5个单位
        public boolean isFull() {}
        
        //清除栈所有元素
        public void removeAll() {}
        
        //获取栈内存在元素个数
        public int getSize() {}
        
        //获取栈的总长度
        public int getLength() {}
    }

## 具体实现 ##

1.  入栈push()  
    首先判断当前栈是否已满，如果已满则扩容；此时栈内存在元素size增加1。

//入栈
        public void push(int num) {
            isFull();
            array[length-1-size] = num;
            size++;
        }

1.  出栈pop()  
    判断当前栈是否为空，为空则返回0；不为空，将数组中最靠近下标0的非0元素置0；此时栈内元素size减1，并返回出栈的值；

//出栈
        public int pop() {
            if(isEmpty()) {
                return 0;
            }
            int result = 0;
            for (int i = 0; i < array.length; i++) {
                if (array[i]==0) {
                    continue;
                }
                result = array[i];
                array[i] = 0;
                size--;
                break;
            }
            return result;
        }

1.  栈是否为空isEmpty()

//栈是否为空
        public boolean isEmpty() {
            if(size==0) {
                System.out.println("栈为空！");
                return true;
            }
            return false;
        }

1.  栈是否已满,已满则每次扩容5个单位isFull()  
    如果栈内存在的元素个数等于数组长度，则表示栈已满；通过new一个新的更大的数组，调用arraycopy方法将b的引用赋给array，并且数组的长度也要加长。  
    arraycopy()的参数含义如下：

/**
             * 参数含义
             * @param src 原数组对象的引用
             * @param srcPos 原数组要拷贝的数据的原始位置
             * @param dest 目标数组对象的引用
             * @param destPos 目标数组要拷贝的数据的原始位置
             * @param length 原数组要拷贝的长度
             */
               public static native void arraycopy(Object src,  int  srcPos,Object dest, int destPos, int length);

//栈是否已满,已满则每次扩容5个单位
        public boolean isFull() {
            if (size==length) {
                //System.out.println("当前栈已满，扩容5个单位。");
                int[] b = new int[length+5]; 
                System.arraycopy(array, 0, b, 5, length);
                array = b;
                this.length += 5;
                return true;
            }
            return false;
        }

1.  清除栈所有元素removeAll()  
    清除所有元素就是遍历一遍数组，将全部元素的值置0；

//清除栈所有元素
        public void removeAll() {
            for (int i = 0; i < array.length; i++) {
                if (array[i]!=0) {
                    array[i] = 0;
                    size--;
                }
            }
        }

1.  获取栈内存在元素个数getSize()

//获取栈内存在元素个数
        public int getSize() {
            return size;
        }

1.  获取栈的总长度getLength()

//获取栈的总长度
        public int getLength() {
            return length;
        }

## 测试 ##

public class StackTest {
        public static void main(String[] args) {
            //创建一个默认长度为10的栈
            Stack stack = new Stack(2);
            //入栈
            stack.push(10);
            stack.push(9);
            stack.push(8);
            System.out.println("当前栈元素个数:"+stack.getSize());
            System.out.println("当前栈的总长度:"+stack.getLength());
            stack.printStack();
            
            //出栈
            int p = stack.pop();
            System.out.println("当前出栈元素的值:"+p);
            System.out.println("当前栈元素个数:"+stack.getSize());
            System.out.println("当前栈的总长度:"+stack.getLength());       
            stack.printStack();
            
            //清空栈
            stack.removeAll();
            //stack.isEmpty();
            int p2 = stack.pop();
            System.out.println("当前出栈元素的值:"+p2);
            System.out.println("当前栈元素个数:"+stack.getSize());
            System.out.println("当前栈的总长度:"+stack.getLength());   
        }
    }

测试结果：

当前栈元素个数:3
    当前栈的总长度:7
    当前栈情况:8 9 10 
    当前出栈元素的值:8
    当前栈元素个数:2
    当前栈的总长度:7
    当前栈情况:9 10 
    栈为空！
    当前出栈元素的值:0
    当前栈元素个数:0
    当前栈的总长度:7

欢迎访问我的个人网站[www.chlinlearn.cn][]  
到这里就要结束了，后续如果有时间也会出一篇链表实现栈的文章，欢迎来访问我的[个人网站][www.chlinlearn.cn]，最新文章都会首先在那里发布哦^^

转载于:https://www.cnblogs.com/chlinlearn/p/10981885.html

[1561653-20190605205824729-933376158.jpg]: /images/20211115/df5a10cbd83d4b0fb60222196dd16d7d.png
[www.chlinlearn.cn]: http://www.chlinlearn.cn