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

栈与队列的常见接口的实现

news 2024/10/22 9:53:32

一 . 栈

1.1 概念与结构

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

  • 压栈 ： 栈的插入操作叫做 进栈 / 压栈 / 入栈 ， 入数据在栈顶
  • 出栈 :   栈的删除操作叫做出栈 。 出数据也在栈顶！

栈的底层结构选型 :  

栈的实现一般可以使用数组或者链表实现 ， 相对而言数组的实现更优一些 。 因为数组在尾上插入数据的代价比较小！

 1.2 栈的常见接口的实现

这里使用数组作为 栈的底层结构：想了解得更详细 => 顺序表应用-CSDN博客

1.2.1 初始化栈

选择栈的底层原理为数组 : 与数组一样 ， 这里只是把size 改称了top , 方便理解操作！

//定义栈结构
typedef int STDataType;
typedef struct Stack
{STDataType* arr;int top; // 栈顶元素 -- 有效数据个数int Capacity;
}ST;//初始化栈
void STInit(ST* ps);
//初始化栈
void STInit(ST* ps)
{assert(ps);ps->arr = NULL;ps->top = ps->Capacity = 0;
}
1.2.2 入栈

与顺序表的插入数据的步骤一样 ：

1 ） 判断空间是否足够

2 ） 插入数据

3 )   top 往后走

//入栈
void StackPush(ST* ps, STDataType x)
{assert(ps);//判断空间是否足够if (ps->top == ps->Capacity){int newCapacity = ps->Capacity == 0 ? sizeof(STDataType) : 2 * ps->Capacity;//空间不足够,realloc进行扩容ST* temp = (ST*)realloc(ps->arr, newCapacity * sizeof(STDataType));if (temp == NULL){perror("realloc fail!");return 1;}ps->arr = temp;ps->Capacity = newCapacity;}//空间足够ps->arr[ps->top++] = x;
}
1.2.3判断栈是否为空
//判断栈是否为空
bool StackEmpty(ST* ps)
{assert(ps);return ps->top == 0; 
}
1.2.4 出栈

出栈之前先判断栈是否为空 ， 不为的空时候再出栈

//出栈
void StackPop(ST* ps)
{//判断栈是否为空assert(!StackEmpty(ps));ps->top--;
}
1.2.5 取栈顶元素
//取栈顶元素
STDataType STTop(ST* ps)
{assert(!StackEmpty(ps));return ps->arr[ps->top - 1];
}
1.2.6 栈的有效个数
int STSize(ST* ps)
{return ps->top;
}
1.2.7 打印栈
	//打印栈while (!StackEmpty(&st)){//取栈顶元素STDataType top = STTop(&st);printf("%d ", top);//出栈StackPop(&st);}
1.2.8 销毁栈
//销毁栈
void STDestory(ST* ps)
{assert(ps);if (ps->arr){free(ps->arr);}ps->arr = NULL;ps->top = ps->Capacity = 0;
}
1.2.9 总代码

Stack.c

#include "Stack.h"//初始化栈
void STInit(ST* ps)
{assert(ps);ps->arr = NULL;ps->top = ps->Capacity = 0;
}//销毁栈
void STDestory(ST* ps)
{assert(ps);if (ps->arr){free(ps->arr);}ps->arr = NULL;ps->top = ps->Capacity = 0;
}//判断栈是否为空
bool StackEmpty(ST* ps)
{assert(ps);return ps->top == 0; 
}//入栈
void StackPush(ST* ps, STDataType x)
{assert(ps);//判断空间是否足够if (ps->top == ps->Capacity){int newCapacity = ps->Capacity == 0 ? sizeof(STDataType) : 2 * ps->Capacity;//空间不足够,realloc进行扩容ST* temp = (ST*)realloc(ps->arr, newCapacity * sizeof(STDataType));if (temp == NULL){perror("realloc fail!");return 1;}ps->arr = temp;ps->Capacity = newCapacity;}//空间足够ps->arr[ps->top++] = x;
}//出栈
void StackPop(ST* ps)
{//判断栈是否为空assert(!StackEmpty(ps));ps->top--;
}//取栈顶元素
STDataType STTop(ST* ps)
{assert(!StackEmpty(ps));return ps->arr[ps->top - 1];
}//获取栈的有效元素个数
int STSize(ST* ps)
{return ps->top;
}

test .c  

#include "Stack.h"void test()
{ST st;STInit(&st);//入栈StackPush(&st, 1);StackPush(&st, 2);StackPush(&st, 3);StackPush(&st, 4);StackPush(&st, 5);//出栈//StackPop(&st);//StackPop(&st);//StackPop(&st);//StackPop(&st);//打印栈while (!StackEmpty(&st)){//取栈顶元素STDataType top = STTop(&st);printf("%d ", top);//出栈StackPop(&st);}STDestory(&st);
}
int main()
{test();return 0;
}

