数据结构实战：链表、栈与队列的C语言实现

数据结构实战：链表、栈与队列的 C 语言实现
（清晰、可读、可直接编译运行的版本，2025–2026 教学/面试常用风格）

下面给出三种最经典数据结构的完整、可独立编译运行的 C 语言实现，包含：

• 单向链表（带头结点）
• 栈（基于链表实现 + 基于数组实现两种）
• 队列（基于链表实现 + 基于数组的循环队列）

每种结构都包含最常用的核心操作，并附带 main 函数测试。

1. 单向链表（带头结点）

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

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

// 创建新节点
Node* createNode(int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("内存分配失败！\n");
        exit(1);
    }
    newNode->data = value;
    newNode->next = NULL;
    return newNode;
}

// 初始化带头结点的链表
Node* initList() {
    return createNode(0);  // 头结点，data 不用
}

// 尾插法
void append(Node* head, int value) {
    Node* newNode = createNode(value);
    Node* p = head;
    while (p->next != NULL) {
        p = p->next;
    }
    p->next = newNode;
}

// 头插法
void prepend(Node* head, int value) {
    Node* newNode = createNode(value);
    newNode->next = head->next;
    head->next = newNode;
}

// 在指定位置后插入（pos 从 0 开始，0 表示头结点后）
void insertAfter(Node* head, int pos, int value) {
    Node* p = head;
    int i = 0;
    while (p != NULL && i < pos) {
        p = p->next;
        i++;
    }
    if (p == NULL) {
        printf("插入位置 %d 无效！\n", pos);
        return;
    }
    Node* newNode = createNode(value);
    newNode->next = p->next;
    p->next = newNode;
}

// 删除指定值的第一个节点
void deleteValue(Node* head, int value) {
    Node* p = head;
    while (p->next != NULL && p->next->data != value) {
        p = p->next;
    }
    if (p->next == NULL) {
        printf("未找到值为 %d 的节点\n", value);
        return;
    }
    Node* temp = p->next;
    p->next = temp->next;
    free(temp);
}

// 打印链表
void printList(Node* head) {
    Node* p = head->next;
    if (p == NULL) {
        printf("链表为空\n");
        return;
    }
    while (p != NULL) {
        printf("%d -> ", p->data);
        p = p->next;
    }
    printf("NULL\n");
}

// 释放整个链表
void freeList(Node* head) {
    Node* p = head;
    while (p != NULL) {
        Node* temp = p;
        p = p->next;
        free(temp);
    }
}

int main() {
    Node* list = initList();

    append(list, 10);
    append(list, 20);
    prepend(list, 5);
    insertAfter(list, 1, 15);

    printf("原始链表：");
    printList(list);

    deleteValue(list, 20);
    printf("删除 20 后：");
    printList(list);

    freeList(list);
    return 0;
}

2. 栈（两种实现）

2.1 基于链表的栈（无大小限制）

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

typedef struct StackNode {
    int data;
    struct StackNode* next;
} StackNode;

typedef struct {
    StackNode* top;
} Stack;

Stack* createStack() {
    Stack* s = (Stack*)malloc(sizeof(Stack));
    s->top = NULL;
    return s;
}

int isEmpty(Stack* s) {
    return s->top == NULL;
}

void push(Stack* s, int value) {
    StackNode* node = (StackNode*)malloc(sizeof(StackNode));
    node->data = value;
    node->next = s->top;
    s->top = node;
}

int pop(Stack* s) {
    if (isEmpty(s)) {
        printf("栈空！\n");
        exit(1);
    }
    StackNode* temp = s->top;
    int value = temp->data;
    s->top = temp->next;
    free(temp);
    return value;
}

int peek(Stack* s) {
    if (isEmpty(s)) {
        printf("栈空！\n");
        exit(1);
    }
    return s->top->data;
}

void freeStack(Stack* s) {
    while (!isEmpty(s)) {
        pop(s);
    }
    free(s);
}

int main() {
    Stack* s = createStack();
    push(s, 1);
    push(s, 2);
    push(s, 3);

    printf("栈顶: %d\n", peek(s));
    printf("弹出: %d\n", pop(s));
    printf("弹出: %d\n", pop(s));

    freeStack(s);
    return 0;
}

