数据结构基础详解(C语言): 栈与队列的详解附完整代码

数据结构 栈

栈的核心重点：

栈是只能从表尾插入和删除的数据结构。
栈的顺序存储结构由两部分组成，top指针和数组。
链栈其实本质就是单链表头插法

文章目录

  • 数据结构 栈
  • 1.栈的基本概念
    • 1.1 栈的常用操作
  • 2.栈的存储结构
    • 2.1 栈的顺序存储结构
      • 2.1.1 栈的定义
      • 2.1.2 栈的初始化
      • 2.1.3 入栈
      • 2.1.4 出栈
      • 2.1.5 读取栈顶元素
      • 2.1.6 共享栈
    • 2.2 栈的链式存储结构
      • 2.2.1 链栈的定义
      • 2.2.2 链栈的初始化
      • 2.2.3 入栈
      • 2.2.4 出栈
      • 2.2.5 取栈顶元素
      • 2.2.6 销毁栈
  • 队列
  • 1.队列的定义
  • 1.1 队列的基本操作
  • 2.队列的实现
    • 2.1 顺序存储的实现
      • 2.1.1 队列的定义
      • 2.1.2 队列的初始化
      • 2.1.3 队列判空
      • 2.1.4 入队和出队
      • 2.1.5 取队头元素
      • 2.1.6 判断队列已满/为空的其他两种方案
    • 2.2 链式存储的实现
      • 2.2.1 定义
      • 2.2.2 初始化
      • 2.2.3 判空与判满
      • 2.2.4 入队
      • 2.2.5 出队

1.栈的基本概念

