数据结构之—栈

最新推荐文章于 2025-05-18 21:08:26 发布

Coder_py

最新推荐文章于 2025-05-18 21:08:26 发布

阅读量370

点赞数

分类专栏：数据结构文章标签：数据结构 java 链表 leetcode

本文链接：https://blog.csdn.net/Coder_py/article/details/106041708

版权

数据结构专栏收录该内容

3 篇文章

订阅专栏

本文详细介绍了数据结构中的栈，包括顺序栈和链栈两种实现方式。顺序栈以数组为基础，阐述了其内部结构、函数声明、进栈出栈操作以及额外的操作。链栈部分则讲解了其结构体定义、函数声明、进栈出栈过程，并配以图示辅助理解。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

数据结构之—栈

顺序栈

内部采用数组实现

结构图；

定义结构体:

typedef struct StackInfo
{
    int topOfStack; /*记录栈顶位置*/
    ElementType stack[STACK_SIZE]; /*栈数组，也可以使用动态数组实现*/
}StackInfo_st;

函数声明

int stack_push(StackInfo_st *s,ElementType value);
int stack_pop(StackInfo_st *s,ElementType *value);
int stack_top(StackInfo_st *s,ElementType *value);
int stack_is_full(StackInfo_st *s);
int stack_is_empty(StackInfo_st *s)

进栈以及出栈

图示:

图2.png

int stack_push(StackInfo_st *s,ElementType value)
{
    if(stack_is_full(s))
        return FAILURE;
    /*先增加topOfStack，再赋值*/
    s->topOfStack++;
    s->stack[s->topOfStack] = value;
    return SUCCESS;
}

int stack_pop(StackInfo_st *s,ElementType *value)
{
    /*首先判断栈是否为空*/
    if(stack_is_empty(s))
        return FAILURE;
    *value = s->stack[s->topOfStack];
    s->topOfStack--;
    return SUCCESS;
}

其余操作

/*访问栈顶元素*/
int stack_top(StackInfo_st *s,ElementType *value)
{
    /*首先判断栈是否为空*/
    if(stack_is_empty(s))
        return FAILURE;
    *value = s->stack[s->topOfStack];
    return SUCCESS;
}
/*判断栈是否已满，满返回1，未满返回0*/
int stack_is_full(StackInfo_st *s)
{
    return s->topOfStack == STACK_SIZE - 1;
}
/*判断栈是否为空，空返回1，非空返回0*/
int stack_is_empty(StackInfo_st *s)
{
    return s->topOfStack ==  - 1;
}

链栈

定义结构体:


typedef struct StackInfo
{
    ElementType value;
    struct StackInfo *next; /*指向栈的下一个元素*/
}StackInfo_st;

函数声明

StackInfo_st *createStack(void);
int stack_push(StackInfo_st *s,ElementType value);
int stack_pop(StackInfo_st *s,ElementType *value);
int stack_top(StackInfo_st *s,ElementType *value);
int stack_is_empty(StackInfo_st *s);

进栈以及出栈

图示:

图3.png


int stack_push(StackInfo_st *s,ElementType value)
{
    StackInfo_st *temp = malloc(sizeof(StackInfo_st));
    if(NULL == temp)
    {
        printf("malloc failed\n");
        return FAILURE;
    }
    /*将新的节点添加s->next前，使得s->next永远指向栈顶*/
    temp->value = value;
    temp->next = s->next;
    s->next = temp;
    return SUCCESS;
}
/*出栈*/
int stack_pop(StackInfo_st *s,ElementType *value)
{
    /*首先判断栈是否为空*/
    if(stack_is_empty(s))
        return FAILURE;
    /*找出栈顶元素*/
    *value = s->next->value;
    StackInfo_st *temp = s->next;
    s->next = s->next->next;

    /*释放栈顶节点内存*/
    free(temp);
    temp = NULL;

    return SUCCESS;
}

其余操作



/*访问栈顶元素*/
int stack_top(StackInfo_st *s,ElementType *value)
{
    /*首先判断栈是否为空*/
    if(stack_is_empty(s))
        return FAILURE;
    *value = s->next->value;
    return SUCCESS;
}
/*判断栈是否为空，空返回1，未空返回0*/
int stack_is_empty(StackInfo_st *s)
{
    /*栈顶指针为空，则栈为空*/
    return s->next == NULL;
}