数据结构：栈(Stack)的各种操作（入栈，出栈，判断栈非空，判断栈已满，附源码）

傷城~ 2024-02-05 14:30 57阅读 0赞

![398a665653964c3094664149862dba7e.gif][]

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

> **前言：**在前面的文章中，我们讲解了**顺序表，单链表，双向链表**。而我们今天要分享的栈则是基于之前的数据结构上搭建的，但是相较于顺序表和链表来说，栈的实现就非常简单了。

**目录**

一.栈(Stack)的概念

二.栈的数据结构

三.栈的实现

判断栈已满

判断栈非空

入栈push

出栈pop

查看栈顶元素

完整代码

Java版本

c语言版

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

## 一.栈(Stack)的概念 ##

栈是一种先进后出（LIFO）的数据结构，在其中元素的的添加（称为“入栈”）和删除（称为“出栈”）仅在栈的顶部进行。因此，最后一个插入到栈中的元素是第一个从栈中删除的元素。

它通常有两个主要操作：

*  **push：**在栈的顶部插入一个元素。
 *  **pop：**从栈的顶部移除一个元素。

栈的**push**入栈图解：

![3cff18a424284030bafb283ae89043d6.png][]

栈的**pop**出栈图解 ：

![b364e82cd9e1409eb9b1bdaafee4827d.png][]

我们可以看见对于栈的操作，我们都是在栈顶上操作的，先进来的元素会被后面的元素覆盖，而最后一个进来的元素也就是栈顶，因此我们称为**先进后出（LIFO）**

像传统的狙击步枪的弹夹就属于是一种栈的结构

![c4685f649e89405daed12325a8f9cfdf.png][]

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

## 二.栈的数据结构 ##

对于栈的实现，我们通常使用数组，当然也可以使用链表，不过相对而言数组的实现是更容易的。

而对于一个栈的数据结构，他首先得有存放元素的位置，我们这里选择用数组来存放，其次还得有栈内元素个数的记录：

public class MyStack {
        public int[] elem;
        public int usedSize;
    }

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

## 三.栈的实现 ##

对于一个栈，他应该有以下这些功能：

*  入栈
 *  出栈
 *  判断栈是否为空
 *  判断栈已满
 *  查看栈顶元素

### 判断栈已满 ###

当已经使用的数组的大小等于数组本身的大小的时候，栈就相当于满了

public boolean isFull() {
            return usedSize == elem.length;
        }

### 判断栈非空 ###

当数组内一个元素都没有，也就是已经使用的数组大小为0的时候，栈就是空的

public boolean isEmpety() {
            return usedSize == 0;
        }

### 入栈push ###

当我们要将元素放入栈内的时候，先进行判断，只有在栈内还有剩余空间的情况下，我们才会进行入栈操作，如果没有剩余空间，我们就进行扩容

![68680320e0ff4f66b60714091737d10b.png][]

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

### 出栈pop ###

出栈前要先进行判断，如果栈内一个元素都没有，那自然是不能进行出栈操作的，我们就抛出一个自定义异常然后抛出；对于正常的出栈操作，我们拿出栈顶的元素，然后让记录数组的个数减一

public int pop() {
            if (isEmpety()) {
                //栈为空，无法出栈
                throw new EmptyStackException("栈为空，无法弹出");
            }
            int popNumber = elem[usedSize-1];
            usedSize--;
            return popNumber;
        }

### 查看栈顶元素 ###

和出栈不一样的是，查看栈顶元素只是将元素拿出来展示，并没有实际上删除这个元素

public int peek() {
            if (isEmpety()) {
                //栈为空，无法出栈
                throw new EmptyStackException("栈为空，无法弹出");
            }
            return elem[usedSize - 1];
        }

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

## 完整代码 ##

栈的整体实现相较于顺序表和链表是非常简单的，这里附上完整代码

### Java版本 ###