Stack .h  

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>//定义栈结构
typedef int STDataType;
typedef struct Stack
{STDataType* arr;int top; // 栈顶元素int Capacity;
}ST;//初始化栈
void STInit(ST* ps);//销毁栈
void STDestory(ST* ps);//判断栈是否为空
bool StackEmpty(ST* ps);//入栈
void StackPush(ST* ps,STDataType x);//出栈
void StackPop(ST* ps);//取栈顶元素
STDataType STTop(ST* ps);//获取栈的有效元素个数
int STSize(ST* ps);

二 . 队列

2.1 概念与结构

队列 ： 只允许在一端进行插入数据操作 ， 在另一端进行删除数据操作的特殊线性表 ， 队列具有先进先出FIFO（Firit In Frist Out )

入队列 ： 进行插入操作的一端称为队尾

出队列 ： 进行删除操作的一端称为对头

这里可以用在饭堂排队吃饭来理解 ==> 排队买饭 ， 不能插队 ， 从队尾入队买饭 ， 打完饭从对头出队吃饭！

 队列底层结构选型 : 

队列也可以用数组和链表的结构实现 ， 使用链表的结构实现更优一些 ， 因为如果使用数组的结构 ， 出队在数组头上出数据 ， 效率会比较低 。 

 如果在链表的基础上 ， 创建一个结构体指针变量 ， 存储队列的尾结点 ， 能减低复杂度

2.2 队列的常见接口的实现

 2.2.1 初始化

这里可能会比较难理解一些 : 这里选择链表作为队列的底层原理 

队列底层原理是链表 ， 链表是由一个一个的结点组成 ，所以 ---> 定义一个结点的结构体 ；

队列有两个成员变量（结构体成员变量），所以 --->  定义队列结构，包含phead,ptail  ; 

typedef int QDataType;
//定义队列结点的结构
typedef struct QueueNode
{QDataType data;struct QueneNode* next;
}QueueNode;
//定义队列的结构
typedef struct Queue
{QueueNode* phead;QueueNode* ptail;
}Queue;//初始化
void QueueInit(Queue* pq);

//初始化
void QueueInit(Queue* pq)
{assert(pq);pq->phead = pq->ptail = NULL;
}

1.2.2 插入数据

往队尾插入数据 ： 

思路 : 

1 . 向操作系统申请一个结点的空间大小 -- newnode

2 . 尾插

         1) 判断队列是否为空 --> 空 ---> pq->phead = pq->ptail = newnode

         2)                    不为空 ---->pq-> ptail -> next  = newnode ,pq-> ptail = newnode  

//插入数据
void QueuePush(Queue* pq, QueueNode* x)
{assert(pq);//向操作系统申请一块结点大小的空间 -- newnodeQueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));if (newnode == NULL){perror("malloc fail!");exit(1);}newnode->data = x;newnode->next = NULL;//插入数据//队列为空if (pq->phead == NULL){pq->phead = pq->ptail = newnode;}//队列不为空else {pq->ptail->next = newnode;pq->ptail = newnode;}
}

1.2.3 队列判空

队列为空时 ， ptail 与 phead 都为空 

//判断队列是否为空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->ptail == NULL;
}

1.2.4 删除数据

删除数据之前 ， 先判断队列是否为空 ， 不为空时才进行数据的删除操作 ， 从队头删除数据 ！

1 ) 如果只有一个结点 ，释放phead , 相当于释放掉 ptail , 最后置为NULL

2 ) 多个节点 --- > 遍历队列进行释放 ， 最后不要忘记把 phead 与 ptail 置为NULL

//删除数据
void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));//一个结点if (pq->phead == pq->ptail){free(pq->phead);pq->phead = pq->ptail = NULL;}//多个结点else {QueueNode* next=pq->phead->next;free(pq->phead);pq->phead = next;}--pq->size;
}

1.2.5 取对头数据 

直接返回 pq->phead->data , 但是要先判断队列不为空

//取队头数据
QDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->phead->data;
}

1.2.6 取队尾数据

直接返回 pq->ptail->data , 但是要先判断队列不为空

//取队尾数据
QDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->ptail->data;
}

1.2.7 队列有效元素个数

有两种方式 ：

第一种 : 定义一个计数器 ， 遍历队列 ， 不为空时 ， 计数器++ ，与队列的其他接口相比，这种方式时间复杂度比较高

第二种 : 给定义队列的成员变量中添加一个变量 size , 当往队列中插入数据时 , size++ , 这是的时间复杂度是 O（1） 

//队列中的有效元素个数
int QueueSize(Queue* pq)
{QueueNode* pcur = pq->phead;int size = 0;while (pcur){size++;pcur = pcur->next;}return pq->size;
}

//定义队列的结构
typedef struct Queue
{QueueNode* phead;QueueNode* ptail;int size;
}Queue;

1.2.8 销毁队列

遍历队列一个一个释放空间

