每日科普 · 2026-10-05 周一

考研 408 × 求职面试

知识点 · 数据结构 · 基础

栈的顺序与链式实现

栈是后进先出（LIFO）的线性表，插入和删除都只在栈顶进行。
1. 顺序栈：用数组存储元素，并维护栈顶指针 top。通常 top=-1 表示空栈；入栈先判断是否已满，再令 data[++top]=x；出栈先判断是否为空，再取 data[top--]。优点是存储连续、实现简单、访问方便；缺点是容量固定，扩容需搬移元素。
2. 链式栈：用单链表实现，通常把栈顶设在链表头，入栈即头插，出栈即删除头结点。它不需要预分配容量，动态增长方便；但每个结点有指针开销，内存不连续，缓存局部性较差。
无论顺序还是链式，入栈、出栈、取栈顶、判空都能在 O(1) 时间完成。选择时若元素规模可预估且追求效率，可用顺序栈；若规模变化大、频繁动态增减，可用链式栈。

每日一题 · 数据结构

栈的顺序与链式实现

下列关于顺序栈和链式栈的说法，正确的是（ ）。A. 顺序栈的入栈、出栈平均时间复杂度为 O(n) B. 链式栈的栈顶应设在链表尾部，方便删除 C. 顺序栈用 top 指向栈顶元素下标，初始 top=-1，入栈可写 data[++top]=x D. 链式栈必须带头结点，否则无法 O(1) 入栈

解析

答案：C。顺序栈 top 指向栈顶下标时，空栈为 -1，入栈应先移动指针再存入，故 data[++top]=x；出栈为 x=data[top--]。A 错，顺序栈入出栈都是 O(1)；B 错，链式栈若栈顶在尾部，删除尾结点需找前驱，可能 O(n)，通常栈顶在链表头；D 错，不带头结点也可用头插、删头实现 O(1) 入栈和出栈。

面试小贴士 · 数据结构

栈的顺序与链式实现

面试常问顺序栈与链式栈区别、top 初值、判空判满、复杂度。答：顺序栈数组+top，容量固定；链式栈头插删头，动态但多指针开销。易错：忘记判空满、链式栈在尾部操作、top 指向含义混淆。

代码实现 · C

代码示例

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

typedef struct Node {
    int val;
    struct Node *next;
} Node;

typedef struct {
    Node *top;
} Stack;

void init(Stack *s) { s->top = NULL; }
int empty(Stack *s) { return s->top == NULL; }
void push(Stack *s, int x) {
    Node *p = (Node*)malloc(sizeof(Node));
    p->val = x;
    p->next = s->top;
    s->top = p;
}
int pop(Stack *s, int *x) {
    if (empty(s)) return 0;
    Node *p = s->top;
    *x = p->val;
    s->top = p->next;
    free(p);
    return 1;
}
int main(void) {
    Stack s; init(&s);
    push(&s, 1); push(&s, 2);
    int x;
    while (pop(&s, &x)) printf("%d ", x); // 输出 2 1
    return 0;
}