java 栈操作模拟实现

栈

1 栈的基本认识

栈只能从栈顶压入元素和从栈顶弹出元素，即栈是一种先进后出的数据结构~~

栈的下标是从栈底开始计算的~~

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

此时如果再弹出一个元素就是12了~~

2 栈操作实现思路

1. 压栈操作（push）

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

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

2. 出栈操作（pop）

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

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

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

3 栈模拟实现

3.1 压栈模拟实现

插入前：

插入后：



代码分析：

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

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

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

 if (isFull()) {
 }
1
2

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

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

整体代码实现

 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;
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

3.2 出栈模拟实现

弹出后栈的元素个数减1个。栈顶元素位置的下标也减少一个。


代码分析：

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

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

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

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

3. 弹出写法1的思路。

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

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

4. 弹出写法2的思路。

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

利用前置–，先减一个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;//为真就是空
 }
1
2
3
4
5
6
7
8
9
10
11
12
13

写法2

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

public boolean isEmpty() {
    return this.usedSize == 0;//为真就是空
}
1
2
3
4
5
6
7
8
9
10
11
12

3.3 peek 操作实现

此时的栈顶元素是45，只看一眼不会拿出，usedSize还是4。

整体代码实现

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