import java.util.Arrays;
    
    public class MyStack {
        public int[] elem;
        public int usedSize;
        public static int DEFULT_SIZE = 10;
        
        public MyStack() {
            this.elem = new int[DEFULT_SIZE];
        }
        
        public void push(int val) {
            if (isFull()) {
                //扩容
                elem = Arrays.copyOf(elem, elem.length * 2);
            }
            elem[usedSize++] = val;
        }
        
        public int pop() {
            if (isEmpety()) {
                //栈为空，无法出栈
                throw new EmptyStackException("栈为空，无法弹出");
            }
            int popNumber = elem[usedSize-1];
            usedSize--;
            return popNumber;
        }
        
        public int peek() {
            if (isEmpety()) {
                //栈为空，无法出栈
                throw new EmptyStackException("栈为空，无法弹出");
            }
            return elem[usedSize - 1];
        }
        
        public boolean isFull() {
            return usedSize == elem.length;
        }
        
        public boolean isEmpety() {
            return usedSize == 0;
        }
    
    }

### c语言版 ###

#include <stdio.h>
    #include <stdlib.h>
    
    #define STACK_SIZE 10
    
    // 定义栈结构体
    typedef struct {
        int data[STACK_SIZE];  // 存放数据的数组
        int top;               // 栈顶指针
    } Stack;
    
    // 初始化栈
    void init_stack(Stack *s) {
        s->top = -1;  // 栈顶初始化为-1
    }
    
    // 判断栈是否为空
    int is_empty(Stack *s) {
        return s->top == -1;
    }
    
    // 判断栈是否已满
    int is_full(Stack *s) {
        return s->top == STACK_SIZE-1;
    }
    
    // 入栈
    void push(Stack *s, int value) {
        if (is_full(s)) {
            printf("Stack overflow\n");
            exit(1);
        }
        s->data[++s->top] = value;  // 栈顶指针先加1，再将元素入栈
    }
    
    // 出栈
    int pop(Stack *s) {
        if (is_empty(s)) {
            printf("Stack underflow\n");
            exit(1);
        }
        return s->data[s->top--];  // 先将元素出栈，再将栈顶指针减1
    }
    
    // 获取栈顶元素
    int peek(Stack *s) {
        if (is_empty(s)) {
            printf("Stack underflow\n");
            exit(1);
        }
        return s->data[s->top];
    }

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

![b4e223eb39274c4790c1accda528968f.png][] **本次的分享就到此为止了，希望我的分享能给您带来帮助，也欢迎大家三连支持，你们的点赞就是博主更新最大的动力！**![dee54f8cb32a413fb28d115ba29feb97.png][]**如有不同意见，欢迎评论区积极讨论交流，让我们一起学习进步！**![08cf81c9e3f84f6fb5e5805897ac6d8e.png][]**有相关问题也可以私信博主，评论区和私信都会认真查看的，我们下次再见**![08cf81c9e3f84f6fb5e5805897ac6d8e.png][]

[398a665653964c3094664149862dba7e.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/09304d12678d4506a8060806a62ef41e.png
[3cff18a424284030bafb283ae89043d6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/a1c565640bbe409194e9df89bb2d4289.png
[b364e82cd9e1409eb9b1bdaafee4827d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/c5cb91d82d734dc48c0b58a89677ec13.png
[c4685f649e89405daed12325a8f9cfdf.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/603dc056e07d479aba025d7d9f25a72d.png
[68680320e0ff4f66b60714091737d10b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/53acc33035f946cc83bd7e8f582507a4.png
[b4e223eb39274c4790c1accda528968f.png]: https://img-blog.csdnimg.cn/b4e223eb39274c4790c1accda528968f.png
[dee54f8cb32a413fb28d115ba29feb97.png]: https://img-blog.csdnimg.cn/dee54f8cb32a413fb28d115ba29feb97.png
[08cf81c9e3f84f6fb5e5805897ac6d8e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/f8b9e4ab1825454bab31435fd2d79d6a.png