湘潭企业网站建设 磐石网络,上海门户网站一网通办,地方网站盈利,化工集团网站建设 中企动力1.栈的概念及结构
栈#xff1a;一种特殊的线性表#xff0c;其只允许在固定的一端进行插入和删除元素操作
进行数据插入和删除操作的一端称为栈顶#xff0c;另一端称为栈底
栈中的数据元素遵守后进先出LIFO,#xff08;Last In First Out#xff09;的原则 压栈…1.栈的概念及结构
栈一种特殊的线性表其只允许在固定的一端进行插入和删除元素操作
进行数据插入和删除操作的一端称为栈顶另一端称为栈底
栈中的数据元素遵守后进先出LIFO,Last In First Out的原则 压栈栈的插入操作叫做进栈/压栈/入栈入数据在栈顶出栈栈的删除操作叫做出栈出数据也在栈顶 Stack的Push和Pop遵循后进显先出原则
2.栈的实现
栈的实现一般可以使用数组或者链表实现相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小 2.1创建栈
我们还是用结构体来作为栈的每一个单独的数据块 2.2初始化
这里我们给top赋什么值得认真考虑需要给0吗?
如果top初始化为0,那么就会出现歧义:top0是有一个元素还是空 所以,如果top指向栈顶元素,需要给top-1才能区分 如果top指向栈顶元素的下一个位置,那么给top初始化为0就可以了 两种方式在初始化的时候会有区别: 如果top指向栈顶元素,top-1:push:top;a[top]x;如果top指向栈顶元素的下一个,top0:push:a[top]x;top; 我们这里初始化的时候就初始化为0,top就是元素个数: 2.3销毁 2.4入栈
由于top我们初始化为0,这里我们入栈的时候就需要先给值,再: 2.5出栈
出栈就很简单了: 入栈顺序和出栈顺序是一对多的关系
一种入栈顺序可能会有多种出栈顺序,而一种出栈顺序只对应一种入栈顺序: 2.6返回栈顶元素 2.7判空 或者更简单的写法: 2.8栈的元素个数 3.总代码
Stack.h
#pragma once
#include stdio.h
#include stdlib.h
#include assert.h
#include stdbool.h
typedef int STDataType;
typedef struct Stack
{STDataType* 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);Stack.c
#define _CRT_SECURE_NO_WARNINGS 1
#include Stack.h
//初始化
void STInit(ST* pst)
{assert(pst);pst-a NULL;pst-capacity 0;pst-top 0;
}
//销毁
void STDestroy(ST* pst)
{assert(pst);free(pst-a);pst-a NULL;pst-top pst-capacity 0;
}
//入栈
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)
{assert(pst);/*if (pst-top 0){return true;}else{return false;}*/return pst-top 0;
}
//栈的元素个数
int STSize(ST* pst)
{assert(pst);return pst-top;
}
test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include Stack.h
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;
}