//销毁队列
void QueueDestory(Queue* pq)
{assert(pq);QueueNode* pcur = pq->phead;while (pcur){QueueNode* next = pcur->next;free(pcur);pcur = next;}pq->phead = pq->ptail = NULL;pq->size = 0;
}

 1.2.9 总代码

test . c

#include "Queue.h"void test()
{Queue q;QueueInit(&q);//插入数据QueuePush(&q, 1);QueuePush(&q, 2);QueuePush(&q, 3);QueuePush(&q, 4);QueuePush(&q, 5);//while (QueueSize(&q))//{//	printf("%d\n", QueueSize(&q));//	QueuePop(&q);//}//printf("phead = %d\n", QueueFront(&q));//printf("ptail = %d\n", QueueBack(&q));QueueDestory(&q);
}
int main()
{test();return 0;
}

Queue . c

#include "Queue.h"//初始化
void QueueInit(Queue* pq)
{assert(pq);pq->phead = pq->ptail = NULL;pq->size = 0;
}//插入数据
void QueuePush(Queue* pq, QueueNode* x)
{assert(pq);//向操作系统申请一块结点大小的空间 -- newnodeQueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));if (newnode == NULL){perror("malloc fail!");exit(1);}newnode->data = x;newnode->next = NULL;//插入数据//队列为空if (pq->phead == NULL){pq->phead = pq->ptail = newnode;}//队列不为空else {pq->ptail->next = newnode;pq->ptail = pq->ptail->next;}pq->size++;
}//判断队列是否为空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->ptail == NULL;
}//队列中的有效元素个数
int QueueSize(Queue* pq)
{//QueueNode* pcur = pq->phead;//int size = 0;//while (pcur)//{//	size++;//	pcur = pcur->next;//}return pq->size;
}//删除数据
void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));//一个结点if (pq->phead == pq->ptail){free(pq->phead);pq->phead = pq->ptail = NULL;}//多个结点else {QueueNode* next=pq->phead->next;free(pq->phead);pq->phead = next;}--pq->size;
}//取队头数据
QDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->phead->data;
}//取队尾数据
QDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->ptail->data;
}//销毁队列
void QueueDestory(Queue* pq)
{assert(pq);QueueNode* pcur = pq->phead;while (pcur){QueueNode* next = pcur->next;free(pcur);pcur = next;}pq->phead = pq->ptail = NULL;pq->size = 0;
}

Queue . h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>typedef int QDataType;
//定义队列结点的结构
typedef struct QueueNode
{QDataType data;struct QueneNode* next;
}QueueNode;
//定义队列的结构
typedef struct Queue
{QueueNode* phead;QueueNode* ptail;int size;
}Queue;//初始化
void QueueInit(Queue* pq);//插入数据
void QueuePush(Queue* pq, QueueNode* x);//判断队列是否为空
bool QueueEmpty(Queue* pq);//队列中的有效元素个数
int QueueSize(Queue* pq);//删除数据
void QueuePop(Queue* pq);//取队头数据
QDataType QueueFront(Queue* pq);//取队尾数据
QDataType QueueBack(Queue* pq);//销毁队列
void QueueDestory(Queue* pq);

http://www.mrgr.cn/news/54973.html

相关文章：

  • WebSocket状态码及异常报错1006
  • VideoCLIP-XL：推进视频CLIP模型对长描述的理解
  • Unity 2d UI 实时跟随场景3d物体
  • linux系统中chmod用法详解
  • 使用Airtest自动化某云音乐爬取歌曲名称
  • 基于springboot的网上服装商城推荐系统的设计与实现
  • yolov8实例分隔
  • OpenCV图像处理——查找线条的转折点
  • 鸿蒙中富文本编辑与展示
  • Guava防击穿回源-同步防击穿
  • 数据结构7——二叉树的顺序结构以及堆的实现
  • jupyter notebook中执行过程中更新模块代码，再执行没有更新执行
  • 机器学习与神经网络：诺贝尔物理学奖的新纪元
  • Vue中使用路由
  • 数据结构：二叉树、堆
  • python+Mosh网课笔记04
  • 计算机毕业设计 基于java个性化智能学习系统的设计与实现 Java+SpringBoot+Vue 前后端分离 文档报告 代码讲解 安装调试
  • 关于SSD1306的OLED的显示的研究
  • 一图秒懂色彩空间和色彩模型
  • 云计算-----单机LNMP结构WordPress网站
  • 从DexMV、VideoDex、MimicPlay到SeeDo：从人类视频中学习：机器人的主流训练方法之一
  • 网盘直链下载神器NDM
  • Springboot指定扫描路径
  • NTA-IoU指标提升超42%，北京大学提出首个使用世界模型提升自动驾驶场景重建质量DriveDreamer4D
  • ESP32-C3 入门笔记04：gpio_key 按键 (ESP-IDF + VSCode)
  • 深入拆解TomcatJetty（二）