当前位置：首页 > news >正文

Linux嵌入书学习—数据结构——栈（seqstak）

news 来源：原创 2024/9/20 12:04:21

一、栈；

定义：

是限定仅在表尾（栈顶）进行插入和删除操作的线性表
栈又称为后进先出（Last In First Out）的线性表，简称 LIFO 结构

栈顶（Top）

栈顶是栈中允许进行添加（入栈）或删除（出栈）元素的一端。在栈的所有操作中，无论是添加还是删除，都发生在栈顶。栈顶元素是最后被添加进去的元素，也是第一个被删除的元素（遵循后进先出LIFO原则）。

栈底（Bottom）

栈底是栈的另一端，与栈顶相对，通常不允许直接进行操作。栈底元素是第一个被添加进栈的元素，但在栈被完全清空之前，它将是最后一个被删除的元素（如果遵循正常的栈操作规则的话）。然而，在实际的栈实现中，栈底的存在主要是为了定义栈的边界，而不是为了直接操作。

入栈（Push）

入栈操作是将一个新元素添加到栈顶的过程。在顺序栈中，这通常意味着将新元素放到数组的末尾（如果栈未满的话）；在链式栈中，这通常意味着在链表的头部创建一个新节点，并将其链接到链表的头部（或称为栈顶）。

出栈（Pop）

出栈操作是从栈顶移除元素的过程，并通常返回被移除的元素的值。在顺序栈中，这通常意味着将数组的末尾元素删除（或更常见地，通过减少栈顶指针来实现），并返回该元素的值；在链式栈中，这通常意味着删除链表的头部节点，并返回其值。

顺序栈（基于数组）

顺序栈使用数组来存储栈中的元素。栈顶通常通过一个索引（或指针）来标识，该索引指向数组中的最后一个元素（栈顶元素）。顺序栈的优点是实现简单，空间利用率高（在栈大小固定的情况下）；缺点是栈的大小在创建时就已确定，不灵活，且在栈满时无法继续添加元素。

链式栈（基于链表）

链式栈使用链表来存储栈中的元素。栈顶元素是链表的第一个元素（头节点）。链式栈的优点是栈的大小可以动态调整，无需事先确定栈的最大容量；缺点是相对于顺序栈，链式栈的每个元素都需要额外的空间来存储指针（或链接），这可能会增加空间开销。

栈的内部实现原理

栈的内部实现原理其实就是数组或链表的操作
而之所以引入栈这个概念，是为了将程序设计问题模型化
用高层的模块指导特定行为（栈的先进后出特性），划分了不同关注层次，使得思考范围缩小
更加聚焦于我们致力解决的问题核心，简化了程序设计的问题

栈的使用场景：

函数调用：在大多数编程语言中，函数调用和返回都使用栈来管理。每当函数被调用时，其返回地址和局部变量等信息被压入栈中；当函数返回时，这些信息被从栈中弹出，恢复到函数调用前的状态。

表达式求值：在编译器和解释器中，栈被用来计算表达式的值。例如，在解析算术表达式时，可以使用两个栈，一个用于存储操作数，另一个用于存储操作符。

语法分析：在编译器设计中，栈用于实现语法分析器，特别是用于处理嵌套结构（如括号匹配、HTML标签等）。

回溯算法：在解决如八皇后问题、迷宫问题等需要尝试多种可能性的问题时，栈可以用来保存每个步骤的状态，以便在需要时回溯到之前的状态。

深度优先搜索（DFS）：在图的遍历中，深度优先搜索可以使用栈来实现。每当访问一个节点时，将其标记为已访问，并将其所有未访问的邻接节点压入栈中。

撤销操作：在文本编辑器、绘图程序等中，栈可以用来实现撤销操作。每当用户执行一个操作时，可以将该操作的信息压入栈中。当需要撤销时，可以从栈中弹出最近的操作信息，并执行相应的撤销操作。

二、顺序栈（seqstack）

1. `SeqStack*CreateSeqStack(int size);`

功能：创建一个顺序栈，并初始化其大小为size。

实现思路：

