当前位置： 首页 > java >正文

栈与队列：数据结构中的双生子

java 2025/8/18 5:36:46

请添加图片描述

栈与队列：数据结构中的双生子

✨前言：在数据结构的学习中，栈(Stack) 与 队列(Queue) 是两种基础而强大的存在。它们看似简单，却在各种算法和系统设计中扮演着核心角色。理解它们的特性和实现原理，是每位程序员成长的必经之路。今天我将带大家深入学习栈和队列。
📖专栏：数据结构与算法

目录

  • 栈与队列：数据结构中的双生子
    • 一、栈（Stack）：后进先出的数据世界
      • 1.1 栈的核心概念
      • 1.2 栈的实现方式
    • 二、队列（Queue）：先进先出的公平机制
      • 2.1 队列的核心概念
      • 2.2 队列的实现方式
    • 三、总结

一、栈（Stack）：后进先出的数据世界

1.1 栈的核心概念

栈是一种特殊的线性表，遵循LIFO（Last In First Out）原则，即最后入栈的元素最先出栈。它只允许在固定的一端（称为栈顶）进行插入（压栈）和删除（出栈）操作，另一端称为栈底。

  • 压栈（Push）：向栈顶添加元素

在这里插入图片描述

  • 出栈（Pop）：从栈顶移除元素

在这里插入图片描述

1.2 栈的实现方式

栈可以通过数组或链表实现，数组实现通常更优，因为：

  • 数组在尾部插入/删除的时间复杂度为O(1)
  • 内存连续，缓存命中率高
    在这里插入图片描述

对于栈顶指针一般指向指向栈顶元素的下一个位置解释：

一般来说，栈顶指针可以指向栈顶元素，那这样的话栈为空的情况，top就只能指向-1了，看起来很别扭，所以为了方便起见，直接让栈顶指针指向指向栈顶元素的下一个位置就行。

1. 栈结构定义和初始化

#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;#define INIT_SIZE 4     // 初始容量大小// 初始化栈
void StackInit(Stack* ps) {assert(ps != NULL); // 安全检查ps->a = NULL;       // 初始时数组为空ps->top = 0;        // 栈顶指针初始为0ps->capacity = 0;    // 初始容量为0
}

2. 容量检查函数（内部使用）

// 检查并扩容栈（内部函数）
static void CheckCapacity(Stack* ps) {assert(ps != NULL);// 当栈满时需要扩容if (ps->capacity == ps->top) {// 计算新容量：初始为INIT_SIZE，否则双倍扩容int newCapacity = (ps->capacity == 0) ? INIT_SIZE : ps->capacity * 2;// 重新分配内存STDataType* tmp = (STDataType*)realloc(ps->a, newCapacity * sizeof(STDataType));if (tmp == NULL) {perror("栈扩容失败");exit(EXIT_FAILURE);}ps->a = tmp;ps->capacity = newCapacity;printf("栈已扩容至%d\n", newCapacity); // 调试信息}
}

3. 入栈操作

// 元素入栈
void StackPush(Stack* ps, STDataType data) {assert(ps != NULL); // 安全检查// 检查是否需要扩容CheckCapacity(ps);// 将元素放入栈顶位置ps->a[ps->top] = data;ps->top++; // 栈顶指针上移printf("元素%d入栈成功\n", data); // 调试信息
}

4. 出栈操作

// 元素出栈
void StackPop(Stack* ps) {// 安全检查：栈不能为空assert(ps != NULL && !StackEmpty(ps));printf("元素%d出栈\n", StackTop(ps)); // 调试信息ps->top--; // 栈顶指针下移
}

5. 获取栈顶元素

// 获取栈顶元素
STDataType StackTop(Stack* ps) {// 安全检查：栈不能为空assert(ps != NULL && !StackEmpty(ps));return ps->a[ps->top - 1]; // 返回栈顶元素
}

6. 获取栈大小

// 获取栈中元素数量
int StackSize(Stack* ps) {assert(ps != NULL);return ps->top; // 栈顶指针就是元素数量
}

7. 判断栈是否为空

// 检查栈是否为空
bool StackEmpty(Stack* ps) {assert(ps != NULL);return ps->top == 0; // 栈顶为0表示空栈
}

8. 销毁栈

// 销毁栈
void StackDestroy(Stack* ps) {assert(ps != NULL);free(ps->a);        // 释放动态数组ps->a = NULL;       // 避免野指针ps->top = 0;        // 重置栈顶指针ps->capacity = 0;   // 重置容量printf("栈已销毁\n"); // 调试信息
}

二、队列（Queue）：先进先出的公平机制

2.1 队列的核心概念

队列是另一种特殊的线性表，遵循FIFO（First In First Out）原则，即最先入队的元素最先出队。插入操作在队尾进行，删除操作在队头进行。

  • 入队（Enqueue）：向队尾添加元素
  • 出队（Dequeue）：从队头移除元素

在这里插入图片描述

2.2 队列的实现方式

队列通常使用链表实现更优，因为：

  • 数组实现时，头部删除需要移动元素（O(n)）
  • 链表在头部删除和尾部插入都是O(1)

1. 队列结构定义

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>typedef int QDataType;  // 队列元素类型// 队列节点结构
typedef struct QueueNode {QDataType data;           // 数据域struct QueueNode* next;   // 指向下一个节点
} QNode;// 队列结构
typedef struct Queue {QNode* phead;   // 队头指针QNode* ptail;   // 队尾指针int size;       // 队列元素个数
} Queue;

2. 队列初始化

