C语言超详细讲解栈的实现及代码
前言
栈的概念
- 栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。有点类似于手枪弹夹，后压进去的子弹总是最先打出，除非枪坏了。
- 压栈：栈的插入操作叫做进栈/压栈/入栈。（入数据在栈顶）
- 出栈：栈的删除操作叫做出栈。（出数据也在栈顶）
注意：
1、函数调用也有栈，这两个栈有区别吗？
当然有区别。函数调用会调用栈帧，内存里头也有一个栈，程序运行起来时要执行函数，函数里头的局部变量、参数、返回值等等都要存在函数栈帧里头。
这两个栈没有任何关联，一个是数据结构中的栈。另一个是操作系统中内存划分的一个区域，叫做栈，用来函数调用时，建立栈帧。虽然本质上没有任何关联，但都符合后进先出的规则。
2、假设入栈顺序为：1 2 3 4，那么出栈顺序一定为：4 3 2 1 吗？
当然不是。虽说规则上明确后进先出，可这是相对而言的，如果说它每进一个再出一个，然后再继续压栈，那不同样符合后进先出的规则吗。就如同上例，你说它出栈顺序为1 2 3 4 都不足为奇，每进一个出一个再进，同样符合规则。类似的入栈两个再出再进再出也是可以的，好比如2 1 4 3。
栈的结构
栈的实现
创建栈结构
Stack.h 文件：
//创建栈结构
typedef int STDataType;
typedef struct Stack
{
STDataType* a; //存储数据
int top; //栈顶的位置
int capacity; //容量
}ST;
初始化栈
思想：
初始化还是相对比较简单的，学了之前的顺序表，初始化栈就很轻松了
Stack.h 文件：
//初始化栈 void StackInit(ST* ps);
Stack.c 文件：
//初始化栈
void StackInit(ST* ps)
{
assert(ps);
ps->a = NULL;
ps->top = 0;
ps->capacity = 0;
}
注意：
???这里初始化的时候将top置为0是有意图的。首先，由上文创建栈结构时已经标注了，top是用来记录栈顶的位置，既然是栈顶的位置，那当top初始化为0时，我们可以直接将数据放入栈中，随后top++，但是当top初始化为-1时，top首先要++才能放入数据，因为数据不可能在负数不属于栈的位置上放入。下图演示过程：
本文以 top = 0 示例
销毁栈
思想：
动态开辟的内存空间一定要释放，free置空即可，并把其余数据置0。
Stack.h 文件：
//销毁栈 void StackDestory(ST* ps);
Stack.c 文件：
//销毁栈
void StackDestory(ST* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->capacity = ps->top = 0;
}
入栈
思路：
前文已经强调了top初始化为0，那么理应直接压入数据，并把top++，不过在这之前，得判断空间是否够，当top=capacity的时候，栈就满了，那么就需要realloc扩容。
Stack.h 文件：
//压栈 void StackPush(ST* ps, STDataType x);
Stack.c 文件：
//压栈
void StackPush(ST* ps, STDataType x)
{
assert(ps);
//如果栈满了，考虑扩容
if (ps->top == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; //检测容量
ps->a = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));
if (ps->a == NULL)
{
printf("realloc fail\n");
exit(-1);
}
ps->capacity = newcapacity; //更新容量
}
ps->a[ps->top] = x;//将数据压进去
ps->top++;//栈顶上移
}
出栈
思路：
在你出栈之前，要确保top不为空，而top不为空的条件就是top>0，所以还要断言top>0，随后，直接将栈顶位置下移--即可。跟顺序表的思想大同小异。
Stack.h 文件：
//出栈 void StackPop(ST* ps);
Stack.c 文件：
//出栈
void StackPop(ST* ps)
{
assert(ps);
assert(ps->top > 0);
ps->top--;
}
获取栈顶元素
思路：
首先要搞清楚谁才是栈顶元素，是top位置还是top-1位置？很显然是top-1的位置才是栈顶元素，因为在前文初始化的时候已经明确指出top为0，当时压栈时直接放入数据的，此时第一个数据下标为0，随后++top再压入其它数据，由此可见，栈顶元素即下标top-1的位置。
Stack.h 文件：
//访问栈顶数据 STDataType StackTop(ST* ps);
Stack.c 文件：
//访问栈顶数据
STDataType StackTop(ST* ps)
{
assert(ps);
assert(ps->top > 0);
return ps->a[ps->top - 1]; //top-1的位置才为栈顶的元素
}
获取栈中有效元素个数
思想：
上文讲到下标top-1才是栈顶元素，那么是不是说总共就是top-1个元素呢？当然不是，这里跟数组下标一样的思想，元素个数应该就是top个，直接返回即可。
Stack.h 文件：
//有效元素个数 int StackSize(ST* ps);
Stack.c 文件：
//有效元素个数
int StackSize(ST* ps)
{
assert(ps);
return ps->top;
}
检测栈是否为空
思路：
当top的值为0时即为空，return直接返回即可
Stack.h 文件：
//判空 bool StackEmpty(ST* ps);
Stack.c 文件：
//判空
bool StackEmpty(ST* ps)
{
assert(ps);
return ps->top == 0; //如果top为0，那么就为真，即返回
}
Test.c 文件：
void TestStack()
{
ST st;
StackInit(&st);
StackPush(&st, 1);
StackPush(&st, 2);
StackPush(&st, 3);
StackPush(&st, 4);
while (!StackEmpty(&st))
{
printf("%d ", StackTop(&st));
StackPop(&st);
}
printf("\n");
StackDestory(&st);
}
效果如下：
总代码
Stack.h 文件
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
//创建栈结构
typedef int STDataType;
typedef struct Stack
{
STDataType* a; //存储数据
int top; //栈顶的位置
int capacity; //容量
}ST;
//初始化栈
void StackInit(ST* ps);
//销毁栈
void StackDestory(ST* ps);
//压栈
void StackPush(ST* ps, STDataType x);
//出栈
void StackPop(ST* ps);
//判空
bool StackEmpty(ST* ps);
//访问栈顶数据
STDataType StackTop(ST* ps);
//有效元素个数
int StackSize(ST* ps);
Stack.c 文件
#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
//初始化栈
void StackInit(ST* ps)
{
assert(ps);
ps->a = NULL;
ps->top = 0;
ps->capacity = 0;
}
//销毁栈
void StackDestory(ST* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->capacity = ps->top = 0;
}
//压栈
void StackPush(ST* ps, STDataType x)
{
assert(ps);
//如果栈满了，考虑扩容
if (ps->top == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; //检测容量
ps->a = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));
if (ps->a == NULL)
{
printf("realloc fail\n");
exit(-1);
}
ps->capacity = newcapacity; //更新容量
}
ps->a[ps->top] = x;//将数据压进去
ps->top++;//栈顶上移
}
//出栈
void StackPop(ST* ps)
{
assert(ps);
assert(ps->top > 0);
ps->top--;
}
//判空
bool StackEmpty(ST* ps)
{
assert(ps);
return ps->top == 0; //如果top为0，那么就为真，即返回
}
//访问栈顶数据
STDataType StackTop(ST* ps)
{
assert(ps);
return ps->a[ps->top - 1]; //top-1的位置才为栈顶的元素
}
//有效元素个数
int StackSize(ST* ps)
{
assert(ps);
return ps->top;
}
Test.c 文件
#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
void TestStack()
{
ST st;
StackInit(&st);
StackPush(&st, 1);
StackPush(&st, 2);
StackPush(&st, 3);
StackPush(&st, 4);
while (!StackEmpty(&st))
{
printf("%d ", StackTop(&st));
StackPop(&st);
}
printf("\n");
StackDestory(&st);
}
int main()
{
TestStack();
return 0;
}
上一篇：C++数字三角形问题与dp算法
栏 目：C代码
下一篇：C++强制类型转换(static_cast、dynamic_cast、const_cast、reinterpret_cast)
本文标题：C语言超详细讲解栈的实现及代码
本文地址：http://www.codeinn.net/misctech/222411.html
