前言：在前面的文章中，我们讲解了顺序表，单链表，双向链表。而我们今天要分享的栈则是基于之前的数据结构上搭建的，但是相较于顺序表和链表来说，栈的实现就非常简单了。
目录
一.栈(Stack)的概念
二.栈的数据结构
三.栈的实现
判断栈已满
判断栈非空
入栈push
出栈pop
查看栈顶元素
完整代码
Java版本
c语言版
一.栈(Stack)的概念
栈是一种先进后出（LIFO）的数据结构，在其中元素的的添加（称为“入栈”）和删除（称为“出栈”）仅在栈的顶部进行。因此，最后一个插入到栈中的元素是第一个从栈中删除的元素。
它通常有两个主要操作：
push：在栈的顶部插入一个元素。pop：从栈的顶部移除一个元素。
栈的push入栈图解：
栈的pop出栈图解 ：
我们可以看见对于栈的操作，我们都是在栈顶上操作的，先进来的元素会被后面的元素覆盖，而最后一个进来的元素也就是栈顶，因此我们称为先进后出（LIFO）
像传统的狙击步枪的弹夹就属于是一种栈的结构
二.栈的数据结构
对于栈的实现，我们通常使用数组，当然也可以使用链表，不过相对而言数组的实现是更容易的。
而对于一个栈的数据结构，他首先得有存放元素的位置，我们这里选择用数组来存放，其次还得有栈内元素个数的记录：
public class MyStack {
public int[] elem;
public int usedSize;
}
三.栈的实现
对于一个栈，他应该有以下这些功能：
入栈出栈判断栈是否为空判断栈已满查看栈顶元素
判断栈已满
当已经使用的数组的大小等于数组本身的大小的时候，栈就相当于满了
public boolean isFull() {
return usedSize == elem.length;
}
判断栈非空
当数组内一个元素都没有，也就是已经使用的数组大小为0的时候，栈就是空的
public boolean isEmpety() {
return usedSize == 0;
}
入栈push
当我们要将元素放入栈内的时候，先进行判断，只有在栈内还有剩余空间的情况下，我们才会进行入栈操作，如果没有剩余空间，我们就进行扩容
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
#include
#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];
}
本次的分享就到此为止了，希望我的分享能给您带来帮助，也欢迎大家三连支持，你们的点赞就是博主更新最大的动力！如有不同意见，欢迎评论区积极讨论交流，让我们一起学习进步！有相关问题也可以私信博主，评论区和私信都会认真查看的，我们下次再见