《重生之霸道总裁爱上学数据结构的我（三）》之没人比我更懂栈和队列

Ne0inhk

— 12 min read
《重生之霸道总裁爱上学数据结构的我（三）》之没人比我更懂栈和队列

个人主页-爱因斯晨

文章专栏-霸道总裁爱上学数据结构的我

在这里插入图片描述

一、前言

我们在前两篇文章中讲到顺序表和链表其都是线性结构，我们今天讲的栈和队列也是特殊的线性表。顺序表和链表没有所谓的进出限制，但是我们今天要讲的栈就不一样，他有特殊的进栈和出栈顺序，只允许在一端进行插入和删除。也就是说后进先出，先进后出。但是队列呢，只允许从前面插入，后面出。也就是他俩是特殊的线性结构，所以在基本操作上和前文的线性表和链表有一定相似之处。

二、栈

在这里插入图片描述

只允许在一端进行插入和删除操作的线性表

空栈，没有元素。

栈顶允许插入和删除，栈底不允许。

2.1顺序栈

就是用顺序方式存储的栈就是顺序栈。

在这里插入图片描述

顺序栈的定义

这里用top指针来标记栈顶位置，初始化时top = -1，表示栈是空的。就像刚买的空盘子架，还没放任何盘子。

#defineMAXSIZE100//栈的最大容量#include<stdio.h>#include<stdlib.h>#include<stdbool.h>typedefstruct{//顺序栈的结构体int data[100];//栈的数组int top;//栈顶指针}SqStack;//顺序栈的类型定义

初始化

//初始化操作voidInitStack(SqStack *S){ S->top =-1;//将栈顶指针设为-1}//判断栈是否为空 bool StackEmpty(SqStack *S){if(S->top ==-1){return true;//栈为空}else{return false;//栈不为空}}

进栈操作

进栈就像往盘子架上放新盘子，只能放在最上面：

//进栈操作 bool Push(SqStack *S,int x){if(S->top == MAXSIZE){return false;//栈满} S->top++;//栈顶指针加1 S->data[S->top]= x;//将x入栈return true;//入栈成功}

先检查栈是不是满了（top等于最大容量），没满的话就把top往上挪一位，再把数据放进去。

出栈操作

出栈则是从最上面拿走一个盘子：

//出栈操作 bool Pop(SqStack *S,int*x){if(S->top ==-1){return false;//栈为空}*x = S->data[S->top];//将栈顶元素出栈 S->top--;//栈顶指针减1return true;//出栈成功}

先检查栈是不是空的，不空的话就把栈顶元素取出来，再把top往下挪一位。

获取栈顶元素

有时候我们只想看看最上面的盘子是啥样，不想拿走它：

//获取栈顶元素 bool GetTop(SqStack *S,int*x){if(S->top ==-1){return false;//栈为空}*x = S->data[S->top];//将栈顶元素赋值给xreturn true;//获取成功}

这个操作和出栈的区别是，top指针不会移动，只是 “偷看” 一眼。

2.2共享栈

共享栈是个节省空间的小能手，它让两个栈共享同一块数组空间，栈底分别在数组的两端，向中间生长。就像两个霸道总裁共用一个衣帽间，一人占一边，谁也不打扰谁。

在这里插入图片描述

建立

//共享栈建立typedefstruct{//共享栈的结构体int data[100];//栈的数组int top;//栈顶指针int top1;//栈底指针}SharedStack;//共享栈的类型定义

初始化

初始化时，第一个栈的top在 - 1，第二个栈的top1在最大容量处：

//初始化voidInitSharedStack(SharedStack *S){ S->top =-1;//将栈顶指针设为-1 S->top1 = MAXSIZE;//将栈顶指针设为最大容量}

这样两个栈就可以向中间扩展，直到top + 1 == top1时，表示栈满。

2.3链栈

链栈就是用链表实现的栈，链表的头结点作为栈顶，这样进栈和出栈操作都能在 O (1) 时间内完成，比顺序栈更灵活（不用提前规定大小）。

建立

//链栈建立typedefstruct{int data[100];int top;//栈顶指针structLinkNode*next;//指向下一个节点的指针}LinkStack;//链栈的类型定义

