栈的常见操作

野性酷女 2022-05-25 23:46 198阅读 0赞

##### 今天正好下午没课，就接着昨天所看的课程一口气把郝斌老师有关栈的视频也刷完了，通过他用代码实现栈的常见操作使我对栈也有了一个进一步的认识，下面是我看过视频后参考郝斌老师的代码对栈常见功能的代码实现。 #####

#include <stdio.h>
    #include <stdlib.h>
    typedef struct Node{
        int data;
        struct Node* pNext;
    } Node,* PNode;
    
    typedef struct Stack{
       //创建两个指针分别指向栈顶和栈底
        PNode pTop;
        PNode pBottom;//总是指向栈的头节点
    } Stack,* PStack;
    
    void init(PStack);//初始化一个栈
    void push(PStack,int);//入栈
    void traverse(PStack);//遍历
    void pop(PStack,int*);//出栈
    void clear(PStack);//重置栈中的数据
    int main() {
        Stack S;
        int val;
        init(&S);
        push(&S,1);
        push(&S,2);
        push(&S,3);
        push(&S,4);
        push(&S,5);
        push(&S,6);
        traverse(&S);
        pop(&S,&val);
        printf("pop的值为%d\n",val);
        traverse(&S);
        clear(&S);
        traverse(&S);
        return 0;
    }
    
    void init(PStack pS){
        pS->pTop = (PNode)malloc(sizeof(Node));
        if(pS == NULL){
            printf("分配内存失败!\n");
            exit(-1);
        }else{
            pS->pBottom = pS->pTop;
            pS->pBottom->pNext = NULL;
        }
        return;
    }
    
    void push(PStack pS,int val){
        PNode pNew = (PNode)malloc(sizeof(Node));
        pNew->data  = val;
        pNew->pNext = pS->pTop;
        pS->pTop = pNew;
        return;
    }
    
    void traverse(PStack pS){
        if(pS->pTop == pS->pBottom){
            printf("栈为空!\n");
            return;
        }else{
            PNode p = pS->pTop;
            while (p != pS->pBottom) {
                printf("%d ",p->data);
                p = p->pNext;
            }
            printf("\n");
        }
        return;
    }
    
    void pop(PStack pS,int* val){
       //这里的int *val是为了让用户知道pop的数据是什么
        if(pS->pTop == pS->pBottom){
            printf("栈为空!\n");
            return;
        }else{
            *val = pS->pTop->data;
            PNode p = pS->pTop;
            pS->pTop = pS->pTop->pNext;
            free(p);
            p = NULL;
        }
        return;
    }
    
    void clear(PStack pS){
        if(pS->pTop == pS->pBottom){
            printf("栈为空!\n");
            return;
        }else{
            PNode p = pS->pTop;
            PNode q;
            while (p != pS->pBottom) {
                q = p;
                p = p->pNext;
                free(q);
                q = NULL;
            }
            pS->pTop = pS->pBottom;
            printf("已clear成功!\n");
            return;
        }
    }

##### 注：个人感觉有链表基础再去理解栈并不难，我认为所谓的栈只不过是给常见的链表加一个总是指向栈底的指针和一个总是指向栈顶的指针，并且每次添加使其总是添加在栈顶，并更新一下指向栈顶的那个指针便可。和链表相比，栈和链表的区别在链表的头节点是在链表的头部，而对于栈，头节点则是在栈低，即指向栈底的指针总是指向头节点。以上都是我个人学习后总结的一些看法，如果我的总结有不对的地方，请各位看到了之后帮我指出，谢谢(°ω°)ﾉ” #####