数据结构中的栈与队列：原理、实现与应用

前言：栈和队列是计算机科学中两种最基础的线性数据结构，它们的独特操作规则和广泛的应用场景使其成为每一位开发者必须掌握的核心知识。本文将通过生活案例、代码实现和实际应用场景，带您深入理解这两种数据结构的精髓。

1.栈（Stack）

基本定义

栈是一种受限的线性表，仅允许在同一端（栈顶）进行数据插入（push）和删除（pop）操作。其核心特性遵循LIFO(后进先出)（Last In First Out）原则，即后进入的元素优先被访问。

LIFO原则

• 后进先出（Last In First Out）：最后入栈的元素总是最先出栈

• 入栈（Push）：将新元素放入栈顶

• 出栈（Pop）：移除并返回栈顶元素

核心机制

• 单端操作：所有操作集中在栈顶完成

• 动态指针：通过栈顶指针（top）实时跟踪最新元素位置

• 操作限制：禁止直接访问中间元素，必须按序操作

• 空间管理：顺序栈需预判容量，链式栈动态扩展但需额外指针空间

2.栈的实现

本文将以动态数组为基础，手把手带你用C语言实现一个智能的“自动扩容栈”。

/* 栈元素类型定义（方便修改数据类型） */
typedef int STDataType;

/* 栈结构体定义
   arr: 动态数组首地址
   top: 栈顶指针（当前元素数量）
   capacity: 数组总容量 */
typedef struct Stack {
    STDataType* arr;
    int top;        
    int capacity;   
} ST;

/* 功能：初始化栈结构
   参数：ps - 指向栈的指针
   关键点：初始状态数组为空，容量为0 */
void STInit(ST* ps) {
    assert(ps);
    ps->arr = NULL;
    ps->capacity = ps->top = 0;
}

/* 功能：压入元素到栈顶
   参数：ps - 栈指针，x - 要入栈的元素
   关键点：自动扩容策略（4→8→16...）
   示例：初始容量0时首次push会扩容到4 */
void STPush(ST* ps, STDataType x) {
    assert(ps);
    // 容量检查与扩容
    if (ps->capacity == ps->top) {
        int newcapacity = ps->capacity ? 2*ps->capacity : 4;
        STDataType* temp = realloc(ps->arr, newcapacity*sizeof(STDataType));
        if (!temp) { perror("malloc"); exit(1); }
        ps->arr = temp;
        ps->capacity = newcapacity;
    }
    ps->arr[ps->top++] = x; // 先存数据再移动指针
}

/* 功能：判断栈是否为空
   参数：ps - 栈指针
   返回：true表示空栈，false非空
   示例：初始化后返回true，push后返回false */
bool STEmpty(ST* ps) {
    assert(ps);
    return ps->top == 0;
}

/* 功能：弹出栈顶元素
   参数：ps - 栈指针
   关键点：实际只移动指针，不删除数据
   注意：空栈弹出会导致断言失败 */
void STPop(ST* ps) {
    assert(ps && !STEmpty(ps));
    ps->top--; // 逻辑删除
}

/* 功能：获取栈元素数量
   参数：ps - 栈指针
   返回：当前元素个数
   示例：push三次后返回3 */
int STSize(ST* ps) {
    assert(ps);
    return ps->top; // top直接表示数量
}

/* 功能：查看栈顶元素（不弹出）
   参数：ps - 栈指针
   返回：栈顶元素值
   关键点：top-1才是最后存入的位置
   示例：栈内[10,20]时返回20 */
STDataType STTop(ST* ps) {
    assert(ps && !STEmpty(ps));
    return ps->arr[ps->top-1];
}

/* 功能：销毁栈并释放内存
   参数：ps - 栈指针
   关键点：必须调用防止内存泄漏
   注意：调用后栈不可再使用 */
void STDestroy(ST* ps) {
    assert(ps);
    if (ps->arr) free(ps->arr);
    ps->arr = NULL;
    ps->capacity = ps->top = 0;
}

测试用例 

