嵌入式 数据结构 栈和队列 学习笔记

栈栈的定义和应用栈Stack是限定仅在表尾进行插入或删除操作的线性表。因此对栈来说表尾端有其特殊含义称为栈顶top相应地表头端称为栈底bottom。不含元素的空表称为空栈。栈遵循后进先出last in first outLIFO的原则。1.函数调用管理栈用于管理函数调用包括存储局部变量和返回地址。当一个函数调用另一个函数时当前函数的状态被推入栈中待调用的函数完成后从栈中弹出状态恢复执行。2.撤销操作在文本编辑器或其他应用程序中栈用于实现撤销操作。每次用户进行操作时操作会被推入栈中用户可以通过弹出栈中的操作来撤销最近的操作。3.浏览器历史管理栈可以用于管理浏览器的历史记录。当用户访问新页面时当前页面的地址被推入栈中用户按“后退”按钮时最近访问的页面被弹出并加载。4.字符串反转使用栈可以轻松地实现字符串的反转将字符串中的字符逐个推入栈中然后再依次弹出。顺序栈和链栈typedef struct { SElemType *base; SElemType *top; int stacksize; }栈的基本操作•数据类型栈使用的数据类型为D{ai|ai∈ElemSet, i1,2,…,n,n ≥ 0}。•基本操作1.InitStack(*S)初始化一个空栈 S。2.DestroyStack(*S)销毁栈 S。3.ClearStack(*S)清空栈 S 中的所有元素。4.StackEmpty(S)检查栈 S 是否为空。如果为空返回 TRUE否则返回 FALSE。5.StackLength(S)返回栈 S 中元素的个数。6.GetTop(S, *e)返回栈 S 顶端的元素并将其赋值给 e。7.Push(*S, e)将元素 e 压入栈 S 的顶端。8.Pop(*S, *e)将栈 S 顶端的元素弹出并将其赋值给 e。9.StackTraverse(S, visit())从栈顶到底部遍历栈 S并对每个元素应用 visit() 函数。如果 visit() 函数失败则遍历停止。初始化栈Status InitStack(SqStack *S) { // 构造一个空栈 S-base (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType)); if (!S-base) exit(OVERFLOW); S-top S-base; S-stacksize STACK_INIT_SIZE; return OK; } Status GetToop(SqStack *S, SElemType *e) { // 若栈不空则用e返回S的栈顶元素并返回OK否则返回ERROR if (S-top S-base) return ERROR; *e *(S-top - 1); return OK; }入栈出栈Status Push(SqStack *S, SElemType e) { // 插入元素e为新的栈顶元素 if (S-top - S-base S-stacksize) { S-base (SElemType *)realloc(S-base, (S-stacksize STACKINCREMENT) * sizeof(SElemType)); if (!S-base) exit(OVERFLOW); S-top S-base S-stacksize; S-stacksize STACKINCREMENT; } *S-top e; return OK; } Status Pop(SqStack *S, SElemType *e) { // 若栈不空则删除S的栈顶元素用e返回其值并返回OK否则返回ERROR if (S-top S-base) return ERROR; *e *--S-top; return OK; }获得栈顶元素Status GetToop(SqStack *S, SElemType *e) { // 若栈不空则用e返回S的栈顶元素并返回OK否则返回ERROR if (S-top S-base) return ERROR; *e *(S-top - 1); return OK; }应用-数值转换十进制数N和其他d进制数的转换是计算机实现计算的基本问题其解决方法很多其中一个简单算法基于下列原理N (N div d) * d N mod d其中div为整除运算mod为求余运算。例如13481025048其运算过程如下编写一个满足下列要求的程序对于输入的任意一个非负十进制整数打印输出与其等值的八进制数。应用-行编辑程序接受用户从终端输入的程序或数据先存入缓存区当用户输入回车后将数据进行存放到数据区存储。在输入回车之前输入#代表清除上一个字符输入代表清除整行字符。如whli##ilr #e(s #*s) outcha putchar(*s #); 实际对应的数据是 while (*s) putchar(*s);队列队列的定义队列queue是一种先进先出first in first outFIFO的线性表它只允许在表的一端进行插入而在另一端删除元素。允许插入的一端叫做队尾rear允许删除的一端叫做队头front。InitQueue(*Q)初始化队列DestroyQueue(*Q)销毁队列ClearQueue(*Q)清空队列QueueEmpty(Q)判断队列是否为空QueueLength(Q)返回队列中的元素个数GetHead(Q,*e)返回队头元素EnQueue(*Q,e)入队元素DeQueue(*Q,*e)出队元素QueueTraverse(Q,visit())队列遍历双端队列队列的应用队列广泛应用于许多实际问题中尤其是在需要处理任务、事件或资源的场景中常见的应用包括•任务调度操作系统的进程调度常常使用队列处理先到先处理的任务。•打印任务管理多个打印任务可能进入队列按照顺序依次进行打印。•消息队列在分布式系统中消息队列用于异步通信和任务分发。•广度优先搜索BFS在图的广度优先搜索算法中队列用于存储待访问的节点。队列的实现方式链队列——队列的链式表示链队列链队列-初始化typedef struct QNode{ QElemType data; struct QNode *next; } QNode, *QueuePtr; typedef struct{ QueuePtr front; QueuePtr rear; } LinkQueue Status InitQueue(LinkQueue *Q){ // 构造一个空队列 Q Q-front Q-rear (QueuePtr)malloc(sizeof(QNode)); if (!Q-front) exit(OVERFLOW); Q-front-next NULL; return OK; }链队列-入队和出队Status EnQueue(LinkQueue *Q, QElemType e) { // 插入元素 e 为 Q 的新的队尾元素 p (QueuePtr)malloc(sizeof(QNode)); if (!p) exit(OVERFLOW); p-data e; p-next NULL; Q-rear-next p; Q-rear p; return OK; } Status DeQueue(LinkQueue *Q, QElemType *e) { // 若队列不空则删除 Q 的队头元素用 e 返回其值并返回 OK if (Q-front Q-rear) return ERROR; p Q-front-next; *e p-data; Q-front-next p-next; if (Q-rear p) Q-rear Q-front; free(p); return OK; }链队列-销毁队列Status DestroyQueue(LinkQueue *Q) { // 销毁队列 QQ不再存在 while (Q-front) { p Q-front-next; free(Q-front); Q-front p; } return OK; }循环队列——队列的顺序表示循环队列循环队列•如果你知道队列的最大长度并且不需要频繁变化循环队列是一个理想选择因为它的空间利用效率高、实现简单。•如果队列的大小不可预测且希望能根据需求动态扩展链队列是更好的选择虽然会有额外的内存开销和管理复杂度。循环队列——初始化#define MAXQSIZE 100 typedef struct { QElemType *base; int front; int rear; } SqQueue; Status InitQueue(SqQueue *Q) { Q-base (QElemType *)malloc(MAXQSIZE * sizeof(QElemType)); if (!Q-base) exit(OVERFLOW); Q-front Q-rear 0; return OK; }循环队列——入队和出队Status EnQueue(SqQueue *Q, QElemType e) { if (Q-front (Q-rear 1) % MAXSIZE) return ERROR; Q-base[Q-rear] e; Q-rear (Q-rear 1) % MAXSIZE; return OK; } Status DeQueue(SqQueue *Q, QElemType *e) { if (Q-front Q-rear) return ERROR; *e Q-base[Q-front]; Q-front (Q-front 1) % MAXSIZE; return OK; }循环队列——元素个数int QueueLength(SqQueue Q) { return (Q.rear - Q.front MAXSIZE) % MAXSIZE; }