链式栈

链式栈用链表实现,栈顶为链表头部(头结点之后),入栈出栈都在头部操作,无需担心栈满。

typedef struct SNode {
    int data;
    struct SNode *next;
} SNode, *LinkStack;

// 入栈(头插法)
bool Push(LinkStack &S, int x) {
    SNode *s = (SNode *)malloc(sizeof(SNode));
    s->data = x;
    s->next = S->next;  // S 为头结点
    S->next = s;
    return true;
}

// 出栈
bool Pop(LinkStack &S, int &x) {
    if (S->next == NULL) return false;  // 栈空
    SNode *p = S->next;
    x = p->data;
    S->next = p->next;
    free(p);
    return true;
}

时间复杂度:入栈、出栈均为 O(1)O(1),且链式栈不会栈满。

习题

习题 1

栈的顺序存储和链式存储有何优缺点?

顺序栈链式栈存储结构时间复杂度

解题思路:

本题考查栈的两种存储结构的优缺点对比。答题时从空间分配方式、是否支持随机访问、栈满溢出风险和插入删除的代价四个角度分别评述顺序栈与链式栈。

详细步骤:

  1. 顺序栈:空间连续、实现简单、支持随机访问,但需要预先分配空间,存在栈满溢出的风险。
  2. 链式栈:空间按需分配、不会栈满,插入与删除都在栈顶(链表头部)完成(O(1)O(1)),但不支持随机访问,每个结点需额外存储指针。
  3. 取舍结论:栈规模可预判且要求随机访问时用顺序栈,规模变化大或要求动态伸缩时用链式栈。

最终答案:

顺序栈:空间连续、实现简单、支持随机访问,但需要预先分配空间,存在栈满溢出风险。链式栈:空间按需分配、不会栈满,插入/删除都在头部(O(1)O(1)),但不支持随机访问,每个结点需额外存储指针。

发现内容有问题?

告诉我们哪里需要改进。