int main()
{
	ST st;          // 声明栈变量（未初始化状态）
	STInit(&st);    // 初始化栈 → arr=NULL, capacity=0, top=0

	STPush(&st, 1);  // 触发扩容（0→4）→ arr[0]=1, top=1
	printf("%d\n", STSize(&st)); // 输出1（当前元素数量）

	STPush(&st, 2);  // arr[1]=2, top=2
	printf("%d\n", STSize(&st)); // 输出2

	STPush(&st, 3);  // arr[2]=3, top=3
	printf("%d\n", STSize(&st)); // 输出3

	STPush(&st, 4);  // arr[3]=4, top=4（栈满）
	printf("%d\n", STSize(&st)); // 输出4

	while (!STEmpty(&st)) //打印栈中所有元素
	{          
		printf("%d ", STTop(&st));  // 从栈顶开始输出：4 3 2 1
		STPop(&st);           // 每次循环top减1
	}
	printf("\n%d", STSize(&st)); // 输出0（此时栈空）

	STDestroy(&st);          // 必须调用！释放动态内存
    return 0;
}

3.队列（Queue）

基本定义

队列是另一种受限线性表，遵循FIFO（First In First Out）原则。元素从队尾（rear）插入（enqueue），从队首（front）移除，保持严格的先进先出顺序。

核心机制

• 双指针系统：通过 front 和 rear 指针分别管理两端

• 循环优化：使用模运算实现环形缓冲区解决"假溢出"问题

• 等待特性：元素按到达顺序被处理，具有公平性特征

• 容量管理：动态队列可扩展，但需考虑内存碎片问题

4.队列的实现

在本文中，会着重介绍下面三种队列，普通数组队列的使用并不常见，我们在这里并不过多介绍，大家可以自己尝试着实现。首先，我们实现链式队列。循环数组队列和动态数组队列我们作为后面习题补充会涉及到。

注意：链式队列的实现与单链表的实现大差不差，前面单链表的实现非常重要，能够完成单链表的实现代码，实现链式队列代码就不成问题。

typedef int QDataType;  // 队列元素类型别名，方便修改存储类型

// 队列节点结构（链式存储）
typedef struct QueueNode {
    int val;              // 存储数据
    struct QueueNode* next; // 指向下一个节点
} QNode;

// 队列管理结构
typedef struct Queue {
    QNode* phead;  // 队头指针（删除端）
    QNode* ptail;  // 队尾指针（插入端）
    int size;       // 当前元素数量
} Queue;


// 功能：初始化队列结构
// 参数：pq - 指向队列的指针
// 关键点：将指针置空，size清零
void QueueInit(Queue* pq) {
    assert(pq);  // 防御性编程，确保指针有效
    pq->phead = pq->ptail = NULL;
    pq->size = 0;  // 初始为空队列
}


// 功能：创建新节点
// 参数：x - 要存储的数据
// 返回：新节点指针
// 关键点：内存分配与初始化
QNode* Createnode(QDataType x) {
    QNode* newnode = (QNode*)malloc(sizeof(QNode));
    if (newnode == NULL) {          // 内存不足处理
        perror("malloc");           // 打印错误信息
        exit(1);                    // 直接终止程序
    }
    newnode->val = x;               // 存储数据
    newnode->next = NULL;           // 初始化指针
    return newnode;
}


// 功能：在队尾插入新元素
// 参数：pq - 队列指针，x - 要插入的数据
// 关键点：维护头尾指针关系
void QueuePush(Queue* pq, QDataType x) {
    assert(pq);
    QNode* newnode = Createnode(x);  // 创建新节点
    
    if (pq->phead == NULL) {        // 空队列情况
        pq->phead = pq->ptail = newnode;
    } else {                        // 非空队列
        pq->ptail->next = newnode;  // 链接新节点
        pq->ptail = newnode;        // 更新尾指针
    }
    pq->size++;  // 元素计数增加
}


// 功能：判断队列是否为空
// 参数：pq - 队列指针
// 返回：true为空，false非空
// 关键点：只需检查头指针
bool QueueEmpty(Queue* pq) {
    assert(pq);
    return pq->phead == NULL;  // 头指针为空即队列空
}


// 功能：删除队头元素
// 参数：pq - 队列指针
// 关键点：处理最后一个节点的特殊情况
void QueuePop(Queue* pq) {
    assert(pq);
    assert(!QueueEmpty(pq));  // 确保队列非空

    QNode* del = pq->phead;     // 保存待删除节点
    pq->phead = pq->phead->next;// 头指针后移
    
    // 处理删除最后一个元素的情况
    if (pq->phead == NULL) {
        pq->ptail = NULL;      // 尾指针也必须置空
    }
    
    free(del);      // 释放节点内存
    pq->size--;     // 元素计数减少
}


