嵌入式培训之数据结构学习（五）栈与队列

一、栈

（一）栈的基本概念

1、栈的定义：

注：线性表中的栈在堆区（因为是malloc来的）；系统中的栈区存储局部变量、函数形参、函数返回值地址。

2、栈顶和栈底：

        允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)，不含任何数据元素的栈称为空栈。

3、 LIFO 结构：栈又称为后进先出(LastInFirst0ut)的线性表。

4、栈示意图：

top为栈顶指针

5、栈对线性表的插入和删除的位置进行了限制，并没有对元素进出的时间进行限制，

也就是说，在不是所有元素都进栈的情况下，事先进去的元素也可以出栈，只要保证是

栈顶元素出栈就可以。

6、应用：解决的问题要回溯、递归可以用链栈；

               有优先级问题的用栈处理。

（1）直观应用（eg：gdb调试中的where命令）：函数调用返回原函数用栈结构（一层

一层进、一层一层退）；

（2）（3 + 5 * 6）四则运算表达式

优先级问题、字符串解析（先扫一遍表达式，再套用优先级顺序对优先级高的优先处理，最后在退回来处理表达式）。

（二）链栈的基本操作

1、创建链栈

LinkStack* CreateLinkStack() 
{ 
    // 分配链栈结构体空间，void* 强转为 LinkStack* 
    LinkStack* ls = (LinkStack*)malloc(sizeof(LinkStack)); 
    if(NULL == ls) 
    { 
        // 打印错误信息到标准错误流 
        fprintf(stderr,"CreateLinkStack malloc\n"); 
        return NULL; // 分配失败返回空 
    } 
    ls->top = NULL; // 初始化栈顶指针为空（空栈） 
    ls->clen = 0; // 初始化栈长度为0 
    return ls; // 返回创建好的链栈指针 
}

2、入栈

int PushLinkStack(LinkStack* ls, DATATYPE* data) 
{ 
    // 分配新节点空间 
    LinkStackNode* newnode = malloc(sizeof(LinkStackNode)); 
    if(NULL == newnode) 
    { 
        fprintf(stderr,"PushLinkStack malloc\n"); // 打印内存分配失败信息 
        return 1; // 失败返回错误码1 
    } 
    // 将数据拷贝到新节点的数据域 
    memcpy(&newnode->data, data, sizeof(DATATYPE)); 
    newnode->next = NULL; // 新节点初始next指针为空 
    newnode->next = ls->top; // 新节点next指向原栈顶节点（头插法） 
    ls->top = newnode; // 栈顶更新为新节点 
    ls->clen++; // 栈长度加1 
    return 0; // 成功返回0（原代码缺失return，需补充）
}

3、出栈

int PopLinkStack(LinkStack* ls) 
{ 
    if(IsEmptyLinkStack(ls)) // 检查栈是否为空 
    { 
        return 1; // 空栈返回错误码1 
    } 
    LinkStackNode* tmp = ls->top; // 保存当前栈顶节点指针 
    ls->top = ls->top->next; // 栈顶指针后移一位（指向原次栈顶） 
    free(tmp); // 释放原栈顶节点内存 
    ls->clen--; // 栈长度减1 
    return 0; // 成功返回0 
}

4、判断栈空

int IsEmptyLinkStack(LinkStack* ls) 
{ 
    // 栈长度为0时返回1（真），否则返回0（假） 
    return 0 == ls->clen; 
}

5、获取栈顶元素

DATATYPE* GetTopLinkStack(LinkStack* ls) 
{ 
    if(IsEmptyLinkStack(ls)) // 检查栈是否为空 
    { 
        return NULL; // 空栈返回空指针 
    } 
    // 返回栈顶节点数据域的地址（需确保调用时不为空） 
    return &ls->top->data; 
}

6、销毁链栈

int DestroyLinkStack(LinkStack* ls) 
{ 
    int len = GetSizeLinkStack(ls); // 获取栈当前长度 
    for(int i = 0; i < len; ++i) 
    { 
        PopLinkStack(ls); // 循环调用出栈函数释放所有节点 
    } 
    free(ls); // 释放链栈结构体本身的内存 
    return 0; // 成功返回0 
}

注：查看是否内存泄漏：valgrind  ./app

7、获取栈长度

int GetSizeLinkStack(LinkStack* ls) 
{ 
    // 直接返回结构体中记录的栈长度（O(1)时间复杂度） 
    return ls->clen; 
}