这里栈顶指针就是链表的头指针，进栈就是在头结点前插入新节点，出栈就是删除头结点。

三、队列

在这里插入图片描述

队列和栈正好相反，它是 “先进先出”（FIFO，First In First Out）的，就像排队买奶茶 —— 先到的人先拿到奶茶。只能在队尾插入（入队），在队头删除（出队）。

顺序队列用数组实现，但有个小问题：如果单纯地让front指向队头，rear指向队尾，随着入队和出队操作，front和rear都会往后移动，可能导致数组前面的空间浪费。

定义

初始化时，front和rear都指向 0：

//队列定义typedefstruct{int data[100];//队列的数组int front;//队头指针int rear;//队尾指针}SqQueue;//链队列的类型定义

初始化队列

//初始化队列 void InitQueue(SqQueue *Q) { Q->front = Q->rear = 0; //将队头指针和队尾指针设为0 }

判断队列是否为空

//判断队列是否为空 bool QueueEmpty(SqQueue *Q){if(Q->front == Q->rear){return true;//队列为空}else{return false;//队列不为空}}

入队操作

//入队操作 bool EnQueue(SqQueue *Q,int x){if(Q->rear == MAXSIZE){return false;//队列满} Q->data[Q->rear]= x;//将x入队 Q->rear++;//队尾指针加1return true;//入队成功}

把数据放在rear指向的位置，再把rear往后挪一位。

出队操作

//出队操作 bool DeQueue(SqQueue *Q,int*x){if(Q->front == Q->rear){return false;//队列为空}*x = Q->data[Q->front];//将队头元素赋值给x Q->front++;//队头指针加1return true;//出队成功}

取出front指向的元素，再把front往后挪一位。

判断队列的满和空

法一：

上面的方法有个缺陷：rear到达数组末尾时，即使前面有空位，也会被判为队满。解决这个问题有几种方法：

//判断队列是否为空 bool GetHead(SqQueue Q,int*x){if(Q.rear==Q.front)//队列为空return false;*x=Q.data[Q.front];//将队头元素赋值给xreturn true;}

法二：定义长度问题

增加一个size变量记录队列长度，队满条件是size == MaxSize，队空条件是size == 0。

#defineMaxSize10typedefstruct{int data[10];int front,rear;int size;//队列当前长度}SqQueue;//插入成功：size++ 删除成功size--//初始化时：rear=front=0,size=0//队满条件：size==MaxSize //队空条件：size==0

法三：

增加一个tag变量，记录最近操作是插入（1）还是删除（0）。队满条件是front == rear && tag == 1，队空条件是front == rear && tag == 0。

#defineMaxSize10typedefstruct{int data[10];int front,rear;int tag;//最近进行的是删除/插入 初始化时，rear=front=0;tag=0}SqQueue;

每次删除操作成功时，都令tag=0

每次插入操作成功时，都令tag=1

只有删除操作，才可能导致队空，只有插入操作，才可能导致队满

队满条件：frontrear&&tag1

队空条件：frontrear&&tag0

链式存储实现队列

链式队列用链表实现，队头指针指向头结点，队尾指针指向最后一个节点，这样入队和出队操作都很方便。

定义一个链式队列

//链队列的节点类型定义typedefstructLinkNode{int data;//数据域structLinkNode*next;//指向下一个节点的指针}LinkNode;//链队列的节点类型定义typedefstruct{ LinkNode *front ,*rear;//队头指针和队尾指针}LinkQueue;//链队列的类型定义

初始化（带头结点）

头结点不存数据，只是为了操作方便。

//初始化链队列voidInitoQueue(LinkQueue *Q){//初始时队头指针和队尾指针都指向头结点 Q->front = Q->rear =(LinkNode *)malloc(sizeof(LinkNode)); Q->front->next =NULL;//头结点的next指针设为NULL}//判断队列是否为空 bool QueueoEmpty(LinkQueue *Q){if(Q->front == Q->rear){return true;//队列为空}else{return false;//队列不为空}}

初始化队列不带头结点

//判断队列是否为空 bool QueueoEmpty(LinkQueue *Q) { if (Q->front == Q->rear) { return true; //队列为空 } else { return false; //队列不为空 } }