// 功能：查看队头元素（不删除）
// 参数：pq - 队列指针
// 返回：队头元素值
// 注意：队列为空时触发断言
QDataType QueueFront(Queue* pq) {
    assert(pq);
    assert(!QueueEmpty(pq));  // 防御空队列访问
    return pq->phead->val;    // 直接返回头节点值
}


// 功能：查看队尾元素（不删除）
// 参数：pq - 队列指针
// 返回：队尾元素值
QDataType QueueBack(Queue* pq) {
    assert(pq);
    assert(!QueueEmpty(pq));  // 防御空队列访问
    return pq->ptail->val;    // 直接返回尾节点值
}


// 功能：获取当前元素数量
// 参数：pq - 队列指针
// 返回：队列元素个数
// 优势：O(1)时间复杂度
int QueueSize(Queue* pq) {
    assert(pq);
    return pq->size;  // 直接返回计数器值
}



// 功能：释放队列所有内存
// 参数：pq - 队列指针
// 关键点：必须遍历释放所有节点
void QueueDestroy(Queue* pq) {
    assert(pq);
    QNode* curr = pq->phead;
    while (curr) {
        QNode* del = curr;   // 保存当前节点
        curr = curr->next;   // 移动到下一个节点
        free(del);           // 释放当前节点
    }
    pq->phead = pq->ptail = NULL;  // 重置指针
    pq->size = 0;                  // 重置计数器
}

测试用例

int main() {
    Queue q;
    QueueInit(&q);  // 必须初始化
    
    QueuePush(&q, 10);
    QueuePush(&q, 20);
    printf("队头：%d\n", QueueFront(&q));  // 输出10
    
    QueuePop(&q);  // 删除10
    printf("当前大小：%d\n", QueueSize(&q));  // 输出1
    
    QueueDestroy(&q);  // 必须销毁
    return 0;
}

 5.栈与队列算法题

5.1 力扣：有效的括号

 1. 核心思想

• 栈的LIFO特性：利用栈后进先出的特性，确保最近打开的括号必须最先闭合

• 匹配原则：遍历字符串时，遇到左括号入栈，遇到右括号必须与栈顶左括号类型匹配

2. 执行流程

1. 初始化栈：创建空栈用于存储待匹配的左括号

