链式栈
链式栈用链表实现,栈顶为链表头部(头结点之后),入栈出栈都在头部操作,无需担心栈满。
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;
}
时间复杂度:入栈、出栈均为 ,且链式栈不会栈满。
习题 1
栈的顺序存储和链式存储有何优缺点?
解题思路:
本题考查栈的两种存储结构的优缺点对比。答题时从空间分配方式、是否支持随机访问、栈满溢出风险和插入删除的代价四个角度分别评述顺序栈与链式栈。
详细步骤:
- 顺序栈:空间连续、实现简单、支持随机访问,但需要预先分配空间,存在栈满溢出的风险。
- 链式栈:空间按需分配、不会栈满,插入与删除都在栈顶(链表头部)完成(),但不支持随机访问,每个结点需额外存储指针。
- 取舍结论:栈规模可预判且要求随机访问时用顺序栈,规模变化大或要求动态伸缩时用链式栈。
最终答案:
顺序栈:空间连续、实现简单、支持随机访问,但需要预先分配空间,存在栈满溢出风险。链式栈:空间按需分配、不会栈满,插入/删除都在头部(),但不支持随机访问,每个结点需额外存储指针。
