言十年的博客

上善若水,水善利萬物而不爭

物盡其用!人盡其才!兩全其美!


栈【总结】

栈跟堆的区别?

分配内存的方式不一样。

静态的,局部变量,以压栈的方式分配内存。

堆是堆排序的方式分配的内存。malloc是分配到堆上的。

线性结构的两种常见应用之一 栈

定义:

一种可以实现“先进后出”的存储结构

栈类似于箱子

分类:

静态栈:从下往上的放。比如:数组

动态栈:元素之间不联系。比如:链表

用的最多的还是动态栈。

算法:

出栈

压栈

###模拟栈代码

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct Node
{
    int data;
    struct Node * pNext;
}NODE, * PNODE;

typedef struct Stack
{
    PNODE pTop;
    PNODE pBottom;
}STACK, * PSTACK;
void init(PSTACK pS);
bool empty(PSTACK pS);
void push(PSTACK pS, int val);
bool pop(PSTACK pS, int *pVal);
void traverse(PSTACK pS);
void clearA(PSTACK pS);
int main(int argc, const char * argv[]) {
    // insert code here...
    
    STACK S; //STACK 等价于 struct Stack
    
    init(&S);
    push(&S, 1);
    push(&S, 2);
    push(&S, 3);
    push(&S, 4);
    traverse(&S);
    int pVal;
    pop(&S, &pVal);
    clearA(&S);
    traverse(&S);
    return 0;
}
// pS->bottom 如果等于 pS->top 说明为空栈
void init(PSTACK pS)
{
    //我们希望top是头,bottom是底指向一个没有实际含义的元素
    pS->pTop = (PNODE)malloc(sizeof(NODE));
    if (NULL == pS->pTop) {
        printf("动态内存分配失败!\n");
        exit(-1);
    } else {
        pS->pBottom = pS->pTop;
        pS->pTop->pNext = NULL; // 如果top跟bottom的pSNext指向的都为空,那么就为空栈
    }
}
void push(PSTACK pS, int val)
{
    PNODE pNew = (PNODE)malloc(sizeof(NODE));
    
    pNew->data = val;
    pNew->pNext = pS->pTop;//pS->top不能改成pS—>bottom
    pS->pTop = pNew;
}
void traverse(PSTACK pS)
{
    PNODE p = pS->pTop;
    
    while (p != pS->pBottom) {
        printf("遍历%d\n", p->data);
        p = p->pNext;
    }
    return ;
}
bool empty(PSTACK pS)
{
    if (pS->pTop == pS->pBottom) {
        return true;
    }
    return false;
}

//把pS所指向的栈出栈一次,并把出栈的元素存入pVal 形参指向的变量中,如果出栈失败,返回false,否则返回true
bool pop(PSTACK pS, int *pVal)
{
    if (empty(pS)) {
        return false;
    }
    PNODE top = pS->pTop;
    pS->pTop = top->pNext;
    *pVal = top->data;
    free(top);
    top = NULL; //free函数只是把指针指向的内存空间释放了,即内存中存储的值,但是并没有将指针的值赋为NULL,指针仍然指向这块内存。top->data很有可能指向垃圾值,所以要设置NULL
    return true;
}
// 清空
void clearA(PSTACK pS)
{
    if (empty(pS)) {
        return;
    }
    PNODE p = pS->pTop;
    PNODE q = NULL;
    while (p != pS->pBottom ) {
        q = p->pNext;
        free(p);
        p = q;
    }
    pS->pTop = pS->pBottom;
}

###应用:

函数调用

栈的应用

 f() {
    g()
 }
 
 g() {
    k()
 }
 k() {
 }

 k(把k函数执行完后的下一个语句的地址,以及为所有为k函数分配的形参、局部变量以及其他相关信息,压入到栈中执行)调用完k出栈(分配的内存就没有了,出栈其中包含的下一个语句的地址找到,赋值cpu中的寄存器cs ds执行)返回到g,g调用完出栈返回到f。

中断

表达式求值

内存分配

缓冲处理

迷宫

參考資料:

  • 《啊哈算法》作者:紀磊
  • 《郝斌數據結構》視頻
分享到