（三）栈练习：C语言文本检查器（符号匹配）

1、代码：

（1）文件读取函数 readfile
 int readfile(char *filename, char *filecontext) 
{ 
    // 以只读模式打开文件 
    FILE *fp = fopen(filename, "r"); 
    if (NULL == fp) 
    { 
        return 1; // 打开失败返回1 
    } 
    // 从文件读取1024字节到filecontext缓冲区，返回实际读取块数（此处块大小为1字节） 
    fread(filecontext, 1024, 1, fp); 
    fclose(fp); // 关闭文件 
    return 0; // 成功返回0 
}

（2） 主函数 main
 
int main(int argc, char **argv) 
{ 
    char buf[1024] = {0}; // 初始化1024字节缓冲区 
    int ret = readfile("/home/linux/2.c", buf); // 读取文件内容到buf 
    if (1 == ret) 
    { 
        return 1; // 读取失败直接退出 
    } 

    LinkStack *ls = CreateLinkStack(); // 创建链栈用于符号匹配 
    char *tmp = buf; // 临时指针指向缓冲区起始位置 
    DATATYPE data = {0}; // 存储符号及其行列信息的结构体 
    int row = 1; // 当前行号，初始为1 
    int col = 1; // 当前列号，初始为1 
    DATATYPE *top; // 用于存储栈顶元素的指针 

    while (*tmp) // 遍历缓冲区直到遇到'\0' 
    { 
        memset(&data, 0, sizeof(DATATYPE)); // 清空结构体数据 
        switch (*tmp) // 根据当前字符判断类型 
        {
            // 处理左括号：( [ {
            case '(': 
            case '[': 
            case '{': 
                data.c = *tmp; // 存储符号 
                data.col = col; // 存储列号 
                data.row = row; // 存储行号 
                PushLinkStack(ls, &data); // 将符号入栈 
                break;

            // 处理右括号：)
            case ')': 
                top = GetTopLinkStack(ls); // 获取栈顶元素 
                // 栈顶存在且为匹配的'(' 
                if ('(' == top->c && NULL != top) 
                { 
                    PopLinkStack(ls); // 匹配成功，出栈 
                } 
                else 
                { 
                    if (NULL == top) // 栈空，说明缺少左括号 
                    { 
                        // 输出错误：右括号无匹配左括号 
                        printf("sym:%c row:%d col%d\n", ')', row, col); 
                    } 
                    else // 栈顶符号不匹配（如栈顶是'['或'{'） 
                    { 
                        // 输出错误：栈顶符号与当前右括号不匹配 
                        printf(
                            "top sym:%c row:%d col%d , or file sym:%c row:%d col%d\n", 
                            top->c, top->row, top->col, *tmp, row, col); 
                    } 
                    return 1; // 匹配失败，程序退出 
                } 
                break;

            // 处理右括号：]（逻辑同'）'）
            case ']': 
                top = GetTopLinkStack(ls); 
                if ('[' == top->c && NULL != top) 
                { 
                    PopLinkStack(ls); 
                } 
                else 
                { 
                    if (NULL == top) 
                    { 
                        printf("sym:%c row:%d col%d\n", ']', row, col); // 注意此处误写为')'，应为']' 
                    } 
                    else 
                    { 
                        printf(
                            "top sym:%c row:%d col%d , or file sym:%c row:%d col%d\n", 
                            top->c, top->row, top->col, *tmp, row, col); 
                    } 
                    return 1; 
                } 
                break;

            // 处理右括号：}（逻辑同'）'）
            case '}': 
                top = GetTopLinkStack(ls); 
                if ('{' == top->c && NULL != top) 
                { 
                    PopLinkStack(ls); 
                } 
                else 
                { 
                    if (NULL == top) 
                    { 
                        printf("sym:%c row:%d col%d\n", '}', row, col); // 注意此处误写为')'，应为'}' 
                    } 
                    else 
                    { 
                        printf(
                            "top sym:%c row:%d col%d , or file sym:%c row:%d col%d\n", 
                            top->c, top->row, top->col, *tmp, row, col); 
                    } 
                    return 1; 
                } 
                break;
        }

        col++; // 列号递增 
        if ('\n' == *tmp) // 遇到换行符 
        { 
            col = 1; // 列号重置为1 
            row++; // 行号递增 
        } 
        tmp++; // 移动到下一个字符 
    }

    // 遍历结束后检查栈是否为空（所有左括号是否匹配）
    if ('\0' == *tmp && IsEmptyLinkStack(ls)) 
    { 
        printf("ok"); // 完全匹配，输出"ok" 
    } 
    else 
    { 
        top = GetTopLinkStack(ls); // 获取剩余未匹配的左括号 
        // 输出未匹配的左括号及其位置 
        printf("top sym:%c row:%d col%d\n", top->c, top->row, top->col); 
    }

    DestroyLinkStack(ls); // 销毁链栈，释放内存 
    return 0; 
}