// 初始化队列 
void QueueInit(Queue* q) {assert(q);  // 确保队列指针有效q->phead = q->ptail = NULL;  // 初始时头尾指针都为空q->size = 0;                 // 初始大小为0
}

3. 入队操作

// 队尾入队列 
void QueuePush(Queue* q, QDataType data) {assert(q);  // 确保队列指针有效// 创建新节点QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL) {perror("malloc fail");exit(1);}newnode->data = data;  // 设置节点数据newnode->next = NULL;  // 新节点next置空// 队列为空时的特殊处理if (q->phead == NULL) {q->phead = q->ptail = newnode;} else {q->ptail->next = newnode;  // 原尾节点指向新节点q->ptail = newnode;        // 更新尾指针}q->size++;  // 队列大小增加
}

4. 出队操作

// 队头出队列 
void QueuePop(Queue* q) {assert(q && q->phead != NULL);  // 确保队列不为空QNode* pop = q->phead;     // 保存要删除的节点q->phead = q->phead->next; // 头指针后移free(pop);                 // 释放原头节点pop = NULL;                // 避免野指针// 如果出队后队列为空，更新尾指针if (q->phead == NULL) {q->ptail = NULL;}q->size--;  // 队列大小减少
}

5. 获取队头元素

// 获取队列头部元素 
QDataType QueueFront(Queue* q) {assert(q && q->phead);  // 确保队列不为空return q->phead->data;  // 返回头节点数据
}

6. 获取队尾元素

// 获取队列队尾元素 
QDataType QueueBack(Queue* q) {assert(q && q->ptail);  // 确保队列不为空return q->ptail->data;  // 返回尾节点数据
}

7. 获取队列大小

// 获取队列中有效元素个数 
int QueueSize(Queue* q) {assert(q);        // 确保队列指针有效return q->size;   // 直接返回size成员
}

8. 检查队列是否为空

// 检测队列是否为空
bool QueueEmpty(Queue* q) {assert(q);             // 确保队列指针有效return q->size == 0;   // size为0表示空队列
}

9. 销毁队列

// 销毁队列 
void QueueDestroy(Queue* q) {assert(q);  // 确保队列指针有效QNode* pcur = q->phead;  // 从头节点开始QNode* next = NULL;      // 保存下一个节点// 遍历释放所有节点while (pcur) {next = pcur->next;  // 保存下一个节点free(pcur);        // 释放当前节点pcur = next;       // 移动到下一个节点}// 重置队列状态q->phead = q->ptail = NULL;q->size = 0;
}

三、总结

栈和队列虽然操作规则截然不同，但它们都是线性数据结构的基础构件。栈的LIFO特性使其成为处理递归和回溯的理想选择，而队列的FIFO特性则完美匹配需要公平处理的场景。理解它们的核心概念和实现细节，能够帮助我们更好地设计算法和解决实际问题。这两种看似简单的数据结构，共同构建了计算机科学中无数复杂系统的基石。

如果本文对您有启发：
✅ 点赞 - 让更多人看到这篇硬核技术解析 ！
✅ 收藏 - 实战代码随时复现
✅ 关注 - 获取数据结构系列深度更新
您的每一个[三连]都是我们持续创作的动力！✨

请添加图片描述

http://www.xdnf.cn/news/18039.html

相关文章：

  • 【P14 3-6 】OpenCV Python——视频加载、摄像头调用、视频基本信息获取（宽、高、帧率、总帧数），视频保存在指定位置
  • 在职老D渗透日记day18:sqli-labs靶场通关（第26关）get报错注入 过滤or和and基础上又过滤了空格和注释符 ‘闭合 手动注入
  • qt vs2019编译QXlsx
  • Linux软件编程(六)(exec 函数族、system 实现、进程回收与线程通信)
  • C++ 内存管理(内存分布 , 管理方式 , new和delete实现原理)
  • pidgen!DecodeProdKey函数分析之iDecodedBytesMax
  • 服务器硬件电路设计之I2C问答（七）：解析 I2C 通信 “卡壳” 难题：从设备无响应与跨电压兼容之道
  • Spring AI Starter和文档解读
  • InfluxDB 数据迁移工具：跨数据库同步方案（一）
  • 超酷炫的Three.js示例
  • Java：File类、递归、字符集、IO流体系及Commons-io框架
  • 【大模型核心技术】Dify 入门教程
  • Flow-GRPO：通过在线 RL 训练 Flow matching 模型
  • PS插件整合包！内置数百款PS插件，支持PS2017-PS2025所有版本！
  • 【学习嵌入式day-26-线程间通信】
  • TypeScript快速入门
  • CPP多线程3：async和future、promise
  • ArrayList的contains问题
  • 机器学习 [白板推导]（十二）[卡曼滤波、粒子滤波]
  • 第G7周：Semi-Supervised GAN 理论与实战
  • 【科研绘图系列】R语言绘制雷达图
  • 洛谷B3865 [GESP202309 二级] 小杨的 X 字矩阵（举一反三）
  • 从 MySQL 5.7 迁移到 8.0：别让 SQL 文件 “坑” 了你
  • 《从入门到高可用：2025最新MySQL 8.0全栈速通指南》
  • Linux配置Dante使用的pam验证
  • 【攻防实战】红队攻防之Goby反杀
  • 力扣（LeetCode) ——622. 设计循环队列（C语言）
  • Android Jetpack | Lifecycle
  • 6JSON格式转python并实现数据可视化
  • 储能领域大数据平台的设计中如何使用 Hadoop、Spark、Flink 等组件实现数据采集、清洗、存储及实时 / 离线计算，支持储能系统分析与预测