Java数据结构——栈的方法与模拟实现

亦凉 2023-10-10 15:04 14阅读 0赞

![ced485cbb11e458d81a746890b32cf3f.gif][]

> 作者：敲代码の流川枫
> 
> 博客主页：[流川枫的博客][Link 1]
> 
> 专栏：[和我一起学java][java]
> 
> 语录：Stay hungry stay foolish
> 
> 工欲善其事必先利其器，给大家介绍一款超牛的斩获大厂offer利器——牛客网
> 
> [点击注册和我一起刷题][Link 2]

**文章目录**

1.栈的基本概念

栈（stack）

Stack的源码

2.栈的方法

push和pop

peek

empty

3.用数组实现栈

创建一个栈

实现push方法

实现pop方法

实现peek方法

测试

--------------------

## 1.栈的基本概念 ##

### 栈（stack） ###

又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

栈作为一种[数据结构][Link 3]，是一种只能在一端进行插入和删除操作的特殊[线性表][Link 4]。它按照后进先出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。栈具有记忆作用，对栈的插入与删除操作中，不需要改变栈底[指针][Link 5]。

栈是允许在同一端进行插入和删除操作的特殊[线性表][Link 4]。允许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)；栈底固定，而栈顶浮动；栈中元素个数为零时称为空栈。插入一般称为[进栈][Link 6]（PUSH），删除则称为退栈（POP）。栈也称为先进后出表。

![5ce405e93e694a7db32c9dd155677764.png][]

### Stack的源码 ###

![31f85836de3548fc877620d6b67d3987.png][]

源码中我们发现并没有成员， 我们注意到它继承了Vector类，打开Vector的源码可以看出栈的底层实际上是数组

![93bdb24a578e4bc98194b0e0b072de7a.png][]

## 2.栈的方法 ##

![05d0b0c6bad64c70926839c7a6b1350f.png][]

### push和pop ###

即入栈和出栈

![e49d2fb31d4846e0ab482f3104384f59.png][]

可以看出栈的先进后出的特点

### peek ###

peek方法是指只获得栈顶元素，不删除

public static void main(String[] args) {
            Stack<Integer> stack = new Stack<>();
            stack.add(12);
            stack.add(23);
            stack.add(34);
            int x = stack.pop();
            System.out.println("x = "+x);
            int y = stack.pop();
            System.out.println("y = "+y);
            System.out.println("===========");
            int z = stack.peek();
            System.out.println("z = "+z);
            System.out.println("===========");
            System.out.println("stack = "+stack);
        }

![3b39185819664a95bbea10c9084010a0.png][]

### empty ###

判断栈是否为空

![b2de07555fda4a6d9b33295ddf65e081.png][]

## 3.用数组实现栈 ##

### 创建一个栈 ###

class MyStack{
        public int[] elem;
        public int usedSize;
        public static final int DEFAULT_SIZE = 10;
    
        public MyStack(){
            this.elem = new int[DEFAULT_SIZE];
        }
    }

### 实现push方法 ###

需要判断栈是否满了，如果满了需要扩容之后再进行压栈

public int push(int val){
            if(isFull()){
                elem = Arrays.copyOf(elem,2*elem.length);
            }
            elem[usedSize] = val;
            usedSize++;
            return val;
        }
        public boolean isFull(){
            return usedSize == elem.length;
        }

### 实现pop方法 ###

先判断栈是否为空，不为空，直接返回usedSize-1下标的值，并且usedSize--；

public int pop(){
            if(empty()){
                throw new StackEmptyException("栈为空");
            }
            return elem[--usedSize];
        }
        public boolean empty(){
            return usedSize == 0;
        }

### 实现peek方法 ###

先判断是否为空，不为空 返回usedSize-1下标的值

public int peek(){
            if(empty()){
                throw new StackEmptyException("栈为空");
            }
            return elem[usedSize-1];
        }

我们知道pop是栈顶元素出栈，peek只是得到栈顶元素，不改变栈![2081f7a378a74147a680ac8c8a5b81a8.png][]

> **两个返回值的差异**
> 
> **pop之后usedSize本身的大小会减小，改变了栈**
> 
> **peek中usedSize本身并不改变，因此不会改变栈**

### 测试 ###

public static void main(String[] args) {
            MyStack myStack = new MyStack();
            myStack.push(1);
            myStack.push(2);
            myStack.push(3);
            int x = myStack.pop();
            System.out.println("X = "+x);
            int y = myStack.peek();
            System.out.println("y = "+y);
            int x1 = myStack.peek();
            System.out.println("x1 = "+x1);
            int y1 = myStack.peek();
            System.out.println("y1 = "+y1);
    
        }

![0362af4b29fa4245abc8a182e9aa2292.png][]

> “ 本期的分享就到这里了， 记得给博主一个三连哈，你的支持是我创作的最大动力！

![ced485cbb11e458d81a746890b32cf3f.gif][]

[ced485cbb11e458d81a746890b32cf3f.gif]: https://img-blog.csdnimg.cn/ced485cbb11e458d81a746890b32cf3f.gif
[Link 1]: https://blog.csdn.net/chenchenchencl?spm=1011.2421.3001.5343
[java]: https://blog.csdn.net/chenchenchencl/category_11932758.html
[Link 2]: https://www.nowcoder.com/link/pc_csdncpt_qdmdlcf_c
[Link 3]: https://baike.baidu.com/item/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84?fromModule=lemma_inlink
[Link 4]: https://baike.baidu.com/item/%E7%BA%BF%E6%80%A7%E8%A1%A8?fromModule=lemma_inlink
[Link 5]: https://baike.baidu.com/item/%E6%8C%87%E9%92%88?fromModule=lemma_inlink
[Link 6]: https://baike.baidu.com/item/%E8%BF%9B%E6%A0%88?fromModule=lemma_inlink
[5ce405e93e694a7db32c9dd155677764.png]: https://img-blog.csdnimg.cn/5ce405e93e694a7db32c9dd155677764.png
[31f85836de3548fc877620d6b67d3987.png]: https://img-blog.csdnimg.cn/31f85836de3548fc877620d6b67d3987.png
[93bdb24a578e4bc98194b0e0b072de7a.png]: https://img-blog.csdnimg.cn/93bdb24a578e4bc98194b0e0b072de7a.png
[05d0b0c6bad64c70926839c7a6b1350f.png]: https://img-blog.csdnimg.cn/05d0b0c6bad64c70926839c7a6b1350f.png
[e49d2fb31d4846e0ab482f3104384f59.png]: https://img-blog.csdnimg.cn/e49d2fb31d4846e0ab482f3104384f59.png
[3b39185819664a95bbea10c9084010a0.png]: https://img-blog.csdnimg.cn/3b39185819664a95bbea10c9084010a0.png
[b2de07555fda4a6d9b33295ddf65e081.png]: https://img-blog.csdnimg.cn/b2de07555fda4a6d9b33295ddf65e081.png
[2081f7a378a74147a680ac8c8a5b81a8.png]: https://img-blog.csdnimg.cn/2081f7a378a74147a680ac8c8a5b81a8.png
[0362af4b29fa4245abc8a182e9aa2292.png]: https://img-blog.csdnimg.cn/0362af4b29fa4245abc8a182e9aa2292.png