java 栈操作模拟实现

落日映苍穹つ 2023-10-02 21:51 28阅读 0赞

#### 文章目录 ####

*  栈
 *   *  1 栈的基本认识
     *  2 栈操作实现思路
     *  3 栈模拟实现
     *   *  3.1 压栈模拟实现
         *  3.2 出栈模拟实现
         *  3.3 peek 操作实现

![52c70ded396f4e14b338df781a3d4f30.jpeg_pic_center][]

## 栈 ##

### 1 栈的基本认识 ###

栈只能从栈顶压入元素和从栈顶弹出元素，即**栈是一种先进后出的数据结构**~~  
![fdfd4096d72541e08907155648e411c7.png_pic_center][]  
**栈的下标是从栈底开始计算的~~**

*就像枪的弹夹一样，先压进去的子弹会最后打出来~  
如果想要将元素12弹出，就只能先将45、34、23依次弹出~*

![在这里插入图片描述][67c8181fff084bbaa8526530ec169bf3.png_pic_center]  
此时如果再弹出一个元素就是12了~~

### 2 栈操作实现思路 ###

1.  **压栈操作**（push）

*  定义一个usedSize来记录栈中的元素个数。
 *  栈顶的下标是元素个数减1。
 *  插入数值到栈顶的上一个位置。
 *  空间满了要考虑扩容。

**注意：**  
压栈后栈顶的下标要加1。  
栈的元素个数要加1个。  
访问栈顶下标就可以访问到栈顶的上一个位置。

1.  **出栈操作**（pop）

*  要首先判断栈是不是空的。
 *  栈顶元素是数组元素个数减1。
 *  直接返回栈顶下标。
 *  栈的元素个数减1个。

1.  **peek**操作（看一眼此时的栈顶元素，但是**不弹出**）

*  和出栈的操作类似，只是不会弹出栈顶元素。
 *  直接返回栈底元素。
 *  栈的元素个数不会减1个。

### 3 栈模拟实现 ###

#### 3.1 压栈模拟实现 ####

*插入前：*  
![53c69ec7b112462b8488b4eeb8b7a9f3.png_pic_center][]

*插入后：*  
![cc362aee484b4bd1be8e1158b6586ae9.png_pic_center][]  
  
  
*代码分析：*

1.  若栈的空间满了就返回true。

public boolean isFull(){
        
         //当前栈中元素个数等不等于数组的大小
         return this.usedSize == elem.length;
     }

1.  调用 isFull 方法并判断得到的值，如果为真则需要扩容。

if (isFull()) {
        
     }

1.  扩容的实现 - 利用方法 copyOf 来实现。

elem = Arrays.copyOf(elem, 2 * elem.length);//扩2倍

*整体代码实现*

public int push(int val) {
        
         if (isFull()) {
        
             //扩容
             elem = Arrays.copyOf(elem, 2 * elem.length);//扩2倍
         }
         this.elem[this.usedSize] = val;//从栈顶压入元素
         this.usedSize++;//元素个数加1
         return val;
     }
    
     public boolean isFull(){
        
         //当前栈中元素个数等不等于数组的大小
         return this.usedSize == elem.length;
     }

#### 3.2 出栈模拟实现 ####

![3504fa246e064fceb83bc1120ca935bc.png_pic_center][]  
弹出后栈的元素个数减1个。栈顶元素位置的下标也减少一个。  
  
  
**代码分析：**

1.  栈的元素个数等于0就返回true。

public boolean isEmpty() {
        
        return this.usedSize == 0;//为真就是空
    }

1.  判断此时的栈是不是空的，为空就抛一个异常。

if (isEmpty()) {
        
        //抛异常
        throw new MyemptyStackException("栈为空！！！");
    }

1.  弹出写法1的思路。

int ret = this.elem[this.usedSize - 1];
     this.usedSize--;//栈顶的位置减一个
     return ret;//返回栈顶的下标

ret 接收栈顶的下标。  
弹出后，栈的元素个数减1个。

1.  弹出写法2的思路。

return this.elem[--this.usedSize];

利用前置–，先减一个1，在返回栈顶下标。  
  
  
**整体代码实现:**  
  
写法1

public int pop() throws MyemptyStackException{
        
         if (isEmpty()) {
        
             //抛异常
             throw new MyemptyStackException("栈为空！！！");
         }
         int ret = this.elem[this.usedSize - 1];
         this.usedSize--;//栈顶的位置减一个
         return ret;//返回栈顶的下标
     }
    
     public boolean isEmpty() {
        
         return this.usedSize == 0;//为真就是空
     }

写法2

public int pop() throws MyemptyStackException{
        
        if (isEmpty()) {
        
            //抛异常
            throw new MyemptyStackException("栈为空！！！");
        }
        //简化
        return this.elem[--this.usedSize];
    }
    
    public boolean isEmpty() {
        
        return this.usedSize == 0;//为真就是空
    }

#### 3.3 peek 操作实现 ####

![5102a0f3ab654efea8f550b54c301662.png_pic_center][]  
此时的栈顶元素是45，只看一眼不会拿出，usedSize还是4。

**整体代码实现**

public int peek() throws MyemptyStackException{
        
        if (isEmpty()) {
        
            throw new MyemptyStackException("栈为空！！！");
        }
        return this.elem[this.usedSize - 1];//栈顶的位置不需要减一个
    }

![184ca3681f004da18b07e508e1103ba8.jpeg_pic_center][]

[52c70ded396f4e14b338df781a3d4f30.jpeg_pic_center]: https://img-blog.csdnimg.cn/52c70ded396f4e14b338df781a3d4f30.jpeg#pic_center
[fdfd4096d72541e08907155648e411c7.png_pic_center]: https://img-blog.csdnimg.cn/fdfd4096d72541e08907155648e411c7.png#pic_center
[67c8181fff084bbaa8526530ec169bf3.png_pic_center]: https://img-blog.csdnimg.cn/67c8181fff084bbaa8526530ec169bf3.png#pic_center
[53c69ec7b112462b8488b4eeb8b7a9f3.png_pic_center]: https://img-blog.csdnimg.cn/53c69ec7b112462b8488b4eeb8b7a9f3.png#pic_center
[cc362aee484b4bd1be8e1158b6586ae9.png_pic_center]: https://img-blog.csdnimg.cn/cc362aee484b4bd1be8e1158b6586ae9.png#pic_center
[3504fa246e064fceb83bc1120ca935bc.png_pic_center]: https://img-blog.csdnimg.cn/3504fa246e064fceb83bc1120ca935bc.png#pic_center
[5102a0f3ab654efea8f550b54c301662.png_pic_center]: https://img-blog.csdnimg.cn/5102a0f3ab654efea8f550b54c301662.png#pic_center
[184ca3681f004da18b07e508e1103ba8.jpeg_pic_center]: https://img-blog.csdnimg.cn/184ca3681f004da18b07e508e1103ba8.jpeg#pic_center