欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

c语言实现链式栈

程序员文章站 2022-05-26 19:40:27
...

C语言实现链式栈

定义

定义不多说了 百度百科找了两张图片图片(侵删)
c语言实现链式栈
c语言实现链式栈

思路

代码的关键在于“先进后出”因为我们用链表实现,所以很容易想到,采用头插入办法保证“先进后出”,只需要关心第一个结点就行,入栈出栈都是针对它,毕竟找链表的尾巴很费事︿( ̄︶ ̄)︿,如果我们还要知道栈的长度什么的可以在struct中加一个len字段,出入栈的时候记录一下就行
代码也没有什么特别好解释的直接上代码吧(参考链表的实现更加简单)

代码

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

typedef int dataType;

typedef struct Node
{
    dataType data;
    struct Node *next;
}NODE,*PNODE;

typedef struct LinkStack
{
    PNODE top;                                  //栈顶指针  
}LINKSTACK,*PLINKSTACK;

PLINKSTACK createEmptyStack();                  //创建一个空栈
bool isEmptyStack(PLINKSTACK s);                //判断是否为空栈 
bool push(PLINKSTACK s, dataType x);            //入栈 
bool pop(PLINKSTACK s);                         //出栈 
void showStack(PLINKSTACK s);                   //打印所有 
dataType getTop(PLINKSTACK s);                  //获取top 
void setEmpty(PLINKSTACK s);                    //置空 
void destory(PLINKSTACK s);                     //销毁 

PLINKSTACK createEmptyStack()
{
    PLINKSTACK s = (PLINKSTACK)malloc(sizeof(LINKSTACK));
    if(s == NULL)
    {
        printf("内存分配失败\n");
    }
    else
    {
        s->top = NULL;
    } 
    return s;
}

bool isEmptyStack(PLINKSTACK s)
{
    return (s->top == NULL);
}

bool push(PLINKSTACK s,dataType x)
{   
    PNODE p = (PNODE)malloc(sizeof(NODE));
    if(p == NULL)
    {
        printf("结点分配失败\n");
        return false;
    }
    else
    {
        p->data = x;
        p->next = s->top;           //链表的下一个结点指向之前的top 第一次为NULL
        s->top = p;                 //把top指针指向新的结点p
        return true; 
    }
} 

bool pop(PLINKSTACK s)
{
    if(isEmptyStack(s))
    {
        printf("stack is empty\n");
        return false;
    }
    PNODE p = s->top;
    printf("pop: %d \n",p->data);
    s->top = p->next;
    free(p);
    p = NULL;
    return true;
}

void showStack(PLINKSTACK s)
{
    if(isEmptyStack(s))
    {
        printf("stack is empty\n");
        return ;
    }
    else
    {
        PNODE p = s->top;   
        printf("---\n");
        while(p != NULL)
        {
            printf("%d \n",p->data);
            p = p->next;
        }
        printf("---\n");
    }
}

dataType getTop(PLINKSTACK s)
{
    if(isEmptyStack(s))
    {
        printf("stack is empty\n");
        return NULL;
    }
    else
    {
        return s->top->data;
    }
} 

void setEmpty(PLINKSTACK s)
{
    if(isEmptyStack(s))
    {
        printf("stack is empty");
        return ;
    }
    //释放掉链表 (其实就是没有头结点单链表的销毁)
    PNODE p = s->top;
    PNODE temp = NULL;
    while(p != NULL) 
    {
        temp = p->next;
        free(p);
        p = temp;
    }
    //置空 
    s->top = NULL; 
} 

void destory(PLINKSTACK s)
{
    setEmpty(s);
    free(s);
    s = NULL;
} 

int main()
{
    PLINKSTACK stack = createEmptyStack(); 
    push(stack,1);
    push(stack,2);
    push(stack,3);
    showStack(stack);
    pop(stack);
    showStack(stack);
    printf("top :%d\n", getTop(stack));
    printf("setEmpty……\n");
    setEmpty(stack) ;
    showStack(stack);
    printf("destroy…… \n");
    destory(stack);
    return 0;
}

代码git
参考