数据结构入门：栈与队列的实现 | 极客日志

C算法

数据结构入门：栈与队列的实现

本文介绍了数据结构中栈（Stack）和队列（Queue）的概念及 C 语言实现。栈遵循后进先出（LIFO）原则，通常使用动态数组实现，包含初始化、压栈、出栈、获取栈顶等核心操作。队列遵循先进先出（FIFO）原则，推荐使用单链表实现以避免头部删除的低效问题，包含入队、出队、获取队头队尾元素等功能。文中详细展示了结构体定义、内存管理（malloc/free）及边界条件处理，并提供了测试代码示例，帮助读者理解线性表的具体应用。

板砖工程师发布于 2026/3/29更新于 2026/4/131 浏览

数据结构入门：栈与队列的实现

栈

1.1 栈的形象概念

栈（Stack）是一种线性结构，可以想象成一个封闭的箱子。数据只能从一端插入和删除，这一端称为栈顶，另一端称为栈底。其存取方式为后进先出（LIFO, Last In First Out）或先进后出。

文章配图

图中展示了空栈到压入三个元素的过程，最底下是栈底，最顶部是栈顶。

核心操作：

压栈（Push）：数据的插入操作，从栈顶进入。
出栈（Pop）：数据的删除操作，从栈顶弹出。
栈顶定位：通常用 top 表示。初始化为 0 时代表栈顶元素的下一个位置；初始化为 -1 时代表当前栈顶元素位置。

1.2 栈的实现

栈通常以数组或链表方式实现。动态增长的数组较为常见，需要用到 malloc 进行扩容。基本操作包括初始化、压栈、出栈、获取栈顶元素、判空及销毁。

1.2.1 头文件内容

// Stack.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>

typedef int STDataType;

typedef struct Stack {
    STDataType* _a;
    int _top;      // 栈顶下标
    int _capacity; // 容量
} Stack;

// 初始化栈
void StackInit(Stack* ps);
// 入栈
void StackPush(Stack* ps, STDataType data);

 ;

STDataType ;

 ;

 ;

 ;

极客日志微信公众号二维码

更多推荐文章

相关免费在线工具

加密/解密文本
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。在线工具，加密/解密文本在线工具，online
Base64 字符串编码/解码
将字符串编码和解码为其 Base64 格式表示形式即可。在线工具，Base64 字符串编码/解码在线工具，online
Base64 文件转换器
将字符串、文件或图像转换为其 Base64 表示形式。在线工具，Base64 文件转换器在线工具，online
Markdown 转 HTML
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。在线工具，Markdown 转 HTML在线工具，online
HTML 转 Markdown
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。在线工具，HTML 转 Markdown在线工具，online
JSON 压缩
通过删除不必要的空白来缩小和压缩JSON。在线工具，JSON 压缩在线工具，online

void StackInit(Stack* s) {
    assert(s);
    s->_a = (STDataType*)malloc(sizeof(STDataType) * 4);
    if (s->_a == NULL) {
        perror("malloc fail");
        return;
    }
    s->_capacity = 4;
    s->_top = 0; // top 指向栈顶元素的下一个位置
}

void StackPush(Stack* s, STDataType x) {
    assert(s);
    if (s->_top == s->_capacity) {
        STDataType* tmp = (STDataType*)realloc(s->_a, sizeof(STDataType) * s->_capacity * 4);
        if (tmp == NULL) {
            perror("malloc fail");
            return;
        }
        s->_a = tmp;
        s->_capacity *= 4;
    }
    s->_a[s->_top] = x;
    s->_top++;
}

void StackPop(Stack* s) {
    assert(s);
    assert(!StackEmpty(s));
    s->_top--;
}

bool StackEmpty(Stack* s) {
    assert(s);
    return s->_top == 0;
}

int StackSize(Stack* s) {
    assert(s);
    return s->_top;
}

STDataType StackTop(Stack* s) {
    assert(s);
    assert(!StackEmpty(s));
    return s->_a[s->_top - 1];
}

void StackDestroy(Stack* s) {
    assert(s);
    free(s->_a);
    s->_a = NULL;
    s->_capacity = 0;
    s->_top = 0;
}

#include "Stack.h"

int main() {
    Stack st;
    StackInit(&st);
    StackPush(&st, 1);
    StackPush(&st, 2);
    StackPush(&st, 3);
    StackPush(&st, 4);
    StackPush(&st, 5);
    StackPush(&st, 6);
    
    while (!StackEmpty(&st)) {
        printf("%d ", StackTop(&st));
        StackPop(&st);
    }
    StackDestroy(&st);
    return 0;
}

// QueueNode 定义
typedef int QDatatype;
typedef struct QueueNode {
    struct QueueNode* next;
    QDatatype data;
} QNode;

// Queue 定义
typedef struct Queue {
    QNode* head;
    QNode* tail;
    int size;
} Queue;

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>

typedef int QDatatype;
typedef struct QueueNode { struct QueueNode* next; QDatatype data; } QNode;
typedef struct Queue { QNode* head; QNode* tail; int size; } Queue;

void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);
void QueuePush(Queue* pq, QDatatype x);
void QueuePop(Queue* pq);
int QueueSize(Queue* pq);
bool QueueEmpty(Queue* pq);
QDatatype QueueFront(Queue* pq);
QDatatype QueueBack(Queue* pq);

#include "Queue.h"

// 初始化
void QueueInit(Queue* pq) {
    assert(pq);
    pq->head = pq->tail = NULL;
    pq->size = 0;
}

// 销毁
void QueueDestroy(Queue* pq) {
    assert(pq);
    QNode* cur = pq->head;
    while (cur) {
        QNode* next = cur->next;
        free(cur);
        cur = next;
    }
    pq->head = pq->tail = NULL;
    pq->size = 0;
}

// 入队
void QueuePush(Queue* pq, QDatatype x) {
    QNode* newnode = (QNode*)malloc(sizeof(QNode));
    if (newnode == NULL) {
        perror("malloc fail");
        return;
    }
    newnode->data = x;
    newnode->next = NULL;
    
    if (pq->head == NULL) {
        assert(pq->tail == NULL);
        pq->head = pq->tail = newnode;
    } else {
        pq->tail->next = newnode;
        pq->tail = newnode;
    }
    pq->size++;
}

// 出队
void QueuePop(Queue* pq) {
    assert(pq);
    assert(pq->head != NULL);
    if (pq->head->next == NULL) {
        free(pq->head);
        pq->head = pq->tail = NULL;
    } else {
        QNode* next = pq->head->next;
        free(pq->head);
        pq->head = next;
    }
    pq->size--;
}

// 获取大小
int QueueSize(Queue* pq) {
    assert(pq);
    return pq->size;
}

// 判空
bool QueueEmpty(Queue* pq) {
    assert(pq);
    return pq->size == 0;
}

// 获取队头
QDatatype QueueFront(Queue* pq) {
    assert(pq);
    assert(!QueueEmpty(pq));
    return pq->head->data;
}

// 获取队尾
QDatatype QueueBack(Queue* pq) {
    assert(pq);
    assert(!QueueEmpty(pq));
    return pq->tail->data;
}