2.2 基于数组的栈（固定容量）

#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int top;
} ArrayStack;

void initArrayStack(ArrayStack* s) {
    s->top = -1;
}

int isEmptyArray(ArrayStack* s) {
    return s->top == -1;
}

int isFullArray(ArrayStack* s) {
    return s->top == MAX_SIZE - 1;
}

void pushArray(ArrayStack* s, int value) {
    if (isFullArray(s)) {
        printf("栈满！\n");
        return;
    }
    s->data[++(s->top)] = value;
}

int popArray(ArrayStack* s) {
    if (isEmptyArray(s)) {
        printf("栈空！\n");
        exit(1);
    }
    return s->data[(s->top)--];
}

3. 队列（两种实现）

3.1 基于链表的队列

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

typedef struct QNode {
    int data;
    struct QNode* next;
} QNode;

typedef struct {
    QNode* front;
    QNode* rear;
} Queue;

Queue* createQueue() {
    Queue* q = (Queue*)malloc(sizeof(Queue));
    q->front = q->rear = NULL;
    return q;
}

int isEmptyQueue(Queue* q) {
    return q->front == NULL;
}

void enqueue(Queue* q, int value) {
    QNode* node = (QNode*)malloc(sizeof(QNode));
    node->data = value;
    node->next = NULL;

    if (isEmptyQueue(q)) {
        q->front = q->rear = node;
    } else {
        q->rear->next = node;
        q->rear = node;
    }
}

int dequeue(Queue* q) {
    if (isEmptyQueue(q)) {
        printf("队列空！\n");
        exit(1);
    }
    QNode* temp = q->front;
    int value = temp->data;
    q->front = temp->next;
    if (q->front == NULL) {
        q->rear = NULL;
    }
    free(temp);
    return value;
}

void freeQueue(Queue* q) {
    while (!isEmptyQueue(q)) {
        dequeue(q);
    }
    free(q);
}

3.2 基于数组的循环队列（推荐生产使用）

#define QUEUE_MAX 100

typedef struct {
    int data[QUEUE_MAX];
    int front;
    int rear;
    int size;
} CircularQueue;

void initCircularQueue(CircularQueue* q) {
    q->front = 0;
    q->rear = 0;
    q->size = 0;
}

int isEmptyCircular(CircularQueue* q) {
    return q->size == 0;
}

int isFullCircular(CircularQueue* q) {
    return q->size == QUEUE_MAX;
}

void enqueueCircular(CircularQueue* q, int value) {
    if (isFullCircular(q)) {
        printf("队列满！\n");
        return;
    }
    q->data[q->rear] = value;
    q->rear = (q->rear + 1) % QUEUE_MAX;
    q->size++;
}

int dequeueCircular(CircularQueue* q) {
    if (isEmptyCircular(q)) {
        printf("队列空！\n");
        exit(1);
    }
    int value = q->data[q->front];
    q->front = (q->front + 1) % QUEUE_MAX;
    q->size--;
    return value;
}

总结对比表（面试常问）

数据结构	实现方式	优点	缺点	典型应用场景
链表	单向带头结点	动态大小、插入删除 O(1)（已知位置）	随机访问 O(n)，缓存不友好	频繁头尾操作、内存不连续
栈	链表实现	无大小限制	每次 push/pop 都要 malloc/free	函数调用、表达式求值、DFS
栈	数组实现	访问快、缓存友好、无碎片	固定大小	嵌入式、性能敏感场景
队列	链表实现	无大小限制、入队出队 O(1)	内存碎片、指针开销	任务队列、广度优先搜索
队列	循环数组	访问极快、无碎片、缓存友好	固定大小、浪费一个槽位判满	消息队列、缓冲区、操作系统

你接下来想重点练习/深入哪一个？

• 链表的更多操作（逆序、合并、环检测、快慢指针等）
• 栈的经典应用（括号匹配、中缀转后缀、单调栈）
• 队列的变种（优先队列、双端队列 deque）
• 手写循环队列的判满判空三种经典方法对比
• 或者直接上 LeetCode 链表/栈/队列题目的 C 语言解法

告诉我你的方向～