建管家企业网站,天元建设集团有限公司青岛分公司张德平不干了,亚马逊网站网址,湘潭简单的网站建设公司栈与队列是数据结构中重要的结构#xff0c; 可以用于解决一些题目 模拟实现时可以增加对于这些结构的理解#xff0c;也可以巩固我们的语言水平#xff0c;解决某些题目也会有很好的效果
话不多说 目录 栈的实现结构体的定义#xff1a;初始化栈:压栈#xff1a;出栈 可以用于解决一些题目 模拟实现时可以增加对于这些结构的理解也可以巩固我们的语言水平解决某些题目也会有很好的效果
话不多说 目录 栈的实现结构体的定义初始化栈:压栈出栈获取栈顶元素获取栈中有效元素个数 :检测栈是否为空:销毁栈 : 栈模拟源代码队列的实现 栈的实现
先来看一下栈的定义: 栈一种特殊的线性表其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端 称为栈顶另一端称为栈底。栈中的数据元素遵守后进先出LIFOLast In First Out的原则。 压栈栈的插入操作叫做进栈/压栈/入栈入数据在栈顶。 出栈栈的删除操作叫做出栈。出数据也在栈顶。 栈的实现一般可以使用数组或者链表实现 相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。 结构体的定义
// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{STDataType* a;int top; // 栈顶int capacity; // 容量
}Stack;初始化栈:
栈在初始化时 我们可以定义top为栈顶元素的下一个故这样我们就可以将top定义为0若将top定义为栈顶元素则需要将top定义为-1
这里我在仔细的讲解一下 当top为0时我们不能将top视作栈顶元素因为如果压栈压入的元素就会在top 0的位置压入压入的top仍为0我们将判断不了top 0时是否有元素 则若top 0我们应当定义栈顶元素的下一个这样我们赋值时ps-a[top] data;top;
同理若是初始化top -1则赋值:top;ps-a[top] data;
// 初始化栈
void StackInit(Stack* ps)
{ps-a NULL;ps-capacity 0;ps-top 0;
}压栈
因为只有压栈时会增加元素个数故我们不需要封装一个函数用来创造新节点
void StackPush(Stack* ps, STDataType data)
{assert(ps);//检查容量if (ps-capacity ps-top){int newcapacity (ps-capacity 0 ? 4 : 2 * ps-capacity);STDataType* tmp (STDataType*)realloc(ps-a, sizeof(STDataType) * newcapacity);if (tmp NULL){perror(realloc fail);return;}ps-a tmp;ps-capacity newcapacity;}ps-a[ps-top] data;ps-top;
}
出栈
void StackPop(Stack* ps)
{assert(ps);assert(ps-top);ps-top--;
}获取栈顶元素
STDataType StackTop(Stack* ps)
{assert(ps);return ps-a[ps-top - 1];
}获取栈中有效元素个数 :
int StackSize(Stack* ps)
{assert(ps);return ps-top;
}检测栈是否为空:
检测栈是否为空如果为空返回非零结果如果不为空返回0
bool StackEmpty(Stack* ps)
{assert(ps);return ps-top 0;
}销毁栈 :
void StackDestroy(Stack* ps)
{free(ps-a);ps-a NULL;ps-capacity 0;ps-top 0;
}栈模拟源代码
stack.c
#define _CRT_SECURE_NO_WARNINGS 1#include stack.h// 初始化栈
void StackInit(Stack* ps)
{ps-a NULL;ps-capacity 0;ps-top 0;
}void StackPush(Stack* ps, STDataType data)
{assert(ps);//检查容量if (ps-capacity ps-top){int newcapacity (ps-capacity 0 ? 4 : 2 * ps-capacity);STDataType* tmp (STDataType*)realloc(ps-a, sizeof(STDataType) * newcapacity);if (tmp NULL){perror(realloc fail);return;}ps-a tmp;ps-capacity newcapacity;}ps-a[ps-top] data;ps-top;
}void StackPop(Stack* ps)
{assert(ps);assert(ps-top);ps-top--;
}STDataType StackTop(Stack* ps)
{assert(ps);return ps-a[ps-top - 1];
}int StackSize(Stack* ps)
{assert(ps);return ps-top;
}bool StackEmpty(Stack* ps)
{assert(ps);return ps-top 0;
}void StackDestroy(Stack* ps)
{free(ps-a);ps-a NULL;ps-capacity 0;ps-top 0;
}stack.h
#define _CRT_SECURE_NO_WARNINGS 1
#includestdio.h
#includestdlib.h
#includeassert.h
#includestdbool.h
// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{STDataType* a;int top; // 栈顶int capacity; // 容量
}Stack;// 初始化栈
void StackInit(Stack* ps);
// 入栈
void StackPush(Stack* ps, STDataType data);
// 出栈
void StackPop(Stack* ps);
// 获取栈顶元素
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数
int StackSize(Stack* ps);
// 检测栈是否为空如果为空返回非零结果如果不为空返回0
bool StackEmpty(Stack* ps);
// 销毁栈
void StackDestroy(Stack* ps);队列的实现 队列的定义 队列只允许在一端进行插入数据操作在另一端进行删除数据操作的特殊线性表队列具有先进先出 FIFO(First In First Out) 入队列进行插入操作的一端称为队尾 出队列进行删除操作的一端称为队头 持续更新中… 敬请期待
