现在网站建设 如何保证安全,微信开放平台是公众号吗,网站建设与网页设计的论文,山东省建设项目备案证明网站前言#xff1a;各位小伙伴们我们前面已经学习了带头双向循环链表#xff0c;数据结构中还有一些特殊的线性表#xff0c;如栈和队列#xff0c;那么我们今天就来实现数组栈。 目录#xff1a;
一、 栈的概念 二、 栈的实现 三、 代码测试
栈的概念#xff1a; 栈的概念… 前言各位小伙伴们我们前面已经学习了带头双向循环链表数据结构中还有一些特殊的线性表如栈和队列那么我们今天就来实现数组栈。 目录
一、 栈的概念 二、 栈的实现 三、 代码测试
栈的概念 栈的概念及结构 栈一种特殊的线性表其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端 称为栈顶另一端称为栈底。栈中的数据元素遵守后进先出LIFOLast In First Out的原则压栈栈的插入操作叫做进栈/压栈/入栈入数据在栈顶出栈栈的删除操作叫做出栈。出数据也在栈顶。 栈顶Top线性表允许进行插入删除的那一端。 栈底Bottom固定的不允许进行插入和删除的另一端。 空栈不含任何元素的空表。 栈的实现 栈的实现一般可以使用数组或者链表实现相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。 接口
// 初始化栈
void STInit(ST* pst);
// 销毁栈
void STDestroy(ST* pst);// 入栈
void STPush(ST* pst, STDataType x);
// 出栈
void STPop(ST* pst);
// 获取栈顶元素
STDataType STTop(ST* pst);// 检测栈是否为空如果为空返回非零结果如果不为空返回0
bool STEmpty(ST* pst);
// 获取栈中有效元素个数
int STSize(ST* pst);这里我们需要三个文件一个头文件一个文件用来实现我们的各种接口一个文件用来测试我们的代码。 头文件Stack.h
#pragma once
#includestdio.h
#includeassert.h
#includestdlib.h
#includestdbool.htypedef int STDataType;typedef struct Stack
{int* a;int top; // 标识栈顶位置的int capacity;
}ST;void STInit(ST* pst);
void STDestroy(ST* pst);// 栈顶插入删除
void STPush(ST* pst, STDataType x);
void STPop(ST* pst);
STDataType STTop(ST* pst);bool STEmpty(ST* pst);
int STSize(ST* pst);我们的top是栈顶如果我们的top0时我们指向的就是栈顶元素如果我们的top1那么我们的top指向的就是栈顶元素的下一个位置。
函数实现Stack.c
#includeStack.hvoid STInit(ST* pst)
{assert(pst);pst-a NULL;pst-capacity 0;pst-top 0;
}void STDestroy(ST* pst)
{}// 栈顶插入删除
void STPush(ST* pst, STDataType x)
{assert(pst);if (pst-top pst-capacity){int newcapacity pst-capacity 0 ? 4 : pst-capacity * 2;STDataType* tmp (STDataType*)realloc(pst-a, sizeof(STDataType) * newcapacity);if (tmp NULL){perror(realloc fail);return;}pst-a tmp;pst-capacity newcapacity;}pst-a[pst-top] x;pst-top;
}void STPop(ST* pst)
{assert(pst);// 不为空assert(pst-top 0);pst-top--;
}STDataType STTop(ST* pst)
{assert(pst);// 不为空assert(pst-top 0);return pst-a[pst-top - 1];
}bool STEmpty(ST* pst);
int STSize(ST* pst);测试代码test.c
int main()
{ST s;STInit(s);STPush(s, 1);STPush(s, 2);STPush(s, 3);STPush(s, 4);STPush(s, 5);while (!STEmpty(s)){printf(%d , STTop(s));STPop(s);}printf(\n);return 0;
}我们这里入栈五个数据当我们的栈里面不为空时我们就访问栈顶元素在让栈顶元素出栈。直到我们的栈为空时就退出循环。 int main()
{ST s;STInit(s);STPush(s, 1);STPush(s, 2);STPush(s, 3);printf(%d , STTop(s));STPop(s);printf(%d , STTop(s));STPop(s);STPush(s, 4);STPush(s, 5);while (!STEmpty(s)){printf(%d , STTop(s));STPop(s);}printf(\n);return 0;
}这里我们可以同时入栈和出栈我们先入栈1,23在出栈我们的栈是后入先出也就是说我们后面入栈的元素在出栈的时候先出栈我们出栈一个也就是3再出栈就是2最后入栈就是4,5。