分配内存空间给SeqStack结构体，并检查内存分配是否成功。
初始化栈的属性，包括栈顶指针设置为栈底（通常是0或-1，取决于是否包含栈底元素），以及栈的大小等。
返回指向新创建的栈的指针。

2. `int DestroySeqStack(SeqStack*ss);`

功能：销毁顺序栈，释放其占用的内存空间。

实现思路：

释放栈所占用的内存空间。
可能需要将传入的指针置为NULL，以避免野指针问题（这取决于函数的设计）。
返回操作状态，成功时返回0或类似值。

3. `int PushSeqStack(SeqStackss, DATATYPEdata);`

功能：向顺序栈中压入一个元素。

实现思路：

检查栈是否已满。
如果栈未满，将*data（即指向的数据的值）复制到栈顶指针指向的位置，并将栈顶指针加1。
返回操作状态，成功时返回0或类似值。

4. `int PopSeqStack(SeqStack*ss);`

功能：从顺序栈中弹出栈顶元素，但不返回该元素的值。

实现思路：

检查栈是否为空。
如果栈不为空，将栈顶指针减1，从而弹出栈顶元素。
注意，这个函数通常不返回被弹出的元素的值，因此如果需要返回该值，可能需要一个额外的参数来接收。
返回操作状态，成功时返回0或类似值。

5. `int IsEmptySeqStack(SeqStack*ss);`

功能：检查顺序栈是否为空。

实现思路：

根据栈顶指针的位置判断栈是否为空（例如，如果栈顶指针等于栈底指针，则栈为空）。
返回判断结果，栈为空时返回非0值（通常是1），否则返回0。

6. `int IsFullSeqStack(SeqStack*ss);`

功能：检查顺序栈是否已满。

实现思路：

根据栈顶指针的位置和栈的容量判断栈是否已满（例如，如果栈顶指针加1等于栈的容量，则栈已满）。
返回判断结果，栈已满时返回非0值（通常是1），否则返回0。

7. `int GetSizeSeqStack(SeqStack*ss);`

功能：获取顺序栈的当前大小（即栈中元素的数量）。

实现思路：

根据栈顶指针的位置和栈底的位置（或栈的初始容量）计算栈中元素的数量。
返回计算结果。

8. `DATATYPEGetTopSeqStack(SeqStackss);`

功能：获取顺序栈的栈顶元素的值，但不从栈中移除它。

实现思路：

检查栈是否为空。
如果栈不为空，返回栈顶元素的地址（或栈顶元素的值，这取决于DATATYPE的类型和函数的设计）。注意，这里返回的是指针，可能是因为DATATYPE是一个结构体或类类型，直接返回其值可能不方便或不安全。
如果栈为空，可能需要设置一个错误码或返回NULL（这取决于函数的设计）。

三，链式栈

1. `LinkStackList* CreateLinkStackList();`

描述：创建一个空的链式栈并返回指向该栈的指针。

实现思路：

分配内存给LinkStackList类型的结构体。
初始化栈顶指针（通常指向NULL，表示空栈）。
返回指向新栈的指针。

`2.int PushLinkStack(LinkStackList* ls, DATATYPE* data);`

描述：将一个元素压入栈顶。

实现思路：

创建一个新的节点，并将传入的数据data（或其副本）存储在节点中。
将新节点的指针设置为当前栈顶指针的下一个节点（即插入到链表头部）。
更新栈顶指针为新节点的指针。
返回值可能用于指示操作是否成功。

需要判断一下原来栈内是否为空

3. `int PopLinkStack(LinkStackList* ls);`

描述：从栈顶弹出一个元素，但不返回该元素。

实现思路：

检查栈是否为空（如果为空，则进行错误处理或返回错误码）。
保存栈顶节点的指针，以便稍后释放其内存。
将栈顶指针更新为当前栈顶节点的下一个节点（即移除头部节点）。
释放保存的栈顶节点的内存。
返回值可能用于指示操作是否成功或栈是否为空。
（1）让tmp等于top，即指向出栈节点，保存出栈节点位置。
（2）将top指向出栈节点的下一个

4. `int DestroyLinkStack(LinkStackList* ls);`