2、输出结果：匹配成功输出ok，匹配不成功输出符号及其位置。

二、队列

（一）队列的基本概念

1、队列的定义：

2、FIFO结构：队列是一种先进先出(FirstInFirst0ut)的线性表。

     允许插入的一 端称为队尾，允许删除的一端称为队头。

3、队列示意图

clen = （尾巴 - 头 + 长度）

4、应用：计算机做缓冲用队列；

5、循环队列（圆环）：（求余就循环起来）

6、面试问题：满队判断条件：尾巴+1==头   (tail + 1 ) % tlen == head

                       空队：尾巴==头   tail == head

（二）队列的基本操作

1、创建顺序队列

SeqQueue* CreateSeqQue(int len) 
{ 
    // 分配顺序队列结构体空间，强转为 SeqQueue* 
    SeqQueue* sq = (SeqQueue*)malloc(sizeof(SeqQueue)); 
    if(NULL == sq) 
    { 
        // 打印结构体内存分配失败信息到标准错误流 
        fprintf(stderr,"CreateSeqQue malloc\n"); 
        return NULL; // 失败返回空 
    } 
    // 分配队列数据存储数组空间（容量为len） 
    sq->array = malloc(sizeof(DATATYPE)*len); 
    if(NULL == sq->array) 
    { 
        // 打印数组内存分配失败信息 
        fprintf(stderr,"CreateSeqQue malloc\n"); 
        free(sq); // 释放已分配的结构体空间（避免内存泄漏） 
        return NULL; 
    } 
    sq->head = 0; // 初始化头指针（指向队头元素前一个位置） 
    sq->tail = 0; // 初始化尾指针（指向队尾元素位置） 
    sq->tlen = len; // 记录队列总长度（容量） 
    return sq; // 返回创建好的顺序队列指针 
}

2、判断队空

int IsEmptySeqQue(SeqQueue* sq) 
{ 
    // 头指针等于尾指针时队列为空（返回1表示真，0表示假） 
    return sq->head == sq->tail; 
}

3、判断队满

int IsFullSeqQue(SeqQueue* sq) 
{ 
    // 尾指针下一个位置（循环取模）等于头指针时队满 
    return (sq->tail + 1) % sq->tlen == sq->head; 
}

4、入队

int EnterSeqQue(SeqQueue* sq, DATATYPE* data) 
{ 
    if(IsFullSeqQue(sq)) 
    { 
        // 打印队满错误信息 
        fprintf(stderr,"EnterSeqQue,SeqQueue full\n"); 
        return 1; // 失败返回错误码1 
    } 
    // 将数据拷贝到尾指针当前位置的数组元素中 
    memcpy(&sq->array[sq->tail], data, sizeof(DATATYPE)); 
    // 尾指针后移一位（循环队列，取模实现环形） 
    sq->tail = (sq->tail + 1) % sq->tlen; 
    return 0; // 成功返回0 
}

5、出队

int QuitSeqQue(SeqQueue* sq) 
{ 
    if(IsEmptySeqQue(sq)) 
    { 
        // 打印队空错误信息 
        fprintf(stderr,"QuitSeqQue SeqQueue empty\n"); 
        return 1; // 失败返回错误码1 
    } 
    // 头指针后移一位（指向实际队头元素，取模实现环形） 
    sq->head = (sq->head + 1) % sq->tlen; 
    return 0; // 成功返回0 
}

6、获取队头元素

DATATYPE* GetHeadSeqQue(SeqQueue* sq) 
{ 
    if(IsEmptySeqQue(sq)) 
    { 
        return NULL; // 队空返回空指针 
    } 
    // 返回队头元素地址（头指针当前指向的是队头元素的位置） 
    return &sq->array[sq->head]; 
}

7、销毁顺序队列

int DestroySeqQue(SeqQueue* sq) 
{ 
    free(sq->array); // 先释放数据存储数组的内存 
    free(sq); // 再释放队列结构体的内存 
    return 0; // 成功返回0 
}