栈( Stack）是只允许在一端进行插入或删除操作的线性表
在这里插入图片描述

1.1 栈的常用操作

  • InitStack(&s):初始化栈,构造一个空栈S,分配内存空间.
  • DestroyStack(&L):销毁栈.销毁并释放S所占用的内存空间
  • Push(&S,x):进栈,若栈S未满,则将x加入使之成为新栈顶
  • Pop(&S,&x):出栈,若栈S非空,则弹出栈顶元素,并用x放回
  • GetTop(S,&x):读栈顶元素.若栈S非空,则用x返回栈顶元素
  • StackEmpty(S):判断一个栈S是否为空.若S为空,则返回true,否则返回false

2.栈的存储结构

2.1 栈的顺序存储结构

2.1.1 栈的定义

#define MaxSize 10
typedef struct{int data[MaxSize]; //静态数组存放栈中元素 int top;           // 栈顶元素 
}SqStack;

2.1.2 栈的初始化

void InitStack(SqStack &S){S.top=-1;   //初始化栈顶指针 
}

2.1.3 入栈

bool Push(SqStack &S,int x)
{if(S.top==MaxSize-1)return false;S.top=S.top+1;S.data[S.top]=x;return true;
}

2.1.4 出栈

bool Pop(SqStack &S,int &x)
{if(S.top==-1)   //栈空,报错 return false;x=S.data[S.top];  //栈顶元素先出栈 S.top=S.top-1; //指针再减1 return true;
}

2.1.5 读取栈顶元素

bool GetTop(SqStack &S,int &x){if(S.top==-1)return false;x=S.data[S.top];return true;
} 

int main()
{	SqStack S;InitStack(S);int x=0;Push(S,2);Push(S,3);Push(S,4);GetTop(S,x);printf("%d",x);
}

上述完整代码如下:

#include <stdio.h>
#include <stdlib.h>#define MaxSize 10
typedef struct{int data[MaxSize]; //静态数组存放栈中元素 int top;           // 栈顶元素 
}SqStack;void InitStack(SqStack &S){S.top=-1;   //初始化栈顶指针 
}bool Push(SqStack &S,int x)
{if(S.top==MaxSize-1)return false;S.top=S.top+1;S.data[S.top]=x;return true;
}bool Pop(SqStack &S,int &x)
{if(S.top==-1)   //栈空,报错 return false;x=S.data[S.top];  //栈顶元素先出栈 S.top=S.top-1; //指针再减1 return true;
}
bool GetTop(SqStack &S,int &x){if(S.top==-1)return false;x=S.data[S.top];return true;
} int main()
{	SqStack S;InitStack(S);int x=0;Push(S,2);Push(S,3);Push(S,4);GetTop(S,x);printf("%d",x);
}

2.1.6 共享栈

两个栈共享同一片空间

#define MaxSize 10
typedef struct{int data[MaxSize]; //静态数组存放栈中元素 int top0;           // 0号栈顶元素int top1;           // 1号栈顶元素
}ShStack;void InitStack(ShStack &S){
s.top0=-1;  //初始化栈顶指针
s.top1=MaxSize;

2.2 栈的链式存储结构

使用不带头结点的链表

2.2.1 链栈的定义

typedef struct LinkNode{int data;//数据域struct LinkNode *next;//指针域 
}stackNode,*LinkStack;

2.2.2 链栈的初始化

void InitStack(LinkStack &s)
{s=NULL;//不需要头节点 
}

2.2.3 入栈

bool Push(LinkStack &S,int e)       
{stackNode *p=(stackNode *)malloc(sizeof(stackNode));p->data=e;p->next=NULL;if(S==NULL){S=p;}else{p->next=S;S=p;}return true;
}

2.2.4 出栈

bool Pop(LinkStack &S,int &e)
{stackNode *p;if(S==NULL)return false;else{p=S;e=p->data;S=S->next;delete p;return true;}
}

2.2.5 取栈顶元素

int top(LinkStack s)
{if(s==NULL)return -1;return s->data;
}

2.2.6 销毁栈

bool DestoryStack(LinkStack &S)
{stackNode *p;while(S){p=S;S=S->next;delete p;}S=NULL;return true;
}

队列

队列的核心:队列是一种先进先出的数据结构。
顺序存储是一个front指针和一个rear指针，和数组
front指针指向队头，rear指针指向队尾。
队空条件：Q.front==Q.rear
进队：Q.data[Q.rear++]
出队：Q.data[Q.front++]

快速图解复习队列:
在这里插入图片描述

在这里插入图片描述

1.队列的定义

队列( Queue）是只允许在一端进行插入，在另一端删除的线性表
在这里插入图片描述

1.1 队列的基本操作

  • InitQueue(&Q):初始化队列，构造一个空队列Q。
  • DestroyQueue(&Q):销毁队列。销毁并释放队列Q所占用的内存空间
  • EnQueue(&Q):入队，若队列Q未满，将x加入，使之成为新的队尾
  • DeQueue(&Q,&x):出队，若队列Q非空，删除队头元素，并用x返回
  • GetHead(Q,&x):读队头元素，若队列Q非空，则将队头元素赋值给x。
  • QueueEmpty(Q):判队列空，若队列Q为空返回true，否则返回false。

2.队列的实现

2.1 顺序存储的实现

在接下来的代码实现中,rear和front指针最初指向相同的位置,在实际的题目中,我们也可以让rear指向data[1],front指向data[0],不必拘泥于某种固定的格式.
在这里插入图片描述

2.1.1 队列的定义

  • 用静态数组存放数据元素
  • 声明一个队头和队尾指针
  • 有typedef,所以定义typedef struct后面没加SqQueue,这个就是一个可写可不写的方式,因为我们取好了别名,也不用struct SqQueue sq1; 这种形式去定义队列
typedef struct{int data[MaxSize];int front,rear;
}SqQueue;

2.1.2 队列的初始化

void InitQueue(SqQueue &Q)
{Q.front=Q.rear=0;
}

2.1.3 队列判空

bool QueueEmpty(SqQueue &Q)
{if(Q.front==Q.rear)return true;return false;
}

2.1.4 入队和出队

入队和出队要注意队列是循环的,出到最后之后,重新找头部从头部开始出队,以此类推
当然了,简单的问题中可能不使用这种循环队列的形式.

在这里插入图片描述
值得思考的是,在入队和出队操作过程中,我们需要进行判断队列是否为空或者队列是否满的,下面先采取放弃一个存储空间的方式,进行判满操作,通过放弃一个存储空间,就不会和判空操作相同,即rear指向最后一个空间没存的情况下就判断它已经满了

⭐️入队

bool EnQueue(SqQueue &Q,int x)
{if((Q.rear+1)%MaxSize==Q.front)return false;Q.data[Q.rear]=x;Q.rear=(Q.rear+1)%MaxSize;return true;
}

⭐️出队

bool DeQueue(SqQueue &Q,int &x)
{if(Q.rear==Q.front)return false;x=Q.data[Q.front];Q.front=(Q.front+1)%MaxSize;return true;
}

当前实现队列元素的个数=(rear+MaxSize-front)%MaxSize

2.1.5 取队头元素

bool GetHead(SqQueue Q,int &x)
{if(Q.rear==Q.front)return false;x=Q.data[Q.front];return true;
}

上述完整代码:

#include <stdio.h>
#include <stdlib.h>
#define  MaxSize 10
typedef struct{int data[MaxSize];int front,rear;
}SqQueue;void InitQueue(SqQueue &Q)
{Q.front=Q.rear=0;
}bool QueueEmpty(SqQueue &Q)
{if(Q.front==Q.rear)return true;return false;
}bool EnQueue(SqQueue &Q,int x)
{if((Q.rear+1)%MaxSize==Q.front)return false;Q.data[Q.rear]=x;Q.rear=(Q.rear+1)%MaxSize;return true;
}bool DeQueue(SqQueue &Q,int &x)
{if(Q.rear==Q.front)return false;x=Q.data[Q.front];Q.front=(Q.front+1)%MaxSize;return true;
}bool GetHead(SqQueue Q,int &x)
{if(Q.rear==Q.front)return false;x=Q.data[Q.front];return true;
}int main()
{SqQueue q;
}

2.1.6 判断队列已满/为空的其他两种方案

之前我们的方案是牺牲一个存储空间
方案一:增加一个size数据,记录队列的当前长度

typedef struct{int data[MaxSize];int front,rear;int size;
}SqQueue;size==MaxSize //队列已满
size==0       //队列为空

方案二:增加一个tag数据,指明最近的依次操作是删除还是插入

typedef struct{int data[MaxSize];int front,rear;int tag;  //tag=1 代表上一次是插入 tag=0代表上一次是删除
}SqQueue;rear==front&&tag=1   //队列已满
rear==front&&tag=0   //队列为空

2.2 链式存储的实现

2.2.1 定义

  • 定义一个结构体是链式队列结点
  • 再定义一个结构体,里面有2个结点指针指向结点,这样便于代码的简洁
typedef struct LinkNode{int data;LinkNode *next;
}LinkNode;typedef struct {LinkNode *front,*rear;
}LinkQueue;

2.2.2 初始化

void InitQueue(LinkQueue &Q)
{Q.front=Q.rear=(LinkNode*)malloc(sizeof(LinkNode));Q.front->next=NULL;
}

2.2.3 判空与判满

判空

bool QueueEmpty(LinkQueue Q)
{if(Q.front==Q.rear)return true;return false;
}

链式存储一般情况不会满,所以不判满

2.2.4 入队

⭐️不带头结点的入队

bool EnQueue(LinkQueue &Q,int x)
{LinkNode *s=(LinkNode*)malloc(sizeof(LinkNode));s->data=x;s->next=NULL;Q.rear->next=s;Q.rear=s;return true;
}

⭐️带头结点的入队第一个元素要特殊处理

bool EnQueue(LinkQueue &Q,int x)
{LinkNode *s=(LinkNode*)malloc(sizeof(LinkNode));s->data=x;s->next=NULL;if(Q.front==NULL){Q.front=s;Q.rear=s;}else{Q.rear->next=s;Q.rear=s;}return true;
}

2.2.5 出队

出队的操作,值得注意的是,如果front指向的是最后一个元素,将他出队后 front指针就指向空了,但是此时的rear指针被蒙在鼓里,所以如果此时p指针和rear指针相同,则说明rear要更新和front指针一样,如果不更新,rear还指向最后一个元素

为什么只有指向最后一个元素的情况下才更新呢?
因为其实,不到最后一个出队,rear和front之间没什么关系,没什么联系

⭐️不带头结点的出队

bool DeQueue(LinkQueue &Q,int &x)  //不带头结点 
{if(Q.front==NULL)return false;LinkNode *p=Q.front; x=p->data;Q.front=p->next;if(Q.rear==p){Q.rear=Q.front; //王道给出的是Q.front==NULL 和 Q.rear==NULL 我觉得没必要,这么写就行 }free(p);return true;
}

⭐️带头结点的出队

bool DeQueue(LinkQueue &Q,int &x)  //带头结点 
{if(Q.rear==Q.front)return false;LinkNode *p=Q.front->next; x=p->data;Q.front->next=p->next;if(Q.rear==p){Q.rear=Q.front;}free(p);return true;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/408947.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

AVL树的旋转

AVL树的旋转

目录 一、AVL树的概念 二、AVL树节点的定义 三、AVL树的插入 四、AVL树的旋转 4.1右单旋 4.2左单旋 4.3左右双旋 4.4右左双旋 五、AVL树的验证 六、AVL树的性能 一、AVL树的概念 二叉搜索树虽可以缩短查找的效率&#xff0c;但如果数据有序或接近有序二叉搜索树将退化…
阅读更多...
【AI绘画】Midjourney提示词详解：精细化技巧与高效实践指南

【AI绘画】Midjourney提示词详解：精细化技巧与高效实践指南

文章目录 &#x1f4af;Midjourney提示词基础结构1 图片链接1.1 上传流程 2 文字描述3 后置参数 &#x1f4af;Midjourney提示词的文字描述结构全面剖析1 主体主体细节描述2 环境背景2.1 环境2.2 光线2.3 色彩2.4 氛围 3 视角4 景别构图5 艺术风格6 图片制作方法7 作品质量万能…
阅读更多...
鸿蒙（API 12 Beta3版）【使用Image完成图片接收器】图片开发指导依赖JS对象

鸿蒙（API 12 Beta3版）【使用Image完成图片接收器】图片开发指导依赖JS对象

图像接收类&#xff0c;用于获取组件surface id&#xff0c;接收最新的图片和读取下一张图片&#xff0c;以及释放ImageReceiver实例。 开发步骤 添加依赖 在进行应用开发之前&#xff0c;开发者需要打开native工程的src/main/cpp/CMakeLists.txt&#xff0c;在target_link_…
阅读更多...
文章中的错字一并替换成正确的字

文章中的错字一并替换成正确的字

with open("文件路径"&#xff0c;"模式"&#xff0c;"编码") as file ("r" 是读&#xff0c;"w"是写) with open(r"D:\python-installer\python-code\pythonProject\src\关于文件操作练习/人物介绍.txt",&quo…
阅读更多...
PHP酒店宾馆民宿预订系统小程序源码

PHP酒店宾馆民宿预订系统小程序源码

酒店宾馆民宿预订系统&#xff1a;一键解锁完美旅行住宿新体验 &#x1f31f; 开篇&#xff1a;告别繁琐&#xff0c;拥抱便捷预订新时代 在这个快节奏的时代&#xff0c;每一次旅行的规划都希望能尽可能高效与省心。想象一下&#xff0c;在规划一场说走就走的旅行时&#xf…
阅读更多...
docker基本环境搭建

docker基本环境搭建

前面在虚拟机centos中搭建的fastdfs和minio分布式文件存储服务都是手动编译安装的&#xff0c;为了方便后续学习&#xff0c;本地开发环境的中间件服务部署&#xff0c;我们将交给docker来部署。下面先进行docker环境搭建。 后续相关教程&#xff08;待更新&#xff09;&#…
阅读更多...
iOS RunLoop

iOS RunLoop

一:什么是Runloop Runloop&#xff0c;正如其名&#xff0c;loop表示某种循环&#xff0c;和run放在一起就表示一直在运行着的循环 二:Runloop的创建? iOS并没有提供Runloop的创建方法,因为创建了现场自然会有一个Runloop. 所以只有获取Runloop的方法: NSRunLoop * runloo…
阅读更多...
selenium学习记录

selenium学习记录

1、初识selenium 概述&#xff1a; Selenium是一个Web的自动化测试工具&#xff0c;最初是为网站自动化测试而开发的&#xff0c;类型像我们玩游戏用的按键精灵&#xff0c;可以按指定的命令自动操作&#xff0c;不同是Selenium 可以直接运行在浏览器上&#xff0c;它支持所有…
阅读更多...
TXT文件转换pdf格式的java方法

TXT文件转换pdf格式的java方法

<dependency><groupId>com.itextpdf</groupId><artifactId>itextpdf</artifactId><version>5.5.13.2</version> </dependency>接下来&#xff0c;编写一个方法来执行文件转换&#xff1a; import com.itextpdf.text.Document…
阅读更多...
计算机网络-物理层

计算机网络-物理层

物理层 基本概念 物理层考虑怎样才能在连接各种计算机的传输媒体上传输数据比特流 物理层为数据链路层屏蔽了各种传输媒体的差异&#xff0c;使数据链路层只需要考虑如何完成本层的协议和服务&#xff0c;而不必考虑网络具体的传输媒体是什么 物理层协议主要任务 机械特性&am…
阅读更多...
小兔鲜首页制作css

小兔鲜首页制作css

一、项目目录 项目名-客户端 xtx-pc 1.images&#xff1a;存放固定使用的图片&#xff0c;例如&#xff1a;logo、样式修饰图 2.uploads:存放非固定图片&#xff0c;例如&#xff1a;商品图、宣传图等需要上传的图片 3.iconfont:字体图标素材 4.css文件&#xff1a; 4.1base.cs…
阅读更多...
C语言 | Leetcode C语言题解之第371题两整数之和

C语言 | Leetcode C语言题解之第371题两整数之和

题目&#xff1a; 题解&#xff1a; int getSum(int a, int b){ int c; while(b) {c(unsigned int)(a&b)<<1;a^b;bc; }return a; }
阅读更多...
资产架构端口应用CDNWAF站库分离负载均衡

资产架构端口应用CDNWAF站库分离负载均衡

知识点&#xff1a; 1、资产架构-端口&目录&插件接口&多站点&多应用 2、番外安全-域名&服务器本身&服务厂商&管理人员 3、考虑阻碍-站库分离&CDN&WAF&负载均衡&主机防护 详细点&#xff1a; 1、前置条件-购买使用-云服务器&a…
阅读更多...
第135天：内网安全-横向移动非约束委派约束委派数据库攻防

第135天：内网安全-横向移动非约束委派约束委派数据库攻防

案例一: 横向移动-原理利用-非约束委派 该案例建立了解即可&#xff0c;真实环境应该不可能有人这样配置 非约束委派的原理和利用场景 原理&#xff1a; 机器 A &#xff08;域控&#xff09;访问具有非约束委派权限的机器 B 的服务&#xff0c;会把当前认证用户&#x…
阅读更多...
Admin.NET源码学习（4：基于Furion的后台服务启动方式浅析）

Admin.NET源码学习（4：基于Furion的后台服务启动方式浅析）

Admin.NET为前后端分离架构&#xff0c;后台服务的入口项目为Admin.NET.Web.Entry&#xff0c;其与其它项目的依赖关系如下图所示。   由于项目采用Furion框架&#xff0c;后台服务启动方式、注册方式、配置方式等方面与常规的asp.net core项目差异明显&#xff0c;初步接触…
阅读更多...
初识C语言指针（5）

初识C语言指针（5）

目录 1. 回调函数 2. qsort函数 2.1 qsort函数的基本参数 2.2 qsort函数的使用 2.3 qsort排序结构体类型数据 结语 1. 回调函数 什么是回调函数呢&#xff1f;回调函数就是⼀个通过函数指针调⽤的函数。 如果你把函数的指针&#xff08;地址&#xff09;作为参数传递给另…
阅读更多...
如何使用ssm实现铁岭河医院医患管理系统+vue

如何使用ssm实现铁岭河医院医患管理系统+vue

TOC ssm077铁岭河医院医患管理系统vue 系统概述 进过系统的分析后&#xff0c;就开始记性系统的设计&#xff0c;系统设计包含总体设计和详细设计。总体设计只是一个大体的设计&#xff0c;经过了总体设计&#xff0c;我们能够划分出系统的一些东西&#xff0c;例如文件、文…
阅读更多...
《黑神话:悟空》中的实景三维建模

《黑神话:悟空》中的实景三维建模

这几天&#xff0c;国产游戏《黑神话:悟空》终于面世&#xff0c;迅速引爆了全球游戏市场。作为一款以《西游记》为背景的3A级动作角色扮演游戏&#xff0c;《黑神话:悟空》不仅在文化表达上极具吸引力&#xff0c;其背后的技术实力更是令人瞩目。本文将深入探讨&#xff0c;3A…
阅读更多...
UEditor百度富文本后端上传文件接口

UEditor百度富文本后端上传文件接口

UEditor百度富文本后端上传文件接口 直接上代码 接口&#xff1a; RequestMapping("/UEditorConfig")public String list(HttpServletRequest request, HttpServletResponse response) throws IOException {String config environment.getProperty("ueditor.c…
阅读更多...
C/C++逆向：寻找main函数（Debug-x86）

C/C++逆向：寻找main函数（Debug-x86）

在程序的逆向分析中&#xff0c;寻找main函数在逆向分析中是非常重要的&#xff0c;它是程序的核心执行点&#xff0c;从这里开始&#xff0c;程序的主要逻辑开始展开&#xff1b;在这边我们需要明确两个概念&#xff1a;用户入口&#xff08;User Entry Point&#xff09; 和 …
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023