入队（带头结点）

入队就是在队尾添加新节点，然后把rear移到新节点。

//入队操作（带头结点） bool EnQueueo(LinkQueue *Q,int x){//创建一个新节点 LinkNode *s =(LinkNode *)malloc(sizeof(LinkNode));if(s ==NULL){return false;//内存分配失败} s->data = x;//将x赋值给新节点的数据域 s->next =NULL;//将新节点的next指针设为NULL Q->rear->next = s;//将原队尾节点的next指针指向新节点 Q->rear = s;//将队尾指针指向新节点return true;//入队成功}

入队（不带头结点）

//入队操作（不带头结点） bool EnQueueo(LinkQueue *Q,int x){//创建一个新节点 LinkNode *s =(LinkNode *)malloc(sizeof(LinkNode));if(s ==NULL){return false;//内存分配失败} s->data = x;//将x赋值给新节点的数据域 s->next =NULL;//将新节点的next指针设为NULL//若队列为空（首次入队），队头和队尾都指向新节点if(QueueoEmpty(Q)){ Q->front = s; Q->rear = s;}else{//队列非空时，队尾节点的next指向新节点，再移动队尾指针 Q->rear->next = s; Q->rear = s;}return true;//入队成功}

不带头结点的链式队列入队操作，核心区别在于需要处理 “首次入队” 的特殊情况：

  • 当队列是空的时候（front和rear都为NULL），新节点既是队头也是队尾，所以front和rear要同时指向这个新节点
  • 非空队列时，操作和带头结点类似：让当前队尾的next指向新节点，再把rear移到新节点上

出队（带头结点）

// 出队操作（带头结点） bool DeQueueo(LinkQueue *Q,int*x){// 队列为空时无法出队if(QueueoEmpty(Q)){return false;} LinkNode *p = Q->front->next;// p指向队头元素节点*x = p->data;// 保存出队元素的值 Q->front->next = p->next;// 头结点跳过队头元素，指向其后继// 若出队的是最后一个元素，队尾指针需指向头结点（保持空队列状态）if(Q->rear == p){ Q->rear = Q->front;}free(p);// 释放出队节点的内存return true;}
  • 队头元素始终是 front->next 指向的节点（头结点不存储数据）
  • 出队时只需修改头结点的 next 指针，最后一个元素出队时需将 rear 重置为头结点

出队（不带头结点）

// 出队操作（不带头结点） bool DeQueueo(LinkQueue *Q,int*x){// 队列为空时无法出队if(QueueoEmpty(Q)){return false;} LinkNode *p = Q->front;// p指向队头元素节点（不带头结点时front直接指向队头）*x = p->data;// 保存出队元素的值// 若队列只有一个元素，出队后队头队尾均置空if(Q->front == Q->rear){ Q->front = Q->rear =NULL;}else{// 队列有多个元素时，队头指针后移 Q->front = Q->front->next;}free(p);// 释放出队节点的内存return true;}
  • 队头指针 front 直接指向队头元素（首个数据节点）
  • 出队时需直接移动 front 指针，最后一个元素出队后需将 front 和 rear 均置为 NULL

队列满的条件

顺序存储，预分配的空间耗尽时队满

链式存储，一般不会队满，除非内存不足

四、总结：

栈和队列都是特殊的线性表，只是对操作的位置做了限制：

  • 栈：只允许在栈顶操作，后进先出
  • 队列：只允许在队尾入队、队头出队，先进先出

它们的实现可以用数组（顺序存储）或链表（链式存储），各有优缺点：

  • 顺序存储：访问快，但大小固定（或需要扩容）
  • 链式存储：大小灵活，但访问需要遍历指针

就像霸道总裁的两种处事风格：栈是 “后来者居上”，队列是 “按规矩办事”，各有各的适用场景。掌握它们的逻辑和实现，对于理解更复杂的数据结构至关重要。

Read more

基于腾讯云HAI + DeepSeek快速设计自己的个人网页

基于腾讯云HAI + DeepSeek快速设计自己的个人网页