描述：销毁链式栈，释放其占用的所有内存。

实现思路：

遍历链表，释放每个节点的内存。
最后释放栈本身（如果栈的指针是在堆上分配的）。
返回值可能用于指示操作是否成功（通常返回0表示成功，非0表示失败）。

5. `int GetSizeLinkStack(LinkStackList* ls);`

描述：返回链式栈的大小（即栈中元素的数量）。

实现思路：

遍历链表并计数节点数量。
返回计数结果。

6. `DATATYPE* GetTopLinkStack(LinkStackList* ls);`

描述：返回栈顶元素的指针（但不从栈中移除它）。

实现思路：

检查栈是否为空（如果为空，则进行错误处理或返回NULL）。
返回栈顶节点的数据指针。

7. `int IsEmptyLinkStack(LinkStackList* ls);`

描述：检查链式栈是否为空。

实现思路：

如果栈顶指针为NULL，则栈为空，返回1（或非0值，表示真）。
否则，栈不为空，返回0（表示假）。

四，顺序栈和链栈的关系区别

顺序栈与链栈的示意图

区别

存储结构：
顺序栈：采用顺序存储结构，通常使用数组来实现。数组中的元素在内存中的存储位置是连续的，且编译器要求我们在编译期就要确定数组的大小。顺序栈的栈底位置固定，栈顶位置随入栈和出栈操作而变化，因此需要一个整型变量（如top）来记录当前栈顶元素在数组中的位置。
链栈：采用链式存储结构，通常使用链表来实现。链表中的元素存储在不连续的地址上，每个节点除了存储数据元素外，还包含一个指向下一个节点的指针。链栈的栈顶通常指向链表的头节点，插入和删除操作都在链表的头部进行。
空间利用率：
顺序栈：由于采用数组存储，空间利用率较高，但大小固定，无法动态扩展。当栈满时，需要手动进行扩容操作。
链栈：空间利用率相对较低，因为需要为每个节点分配额外的指针空间。但链栈的大小可以动态变化，不需要预先分配固定大小的空间。
操作效率：
顺序栈：由于数据元素在内存中连续存储，因此可以通过下标直接访问栈中的元素，存取速度较快。但在栈满时，扩容操作可能涉及大量数据的移动，影响效率。
链栈：插入和删除操作较为灵活，只需要修改指针即可，不需要移动数据元素。但在查找特定元素时，可能需要遍历整个链表，效率较低。
内存分配：
顺序栈：通常在编译时或程序开始时分配一块连续的内存空间。
链栈：节点在需要时动态分配内存空间，当节点不再需要时，可以释放其占用的内存空间。

联系

基本性质：无论是顺序栈还是链栈，它们都是栈结构的具体实现方式，都遵循栈的“后进先出”（LIFO）原则。
基本操作：两者都支持栈的基本操作，如入栈（push）、出栈（pop）、获取栈顶元素（getTop）等。
应用场景：在需要栈结构来解决问题时，可以根据具体需求选择顺序栈或链栈来实现。例如，在处理大量数据且数据大小可预测时，可以选择顺序栈；在数据大小不确定或需要频繁插入和删除操作时，可以选择链栈。

五、联系

1.使用顺序栈，完成，c语言源文件，{}，（），【】，符号陪、匹配问题。

#ifndef SEQSTACK_H
#define SEQSTACK_Htypedef struct{char  sym;int col;int row;
}DATATYPE;typedef struct
{DATATYPE* head;int tlen;int top;// clen
}SeqStack;SeqStack*CreateSeqStack(int size);
int DestroySeqStack(SeqStack*ss);
int PushSeqStack(SeqStack*ss,DATATYPE*data);
int PopSeqStack(SeqStack*ss);
int IsEmptySeqStack(SeqStack*ss);
int IsFullSeqStack(SeqStack*ss);
int GetSizeSeqStack(SeqStack*ss);
DATATYPE*GetTopSeqStack(SeqStack*ss);
#endif // SEQSTACK_H

