文章目录
1.栈
1.1 栈的定义
1.2 C语言实现栈
1.2.1接口函数
1.2.2栈的创建
1.2.3栈的初始化
1.2.4栈的销毁
1.2.5压栈
1.2.6出栈
1.2.7判断栈是否为空
1.2.8取栈顶元素
1.2.9 栈有多少个数据
1.3 C语言实现栈的具体代码
头文件stack.h
接口函数stack.c
测试函数test.c
1.栈
1.1栈的定义
栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。简单地来说，栈内存储的数据，具有“后进先出”的特性。
栈就类似于客栈，客栈是存储货物或供旅客住宿的地方,可引申为仓库、中转站，所以引入到计算机领域里，就是指数据暂时存储的地方。如下图，原来的栈空间有a1、a2、a3、a4这四个元素，然后插入元素a5，即压栈；再进行删除元素，即出栈。
1.2C语言实现栈
在这里就面临一个选择，由于栈是一个受限制的线性表，而在学栈之前，已经学过了顺序表和链表，那么究竟是选择用顺序表实现栈还是用链表实现栈呢？
在这里不妨设想一下，如果用链表实现栈，假设链表的表头是栈底，那么链表尾部就是栈顶，一方面，每次压栈就是尾插操作，要遍历链表；另一方面，每次出栈的时候，都要找到链表倒数第2个，将其数据与置为空，也要遍历链表，还要找倒数第2个，很麻烦。
而如果用顺序表实现栈，顺序表头作为栈底，表尾作为栈顶，那么每次压栈，只需要尾元素的后面再加一个元素就行，然后top++。用顺序表无疑更加方便。如下的压栈和出栈操作，data指向栈的空间、top代表栈里面已经存放的元素个数、capacity代表栈的容量。
1.2.1接口函数
由于并不是无哨兵位的链表，所以并不需要传二级指针，只需要传一级指针即可。
而对栈进行插入元素只有一个接口，所以顺序表里面检查容量的接口，在这里就不特意写成一个函数了，直接在压栈接口里面写即可。
1.2.2栈的创建
如下，和顺序表的创建大同小异，也是STDataType类型的指针、已有数据个数、容量。
typedef int STDataType;
typedef struct Stack
{
STDataType* data;
int top; //已有的数据个数
int capacity; //容量
}ST;
1.2.3栈的初始化
这里没啥问题。
void StackInit(ST* ps)
{
assert(ps);
ps->data = NULL;
ps->capacity = ps->top = 0;
}1.2.4栈的销毁
和初始化配套，也没啥大问题。
void StackDestory(ST* ps)
{
assert(ps);
free(ps->data);
ps->data = NULL;
ps->capacity = ps->top = 0;
}1.2.5压栈
压栈前要进行检查容量的操作，如果栈里面，实际存储元素个数和容量相等，意味着要扩容。扩容扩的是ps->data，因为data是指向存储空间的指针。扩容分为两种情况，首先是该栈为空，那么分配可以存储4个STDataType类型数据的空间；如果不为空，那么容量增加一倍。在这里定义newcapacity，即新的容量，用到了三目运算符。
至于在这里为什么要用一个新指针tmp来接收realloc的内存，然后再把ps->a指向这块空间，在(102条消息) 【动态内存管理】malloc，calloc，realloc的使用方法以及常见错误_中的realloc部分也有详细解释。
然后栈内下标为ps->top（即最后一个元素的后一个空间）的空间插入新元素，ps->top++。在这里，假设有ps->top为n，那么栈内有n个元素，但是它们的下标是0到n-1，所以进行压栈操作的时候，数据应该放在下标为n的位置，正好是下标为ps->top处的空间。
void StackPush(ST* ps, STDataType x)
{
assert(ps);
if (ps->capacity == ps->top)
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
STDataType* temp = (STDataType*)realloc(ps->data,newcapacity*sizeof(STDataType));
if (temp == NULL)
{
printf("realloc fail!\n");
exit(-1);
}
ps->data = temp;
ps->capacity = newcapacity;
}
ps->data[ps->top] = x;
ps->top++;
}1.2.6出栈
相较压栈，出栈就很容易，只要排除不是空栈的情况（用assert），然后已经存放的个数减一即可。至于在这里为什么不把最后一个元素置为0，因为realloc开辟了空间，会把开辟的空间里的数据置为随机值，所以这里是否置为0没有什么太大意义。
void StackPop(ST* ps)
{
assert(ps);
assert(ps->top > 0);// ps->top <= 0 就报错
ps->top--;
}1.2.7判断栈是否为空
ps->top为0，则存放数据个数为0，为空，返回1。这里栈为空，为什么不返回“0“是因为，想象一下平常说话，“栈为空吗？” “为空！” 这里为空则是肯定的意思，这样子理解。
bool StackEmpty(ST* ps)
{
assert(ps);
if (ps->top == 0)
{
return 1;
}
else
return 0;
}1.2.8取栈顶元素
返回第ps->top-1下标的位置即可。当然也要排除栈为空的情况。文章来源：https://www.toymoban.com/news/detail-742630.html
STDataType StackTop(ST* ps)
{
assert(ps);
assert(!StackEmpty(ps));
return ps->data[ps->top-1];
}1.2.9 栈有多少个数据
这个也比较容易，ps->top就代表的有多少个数据，直接返回它就行。文章来源地址https://www.toymoban.com/news/detail-742630.html
int StackSize(ST* ps)
{
assert(ps);
return ps->top;
}1.3C语言实现栈的具体代码
头文件stack.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
#define N 10
typedef int STDataType;
typedef struct Stack
{
STDataType* data;
int top; //已有的数据个数
int capacity; //容量
}ST;
//初始化
void StackInit(ST* ps);
//销毁栈
void StackDestory(ST* ps);
//压栈
void StackPush(ST* ps, STDataType x);
//出栈
void StackPop(ST* ps);
//找到栈顶数据
STDataType StackTop(ST* ps);
//栈的里数据的多少
int StackSize(ST* ps);
//栈是否为空，1位空，0为非空
bool StackEmpty(ST* ps);
接口函数stack.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"stack.h"
void StackInit(ST* ps)
{
assert(ps);
ps->data = NULL;
ps->capacity = ps->top = 0;
}
void StackDestory(ST* ps)
{
assert(ps);
free(ps->data);
ps->data = NULL;
ps->capacity = ps->top = 0;
}
void StackPush(ST* ps, STDataType x)
{
assert(ps);
if (ps->capacity == ps->top)
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
STDataType* temp = (STDataType*)realloc(ps->data,newcapacity*sizeof(STDataType));
if (temp == NULL)
{
printf("realloc fail!\n");
exit(-1);
}
ps->data = temp;
ps->capacity = newcapacity;
}
ps->data[ps->top] = x;
ps->top++;
}
void StackPop(ST* ps)
{
assert(ps);
assert(ps->top > 0);
ps->top--;
}
STDataType StackTop(ST* ps)
{
assert(ps);
assert(!StackEmpty(ps));
return ps->data[ps->top-1];
}
int StackSize(ST* ps)
{
assert(ps);
return ps->top;
}
bool StackEmpty(ST* ps)
{
assert(ps);
if (ps->top == 0)
{
return 1;
}
else
return 0;
}
测试函数test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"stack.h"
void Test1()
{
ST a;
StackInit(&a);
StackPush(&a, 1);
StackPush(&a, 2);
StackPush(&a, 3);
StackPush(&a, 4);
printf("%d ", StackTop(&a));
StackPop(&a);
printf("%d ", StackTop(&a));
StackPop(&a);
StackPush(&a, 5);
StackPush(&a, 6);
while (!StackEmpty(&a))
{
printf("%d ", StackTop(&a));
StackPop(&a);
}
}
int main()
{
Test1();
return 0;
}到了这里，关于【数据结构】栈的实现（C语言）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