前言：通过结合腾讯云HAI 强大的云端运算能力与DeepSeek先进的 AI技术，本文介绍高效、便捷且低成本的设计一个自己的个人网页。你将了解到如何轻松绕过常见的技术阻碍，在腾讯云HAI平台上快速部署DeepSeek模型，仅需简单几步，就能获取一个包含个人简介、技能特长、项目经历及联系方式等核心板块的响应式网页。 目录 一、DeepSeek模型部署在腾讯云HAI 二、设计个人网页 一、DeepSeek模型部署在腾讯云HAI 把 DeepSeek 模型部署于腾讯云 HAI，用户便能避开官网访问限制，直接依托腾讯云 HAI 的超强算力运行 DeepSeek-R1 等模型。这一举措不仅降低了技术门槛，还缩短了部署时间，削减了成本。尤为关键的是，凭借 HAI 平台灵活且可扩展的特性，用户能够依据自身特定需求定制专属解决方案，进而更出色地适配特定业务场景，满足各类技术要求 。 点击访问腾讯云HAI控制台地址： 算力管理 - 高性能应用服务 - 控制台 腾讯云高性能应用服务HAI已支持DeepSeek-R1模型预装环境和CPU算力，只需简单的几步就能调用DeepSeek - R1

By Ne0inhk
AI革命先锋：DeepSeek与蓝耘通义万相2.1的无缝融合引领行业智能化变革

AI革命先锋：DeepSeek与蓝耘通义万相2.1的无缝融合引领行业智能化变革

云边有个稻草人-ZEEKLOG博客 目录 引言 一、什么是DeepSeek？ 1.1 DeepSeek平台概述 1.2 DeepSeek的核心功能与技术 二、蓝耘通义万相2.1概述 2.1 蓝耘科技简介 2.2 蓝耘通义万相2.1的功能与优势 1. 全链条智能化解决方案 2. 强大的数据处理能力 3. 高效的模型训练与优化 4. 自动化推理与部署 5. 行业专用解决方案 三、蓝耘通义万相2.1与DeepSeek的对比分析 3.1 核心区别 3.2 结合使用的优势 四、蓝耘注册流程 五、DeepSeek与蓝耘通义万相2.1的集成应用 5.1 集成应用场景 1. 智能医疗诊断

By Ne0inhk
如何通过 3 个简单步骤在 Windows 上本地运行 DeepSeek

如何通过 3 个简单步骤在 Windows 上本地运行 DeepSeek

它是免费的——社区驱动的人工智能💪。         当 OpenAI 第一次推出定制 GPT 时，我就明白会有越来越多的人为人工智能做出贡献，并且迟早它会完全由社区驱动。         但从来没有想过它会如此接近😂让我们看看如何在 Windows 机器上完全免费使用第一个开源推理模型！  步骤 0：安装 Docker 桌面         我确信很多人已经安装了它，所以可以跳过，但如果没有 — — 这很简单，只需访问Docker 的官方网站，下载并运行安装 👍         如果您需要一些特定的设置，例如使用 WSL，那么有很多指导视频，请查看！我将继续下一步。 步骤 1：安装 CUDA 以获得 GPU 支持         如果您想使用 Nvidia 显卡运行 LLM，则必须安装 CUDA 驱动程序。（嗯……是的，它们需要大量的计算能力）         打开CUDA 下载页面，

By Ne0inhk
在 VSCode 中本地运行 DeepSeek，打造强大的私人 AI

在 VSCode 中本地运行 DeepSeek，打造强大的私人 AI

本文将分步向您展示如何在本地安装和运行 DeepSeek、使用 CodeGPT 对其进行配置以及开始利用 AI 来增强您的软件开发工作流程，所有这些都无需依赖基于云的服务。  步骤 1：在 VSCode 中安装 Ollama 和 CodeGPT         要在本地运行 DeepSeek，我们首先需要安装Ollama，它允许我们在我们的机器上运行 LLM，以及CodeGPT，它是集成这些模型以提供编码辅助的 VSCode 扩展。 安装 Ollama Ollama 是一个轻量级平台，可以轻松运行本地 LLM。 下载Ollama 访问官方网站：https://ollama.com * 下载适合您的操作系统（Windows、macOS 或 Linux）的安装程序。 * 验证安装 安装后，打开终端并运行： ollama --version  如果 Ollama 安装正确，

By Ne0inhk