#include "seqstack.h"
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
SeqStack *CreateSeqStack(int size)
{SeqStack* ss = ( SeqStack*)malloc(sizeof(SeqStack));if(NULL ==ss){perror("CreateSeqStack error malloc1");return NULL;}ss->head = ( DATATYPE*)malloc(sizeof(DATATYPE)*size);if(NULL ==ss->head){perror("CreateSeqStack error malloc2");return NULL;}ss->tlen = size;ss->top =  0;return ss;
}int PushSeqStack(SeqStack *ss, DATATYPE *data)
{if(NULL == ss ||NULL ==data){fprintf(stderr,"SeqStack or data  is null \n");return 1;}if(IsFullSeqStack(ss)){fprintf(stderr,"PushSeqStack full\n");return 1;}memcpy(&ss->head[ss->top],data,sizeof(DATATYPE));ss->top++;return 0;
}int PopSeqStack(SeqStack *ss)
{if(NULL == ss ){fprintf(stderr,"SeqStack  is null \n");return 1;}if(IsEmptySeqStack(ss)){fprintf(stderr,"PopSeqStack is empty \n");return 1;}ss->top--;return 0;
}int IsEmptySeqStack(SeqStack *ss)
{return 0 == ss->top;
}int IsFullSeqStack(SeqStack *ss)
{return ss->top == ss->tlen;
}DATATYPE *GetTopSeqStack(SeqStack *ss)
{if(IsEmptySeqStack(ss)){return NULL;}return &ss->head[ss->top-1];
}int DestroySeqStack(SeqStack *ss)
{free(ss->head);free(ss);return 0;
}int GetSizeSeqStack(SeqStack *ss)
{return ss->top;
}

main.c

#include <stdio.h>
#include "seqstack.h"
#include <string.h>
#include <stdlib.h>
int do_handle(char *linebuf ,SeqStack* ss,int row)
{DATATYPE* tmp =NULL;DATATYPE data;bzero(&data,sizeof(data));int col = 1;while(*linebuf){char c = *linebuf;switch (c){case '(':case '[':case '{':data.sym = c;data.col = col;data.row = row;PushSeqStack(ss,&data);break;case ')':tmp = GetTopSeqStack(ss);if(NULL != tmp &&'(' == tmp->sym){PopSeqStack(ss);}else{if(NULL == tmp){fprintf(stderr," ')' error row:%d col:%d \n",row,col);}else{fprintf(stderr," ')' error row:%d col:%d or stack top sym:%c row:%d col:%d\n",row,col,tmp->sym,tmp->row,tmp->col);}return 1;}break;case ']':tmp = GetTopSeqStack(ss);if(NULL != tmp &&'[' == tmp->sym){PopSeqStack(ss);}else{if(NULL == tmp){fprintf(stderr," ']' error row:%d col:%d\n",row,col);}else{fprintf(stderr," ']' error row:%d col:%d or stack top sym:%c row:%d col:%d\n",row,col,tmp->sym,tmp->row,tmp->col);}return 1;}break;case '}':tmp = GetTopSeqStack(ss);if(NULL != tmp &&'{' == tmp->sym){PopSeqStack(ss);}else{if(NULL == tmp){fprintf(stderr," '}' error row:%d col:%d \n",row,col);}else{fprintf(stderr," '}' error row:%d col:%d or stack top %c row:%d col:%d\n",row,col,tmp->sym,tmp->row,tmp->col);}return 1;}break;}linebuf++;col++;}return 0;}
int main()
{SeqStack* ss = CreateSeqStack(100);FILE *fp=fopen("/home/linux/1.c","r");if(NULL == fp){return 1;}int row =1;int flag = 0;while(1){char buf[1024]={0};if(NULL==fgets(buf,sizeof(buf),fp)){break;}int ret = do_handle(buf,ss,row);if(1 == ret){flag =1;break;}row++;}fclose(fp);if(1 == flag){DestroySeqStack(ss);exit(1);}if(IsEmptySeqStack(ss)){printf("file ok\n");}else{DATATYPE* tmp = GetTopSeqStack(ss);fprintf(stderr,"stack top %c row:%d col:%d\n",tmp->sym,tmp->row,tmp->col);}DestroySeqStack(ss);printf("Hello World!\n");return 0;
}