汉扬编程 C语言入门 嵌入式C语言中栈的应用实现

嵌入式C语言中栈的应用实现

我们在C语言的实际编程开发中,设计的重点一般就是两个方面:算法设计和数据结构设计。关于这两个方面,实际上都有专门的理论课题研究。我们这里主要还是侧重于具体的实现和应用,关于算法设计我前面有专题涉及到过,当然没有讲全,后面有机会我还会再开专题来讲讲。至于数据结构设计,还没有专门探讨过,我们这里就算开个头,先来看看数据结构中的“栈”的具体实现和应用。

嵌入式C语言中栈的应用实现

什么是栈?

嵌入式C语言中栈的应用实现

栈(Stack)是限定仅在表尾进行插入或删除操作的线性表。

因此,对栈来说,表尾端有其特殊含义,称为栈顶( top) ,相应地,表头端称为栈底(bottom)。栈的修改是按后进先出的原则进行的。因此,栈又称为后进先出的线性表。

其中,a1为栈底元素,an为栈顶元素。

栈的设计实现

栈,可以利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素,同时增加一个指示top,用来指示栈顶元素在栈中的位置。可以让top=0表示空栈,当发生进栈时,将进栈元素存放入top指示的存储单元中,然后使top=top+1,因此使用这种表达方式时,top指示的存储单元总是将存放下一个进栈元素,而当栈不为空时,当前栈顶元素的位置为top-1,栈中存储的元素总个数为top。

当发生出栈时,需要使top=top-1,同时取出当前top所指向的元素。而取栈顶元素时只需要返回top-1处的元素即可。

栈的具体代码实现

根据上面描述的栈的表示和实现方法,下面列出栈结构的具体实现代码

typedef struct stack{ ITEMDATA ItemBuffer[MAXSTACKLEN]; unsigned int top;}STACK;该结构体描述了一个简易的栈的主要结构, ITEMDATA为抽象数据类型,具体实现时可将ITEMDATA替换为程序中需要的数据类型;MAXSTACKLEN宏表示栈的缓冲区的大小,该宏的具体数值可根据具体程序实例的情况来确定;ItemBuffer表示栈的缓冲区的数组名;top表示该栈的栈顶指针,实际上是一个表示栈顶所在数组的下标序号。

栈的常用的操作函数有:栈的初始化、进栈、出栈、取栈顶、判断栈是否为空栈,销毁栈等,下面分别列举这些函数的实现方法。

栈的初始化,pstack为指向栈的指针

void init_stack( STACK* pstack){ pstack->top = 0;}进栈,函数返回1表示栈溢出,返回0表示进栈成功

int push_stack(STACK* pstack , ITEMDATA item){ if(pstack->top >= MAXSTACKLEN) { return 1; } pstack->ItemBuffer[pstack->top++] = item; return 0;}出栈,函数返回1表示栈已为空,无法出栈,返回0表示出栈成功

int pop_stack(STACK* pstack , ITEMDATA* pitem){ if(pstack->top <= 0) { return 1; } *pitem = pstack->ItemBuffer[- – (pstack->top)]; return 0;}取栈顶,函数返回1表示栈已为空,返回0表示取栈顶成功

int get_stack_top(STACK* pstack , ITEMDATA* pitem){ if(pstack->top <= 0) { return 1; } *pitem = pstack->ItemBuffer[pstack->top – 1]; return 0;}判断栈是否为空,函数返回1表示栈为空,返回0表示栈不为空

int isempty_stack(STACK* pstack){ if(pstack->top <= 0) { return 1; } else { return 0; }}根据栈应用的具体程序不同,应该对上述代码进行适当的修改,以适应于具体的应用。

栈的实际应用场景

说了这么多,我们会在什么地方真正用到这种栈的数据结构呢?还是举个实际的例子,我在之前的文章《嵌入式C语言中基于状态机的代码实现》中有提到过,关于车灯的控制。对某个车灯来说,能够驱动它的驱动者肯定不止一个,简单假象一下,当前如果有两个驱动者,并且一个优先级低,另一个优先级高。如果有这样一种场景,就是车灯先被低优先级的驱动者控制按某个规则正在闪烁,这时优先级高的那个驱动者也产生了车灯控制请求,那么优先级高的肯定要打断优先级低的控制,这时车灯就会去响应优先级高的驱动者。但是当优先级高的驱动者释放车灯控制权之后,原形低优先级的驱动者如果还在,那么就需要回到打断之前的状态中去,车灯需要维持原来的闪烁状态。

像类似这种功能需求,和栈的后进先出的原则是完全吻合的。这时候你不用栈这种数据结构,你还犹豫什么。其实,类似的场景还有很多,大家可以自己总结。

本文来自网络,不代表汉扬编程立场,转载请注明出处:http://www.hyzlch.com/cjia/7081.html

玛雅人的数字进位为什么要采用20进位和18进位?

关于入栈,出栈指针和数据操作顺序的疑问

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

返回顶部