视频讲解
录视频完了后才发现话筒坏了，已经使用PR处理过尽量让音频变得可识别，如果公放听不清建议戴上耳机。给大家的不便还请谅解。——下次录视频前一定先试录一次(ಥ_ಥ)
因为栈只在栈顶有插入和删除操作，所以没必要使用链式栈，使用顺序栈更合适。
其实c语言中的数组，经过限制后（先进后出，中间结点不允许操作）就可以成为栈。
栈只是一种思想。
-
-
bo3-1.cpp：顺序栈的基本操作（9个）
已经实现的功能：
-
初始化栈
-
压一个元素入栈
-
栈内元素遍历
-
弹出栈顶元素
-
判断栈是否空
- 获取栈顶元素
-
栈长度
-
清空栈
-
销毁栈
-
-
c1.h代码
#include <stdio.h> #include <malloc.h> #include <process.h>
c3-1.h代码
//栈的顺序表示及实现
struct SqStack
{
SElemType* base; //栈底指针
SElemType* top; //栈顶指针
int stacksize; //栈容量大小
};
bo3-1.cpp代码
//栈的顺序表示及实现
void InitStack(struct SqStack &S)
{
S.base = (SElemType *)malloc(2*sizeof(SElemType));
if (S.base == NULL)
{
printf("动态内存分配失败！\n");
exit(-1);
}
S.top = S.base;
S.stacksize = 2; // 初始分配的存储空间量，表示可以存储多少个元素。
}
void Push(struct SqStack &S, SElemType e)
{
// e代表被插入的值
// 先判断栈是否还能存放下，如果满了就追加空间
if (S.top - S.base >= S.stacksize)
{
/*
void *realloc(void *ptr, size_t size)
ptr -- 指针指向一个要重新分配内存的内存块，该内存块之前是通过调用 malloc、calloc 或 realloc 进行分配内存的。如果为空指针，则会分配一个新的内存块，且函数返回一个指向它的指针。
size -- 内存块的新的大小，以字节为单位。如果大小为 0，且 ptr 指向一个已存在的内存块，则 ptr 所指向的内存块会被释放，并返回一个空指针。
*/
// 10 是增量
S.base = (SElemType *)realloc(S.base, (S.stacksize + 10)*sizeof(SElemType));
if (S.base == NULL)
{
printf("Push函数中的动态内存分配失败！\n");
exit(-1);
}
// 将原来老的栈顶指针移至新的栈顶
S.top = S.base + S.stacksize;
// 更改S.stacksize的计数
S.stacksize = S.stacksize + 10;
// e存进栈顶指针指向的结点
//*(S.top) = e;
// 栈顶往上移动一个结点
//S.top++;
}
//先将top指针+1，再赋值给top原来指向的位置空间
//*(S.top)++=e;
*S.top = e;
S.top = S.top + 1;
}
void StackTraverse(struct SqStack &S)
{
SElemType* p = S.base;
while (p != S.top)
{
printf("%5d", *p);
p = p + 1;
}
printf("\n");
}
void Pop(struct SqStack &S, SElemType &e)
{
//先判断栈空，如果栈为空则返回错误
if (S.top == S.base)
{
printf("栈为空，不能删除元素\n");
exit(-1);
}
// 栈顶指针往下移动一个结点即可
S.top = S.top - 1;
e = *S.top;
}
bool StackEmpty(struct SqStack &S)
{
if (S.top == S.base)
{
return 1; //栈为空
}
else
{
return 0; //不空
}
}
void GetTop(struct SqStack &S, SElemType &e)
{
if (S.top == S.base)
{
printf("栈是空的\n");
exit(-1);
}
//S.top = S.top - 1;
e = *(S.top-1);
}
int StackLength(struct SqStack &S)
{
return S.top - S.base;
}
void ClearStack(struct SqStack &S)
{
S.top = S.base;
}
void DestroyStack(struct SqStack &S)
{
free(S.base);
S.base = NULL;
S.top = NULL;
S.stacksize=0;
}
main3-1.cpp代码
//栈的顺序表示及实现
#include "c1.h"
typedef int SElemType; // 栈结点中存放的数据类型
#include "c3-1.h"
#include "bo3-1.cpp"
/*
已经实现的功能
1.初始化栈
2.压一个元素入栈
3.栈内元素遍历
4.弹出栈顶元素
5.判断栈是否空
6.获取栈顶元素
7.栈长度
8.清空栈
9.销毁栈
*/
void main()
{
struct SqStack S;
//Init
InitStack(S);
//Push
int j = 1;
Push(S, j); //对哪个栈操作,插入什么值
//批量Push
int k;
for (k = 2; k <= 12; k++)
{
Push(S, k);
}
//遍历
printf("栈内元素有：");
StackTraverse(S);
//Pop(删除，弹出)
int e; //弹出栈顶元素
Pop(S, e);
printf("被弹出的栈顶元素是：%d\n", e);
printf("弹出栈顶元素后，栈内元素有：");
StackTraverse(S);
//判空
printf("栈为空吗：");
if (StackEmpty(S))
{
printf("栈空\n");
}
else
{
printf("栈不为空\n");
}
//获取栈顶元素
GetTop(S, e);
printf("栈顶元素是：%d\n", e);
//栈长度
printf("栈长度为：%d\n", StackLength(S)); //通过返回值取得长度
// 清空栈
ClearStack(S);
// 销毁栈
DestroyStack(S);
}
代码包
参考文献：
《数据结构算法实现及解析》 高一凡
