2025年跟着陈姥姥学习数据结构之栈

科技前沿 • 2025-02-08 11:29 • 阅读 37

大家好，我是讯享网，很高兴认识大家。

陈姥姥是浙江大学的一名老师，她在mooc上的《数据结构》广受好评，我也专门进行了学习，课讲的确实很好，适合系统地学习数据结构。
在这里插入图片描述
讯享网

真正意义上的，好大学没有围墙。

栈

栈的定义：

栈是一种运算受限的线性表，其限制是指只仅允许在表的一端进行插入和删除操作，这一端被称为栈顶（Top），相对地，把另一端称为栈底（Bottom）。

栈的操作：
在这里插入图片描述

栈的应用：
栈最重要的一种用法是用来做算数运算的后缀表达式。
在这里插入图片描述

在这里插入图片描述

代码实现

最后附上栈的顺序实现和链式实现：

讯享网

讯享网 **顺序实现** typedef int Position; struct SNode { 
    int *Data; /* 存储元素的数组 */ Position Top; /* 栈顶指针 */ int MaxSize; /* 堆栈最大容量 */ }; typedef struct SNode *Stack; Stack CreateStack(int MaxSize); bool IsFull(Stack S); bool Push(Stack S, int X); bool IsEmpty(Stack S); int Pop(Stack S); Stack CreateStack(int MaxSize) { 
    Stack S = (Stack)malloc(sizeof(struct SNode)); S->Data = (int *)malloc(MaxSize * sizeof(int)); S->Top = -1; S->MaxSize = MaxSize; return S; } bool IsFull(Stack S) { 
    return (S->Top == S->MaxSize - 1); } bool Push(Stack S, int X) { 
    if (IsFull(S)) { 
    printf("堆栈满"); return false; } else { 
    S->Data[++(S->Top)] = X; //++i=i+1=i 同时实现top指针上移和赋值 return true; } } bool IsEmpty(Stack S) { 
    return (S->Top == -1); } int Pop(Stack S) { 
    if (IsEmpty(S)) { 
    printf("堆栈空"); return ERROR; /* ERROR是ElementType的特殊值，标志错误 */ } else return (S->Data[(S->Top)--]);//这里并没有销毁原栈顶元素 } **链式存储** typedef struct SNode *PtrToSNode; struct SNode { 
    int Data; PtrToSNode Next; }; typedef PtrToSNode Stack; Stack CreateStack_link(); bool IsEmpty_link(Stack S); bool Push_link(Stack S, int X); int Pop_link(Stack S); Stack CreateStack_link() { 
    /* 构建一个堆栈的头结点，返回该结点指针 */ Stack S; S = (Stack)malloc(sizeof(struct SNode)); S->Next = NULL; return S; } bool IsEmpty_link(Stack S) { 
    /* 判断堆栈S是否为空，若是返回true；否则返回false */ return (S->Next == NULL); } bool Push_link(Stack S, int X) { 
    /* 将元素X压入堆栈S */ PtrToSNode TmpCell; TmpCell = (PtrToSNode)malloc(sizeof(struct SNode)); TmpCell->Data = X; TmpCell->Next = S->Next; S->Next = TmpCell; return true; } int Pop_link(Stack S) { 
    /* 删除并返回堆栈S的栈顶元素 */ PtrToSNode FirstCell; int TopElem; if (IsEmpty_link(S)) { 
    printf("堆栈空"); return ERROR; } else { 
    FirstCell = S->Next; TopElem = FirstCell->Data; S->Next = FirstCell->Next; free(FirstCell); return TopElem; } }

2025年跟着陈姥姥学习数据结构之栈

栈

代码实现

相关推荐