2. 遍历字符：逐个处理输入字符串的每个字符

   • 左括号处理：(/[/{ → 压入栈顶

   • 右括号处理：

     • 检查栈空 → 栈空直接返回false

     • 栈非空 → 检查栈顶是否匹配 → 匹配则弹出，不匹配返回false

3. 最终校验：遍历完成后检查栈是否为空（所有左括号均已匹配）

//代码中所用函数都是上文栈的实现中的函数
bool isValid(char* s) {
    ST st;
    STInit(&st);
    while(*s != '\0')
    {
        if(*s == '(' || *s == '[' || *s == '{')
        {
            STPush(&st,*s);
        }
        else
        {
            if(STEmpty(&st))
                return false;
            STDataType ch1 = STTop(&st);
            if((ch1 == '(' && *s == ')')
            || (ch1 == '[' && *s == ']')
            || (ch1 == '{' && *s == '}'))
                STPop(&st);
            else
            {
                STDestroy(&st);
                return false;
            }
        }
        s++;
    }
    if(!STEmpty(&st))
        return false;
    STDestroy(&st);
    return true;
}

5.2力扣：用队列实现栈 

// 代码中所用函数都是上文队列的实现中的函数

// 使用两个队列实现栈的结构定义
typedef struct {
    Queue q1;
    Queue q2;
} MyStack;

// 创建栈实例并初始化两个队列
MyStack* myStackCreate() 
{
    MyStack* pst = (MyStack*)malloc(sizeof(MyStack));
    QueueInit(&pst->q1);
    QueueInit(&pst->q2);
    return pst;
}

// 入栈操作：将元素压入非空队列（若都为空则选择q1）
void myStackPush(MyStack* obj, int x) {
    if(!QueueEmpty(&obj->q1))
        QueuePush(&obj->q1, x);
    else
        QueuePush(&obj->q2, x);
}

// 出栈操作：将非空队列的前n-1个元素转移到空队列，弹出最后一个元素
int myStackPop(MyStack* obj) {
    Queue* emptyQue = &obj->q1;
    Queue* nonEmptyQue = &obj->q2;
    // 确定空队列和非空队列
    if(QueueEmpty(nonEmptyQue)) {
        emptyQue = &obj->q2;
        nonEmptyQue = &obj->q1;
    }
    // 将非空队列的前n-1个元素转移到空队列
    while(QueueSize(nonEmptyQue) > 1) {
        QDataType data = QueueFront(nonEmptyQue);
        QueuePop(nonEmptyQue);
        QueuePush(emptyQue, data);
    }
    // 弹出并返回最后一个元素
    QDataType ret = QueueFront(nonEmptyQue);
    QueuePop(nonEmptyQue);
    return ret;
}

// 获取栈顶元素：直接返回非空队列的队尾元素
int myStackTop(MyStack* obj) {
    if(!QueueEmpty(&obj->q1))
        return QueueBack(&obj->q1);
    else
        return QueueBack(&obj->q2);
}

// 判断栈是否为空：当两个队列都为空时栈为空
bool myStackEmpty(MyStack* obj) {
    return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}

// 释放栈内存：销毁两个队列并释放栈结构
void myStackFree(MyStack* obj) {
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
    free(obj);
    obj = NULL;
}

 5.3力扣：用栈实现队列

// 代码中所用函数都是上文栈的实现中的函数

// 使用两个栈实现队列的结构定义
typedef struct {
    ST Pushst;    // 用于入队操作的栈
    ST Popst;     // 用于出队操作的栈
} MyQueue;

// 创建队列实例并初始化两个栈
MyQueue* myQueueCreate() {
    MyQueue* pst = (MyQueue*)malloc(sizeof(MyQueue));
    STInit(&pst->Pushst);
    STInit(&pst->Popst);
    return pst;
}

// 入队操作：直接压入Push栈
void myQueuePush(MyQueue* obj, int x) {
    STPush(&obj->Pushst, x);
}

// 出队操作：若Pop栈为空，则将Push栈元素全部倒入Pop栈，再弹出Pop栈顶元素
int myQueuePop(MyQueue* obj) {
    if(STEmpty(&obj->Popst)) {
        // 将Push栈的元素逆序倒入Pop栈
        while(!STEmpty(&obj->Pushst)) {
            STDataType data = STTop(&obj->Pushst);
            STPop(&obj->Pushst);
            STPush(&obj->Popst, data);
        }
    }
    STDataType ret = STTop(&obj->Popst);
    STPop(&obj->Popst);
    return ret;
}

// 获取队首元素：逻辑同出队，但不弹出元素
int myQueuePeek(MyQueue* obj) {
    if(STEmpty(&obj->Popst)) {
        while(!STEmpty(&obj->Pushst)) {
            STDataType data = STTop(&obj->Pushst);
            STPop(&obj->Pushst);
            STPush(&obj->Popst, data);
        }
    }
    return STTop(&obj->Popst);
}

// 判断队列是否为空：当两个栈都为空时队列为空
bool myQueueEmpty(MyQueue* obj) {
    return STEmpty(&obj->Popst) && STEmpty(&obj->Pushst);
}

// 释放队列内存：销毁两个栈并释放队列结构
void myQueueFree(MyQueue* obj) {
    STDestroy(&obj->Popst);
    STDestroy(&obj->Pushst);
    free(obj);
    obj = NULL;
}

 5.4力扣：设计循环队列

// 使用数组实现的环形队列结构
typedef struct {
    int* arr;        // 存储队列元素的数组
    int front;       // 队头指针：指向队列第一个有效元素
    int rear;        // 队尾指针：指向队列最后一个元素的下一个位置
    int capacity;    // 队列的最大容量（实际存储元素个数为capacity）
} MyCircularQueue;

// 创建环形队列实例，k为队列容量
MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    // 分配k+1大小的数组，浪费一个空间用于区分队列满和空的状态
    obj->arr = (int*)malloc(sizeof(int) * (k + 1));
    obj->front = obj->rear = 0;    // 初始化队头队尾指针
    obj->capacity = k;             // 设置队列容量
    return obj;
}

// 判断队列是否为空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    // 当队头和队尾指针指向同一位置时，队列为空
    return obj->rear == obj->front;
}

// 判断队列是否已满
bool myCircularQueueIsFull(MyCircularQueue* obj) {
    // 当队尾指针的下一个位置是队头指针时，队列已满
    // 使用取模运算实现环形效果
    return (obj->rear + 1) % (obj->capacity + 1) == obj->front;
}

// 入队操作
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if (myCircularQueueIsFull(obj))
        return false;    // 队列已满，入队失败
    
    obj->arr[obj->rear] = value;    // 将元素放入队尾位置
    obj->rear = (obj->rear + 1) % (obj->capacity + 1);    // 更新队尾指针，循环前进
    return true;
}

