栈|数据结构|C语言|详细讲解|代码实现

介绍栈

内存可以分为“静态内存”和“动态内存”，讲台内存是在栈中分配的，动态内存是在堆中分配的。

静态或局部变量，是以压栈和出栈的方式分配内存的，就叫栈区；

动态内存是一个一种堆排序的方式分配内存的，就叫堆区。

栈的分类

静态栈和动态栈是两种常用的数据结构，它们的主要区别在于存储方式。

1. 静态栈：

静态栈通常使用数组来实现。它有一个固定的大小，即栈的最大容量。一旦栈满了，就无法再添加元素，除非重新分配更大的数组。静态栈的优点是操作速度快，因为数组的访问和更新都是直接进行的。但缺点是灵活性较差，因为栈的大小在创建时就已经确定，无法动态地增加或减少。

2. 动态栈：

动态栈通常使用链表来实现。与静态栈不同，动态栈的大小是动态的，可以根据需要增长或缩小。当栈满时，可以通过添加新的节点来扩展其容量；当栈空时，可以释放一些节点以减小其容量。动态栈的优点是灵活性高，可以适应不同的需求，而不需要预先确定栈的大小。但缺点是操作速度较慢，因为链表的访问和更新需要遍历节点。

总结来说，静态栈和动态栈各有优缺点。静态栈操作速度快，但灵活性差；动态栈灵活性高，但操作速度慢。选择使用哪种数据结构取决于具体的应用场景和需求。

栈可以执行哪些操作

·出栈（弹栈）

·入栈（压栈）

栈程序演示

代码实现

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

//定义链表节点的数据类型
typedef struct Node{
    int data;
    struct Node* pNext;
}NODE,*PNODE;

//定义栈数据类型
typedef struct Stack{
    PNODE top;//指向栈顶元素
    PNODE bottom;//指向栈底元素的下一个位置
}stack,*pstack;

void init(pstack s);//初始化，创建空栈
void push(pstack s,int val);//入栈
void traverse(pstack s);//出栈
int showTop(pstack s);//显示栈顶元素
int pop(pstack s);//出栈
bool isEmpty(pstack s);

int main(){
    stack S;
    init(&S);
    push(&S,1);
    push(&S,-9);
    push(&S,88);
    traverse(&S);
    printf("栈顶元素为%d\n",showTop(&S));
    printf("出来一个栈顶元素：%d\n",pop(&S));
    printf("出来一个栈顶元素：%d\n",pop(&S));
    printf("出来一个栈顶元素：%d\n",pop(&S));
    //printf("出来一个栈顶元素：%d\n",pop(&S));
    traverse(&S);


    return 0;
}

//初始化栈
//创建一个空栈，空战就是栈的top和bottom指针都指向一个空的不存储任何数据的节点
void init(pstack s){
    s->top=(PNODE)malloc(sizeof(NODE));
    if(!s->top){
        printf("动态内存分配失败\n");
        exit(-1);
    }else{
        s->bottom=s->top;
        s->top->pNext=NULL;//或s->bottom->pNext=NULL;
    }
}

void push(pstack s,int val){
    PNODE pnew=(PNODE)malloc(sizeof(NODE));
    pnew->data=val;
    pnew->pNext=s->top;/*这一步不能是pnew->pNext=s->bottom，因为这一步是入栈而不是插入第一个元素。
                          bottom和top最开始都存着的空节点的地址，但只有top一直存着最顶端元素的地址*/
    s->top=pnew;
}

void traverse(pstack s){
    if(isEmpty(s)){
        printf("栈已空，无法遍历");
        exit(-1);
    }
    PNODE p=s->top;
    while(p!=s->bottom){
        printf("%d  ",p->data);
        p=p->pNext;
    }
    printf("\n");
}

int showTop(pstack s){
    return s->top->data;
}

bool isEmpty(pstack s){
    if(s->top==s->bottom){
        return 1;
    }
    return 0;
}

int pop(pstack s){
    if(isEmpty(s)){
        printf("栈已空，无法出栈");
        exit(-1);
    }
    int val=s->top->data;
    PNODE p=s->top;
    s->top=s->top->pNext;
    free(p);
    return val;
}