// 出队操作
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj))
        return false;    // 队列为空，出队失败
    
    obj->front = (obj->front + 1) % (obj->capacity + 1);    // 更新队头指针，循环前进
    return true;
}

// 获取队头元素
int myCircularQueueFront(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj))
        return -1;    // 队列为空，返回-1表示无效值
    
    return obj->arr[obj->front];    // 返回队头指针指向的元素
}

// 获取队尾元素
int myCircularQueueRear(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj))
        return -1;    // 队列为空，返回-1表示无效值
    
    // 计算队尾元素的实际位置（队尾指针前一个位置）
    int prev = (obj->rear - 1 + (obj->capacity + 1)) % (obj->capacity + 1);
    return obj->arr[prev];
}

// 释放队列内存
void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->arr);    // 释放存储元素的数组
    free(obj);         // 释放队列结构体
    obj = NULL;        // 防止野指针
}

1. 数组大小：

   • 实际分配大小为 capacity + 1，浪费一个空间用于区分队列满和队列空的状态
   • 队列满条件：(rear + 1) % (capacity + 1) == front
   • 队列空条件：rear == front

2. 指针移动：

   • 队头指针front：指向队列的第一个有效元素
   • 队尾指针rear：指向队列最后一个元素的下一个位置
   • 使用% (capacity + 1)实现环形效果

3. 边界处理：

   • 入队时直接在rear位置赋值，然后rear指针后移
   • 出队时直接将front指针后移，无需真正删除元素
   • 获取队尾元素时需要计算rear的前一个位置，处理rear为 0 的情况

5.5设计动态循环列表

#include <stdlib.h>
#include <assert.h>

typedef struct {
    int* data;       // 存储队列元素的动态数组
    int front;       // 队头指针，指向队列第一个元素
    int rear;        // 队尾指针，指向队列最后一个元素的下一个位置
    int capacity;    // 当前队列容量
    int size;        // 当前队列元素个数
} DynamicQueue;

// 创建动态队列，初始容量为initialCapacity
DynamicQueue* createQueue(int initialCapacity) {
    DynamicQueue* queue = (DynamicQueue*)malloc(sizeof(DynamicQueue));
    assert(queue != NULL);
    
    queue->data = (int*)malloc(sizeof(int) * initialCapacity);
    assert(queue->data != NULL);
    
    queue->front = 0;
    queue->rear = 0;
    queue->size = 0;
    queue->capacity = initialCapacity;
    
    return queue;
}

// 判断队列是否为空
bool isEmpty(DynamicQueue* queue) {
    return queue->size == 0;
}

// 判断队列是否已满（实际不会满，会自动扩容）
bool isFull(DynamicQueue* queue) {
    return queue->size == queue->capacity;
}

// 扩容队列，新容量为原容量的2倍
void resizeQueue(DynamicQueue* queue) {
    int newCapacity = queue->capacity * 2;
    int* newData = (int*)malloc(sizeof(int) * newCapacity);
    assert(newData != NULL);
    
    // 复制原队列元素到新数组
    for (int i = 0; i < queue->size; i++) {
        newData[i] = queue->data[(queue->front + i) % queue->capacity];
    }
    
    free(queue->data);
    queue->data = newData;
    queue->front = 0;
    queue->rear = queue->size;
    queue->capacity = newCapacity;
}

// 入队操作
void enqueue(DynamicQueue* queue, int value) {
    if (isFull(queue)) {
        resizeQueue(queue);
    }
    
    queue->data[queue->rear] = value;
    queue->rear = (queue->rear + 1) % queue->capacity;
    queue->size++;
}

// 出队操作，返回队头元素
int dequeue(DynamicQueue* queue) {
    assert(!isEmpty(queue));
    
    int value = queue->data[queue->front];
    queue->front = (queue->front + 1) % queue->capacity;
    queue->size--;
    
    return value;
}

// 获取队头元素
int getFront(DynamicQueue* queue) {
    assert(!isEmpty(queue));
    return queue->data[queue->front];
}

// 获取队列大小
int getSize(DynamicQueue* queue) {
    return queue->size;
}

// 释放队列内存
void freeQueue(DynamicQueue* queue) {
    free(queue->data);
    free(queue);
}