数据结构——栈与队列的实现（全码）

🕗 发布于 2024-10-08 11:40 数据结构 c++ c语言 笔记

一栈的概念

栈是一种特殊的线性表，栈内数据遵循先进后出(LIFO)的原则，对于栈，只能在同一侧进行入栈和出栈操作。

入栈操作和出栈操作是在栈的同一侧进行的，如图示：

对于栈这种数据类型，我们可以采用链表或者数组来实现，但是我们一般采取数组的形式进行实现。

二栈的实现

1.栈的声明

对于一个用数组形式来实现的栈来说，我们需要声明:

指向栈的有效地址指针，栈顶(栈的有效空间)top, 栈的最大容量capacity

typedef int TypeData;
typedef struct Stack {
TypeData* a;
int top;      //有效个数
int capacity;  //最大空间
}ST;

这里top为什么时栈的有效个数呢？因为我们让top指向了当前数组存在有效数据的最大下标+1的位置，这样top更加直观的表达当前栈内的元素

2.栈的初始化

在一个栈创建后，需要对栈进行初始化后才能进行使用，对于栈的初始状态：

指向数组首元素地址的指针为NULL

栈初始的最大容量为0

栈顶top的指向为数组为0的下标，也就是当前栈的有效数据个数为0

void STInit(ST* ps)
{
assert(ps);
ps->a = NULL;
ps->capacity = ps->top = 0;
}

初始化后栈的图示如下：

3.栈的入栈

当我们往栈中入数据时，我们不能一昧的往里面入数据，在每次入数据前需要考虑当前栈的容量是否已经满了，如果当前栈的容量已满，我们需要先将栈的最大容量扩充后再进行入栈操作。

在扩充最大容量操作时，我们应当使用realloc函数，因为我们需要保留原本栈中存放的数据

在空栈时入栈，那么第一次扩充的栈的大小是4个数据类型空间（也可以是8个，10个等）

如果栈中本来就有数据，那么当栈满时，新栈的最大容量为旧栈的两倍（或整数倍）

void STPush(ST* ps, TypeData x)
{
assert(ps);
//检查空间是否足够
if (ps->capacity == ps->top) {
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
//创建newcapacity个空间
ST* tmp = (ST*)realloc(ps->a, sizeof(TypeData) * newcapacity);
//如果开辟空间失败
if (tmp == NULL) {
perror("realloc");
exit(-1);
}
ps->capacity = newcapacity;
ps->a = tmp;
}
//空间足够
ps->a[ps->top++] = x;
}

4.栈的出栈前提

当进行出栈操作时，需要判定栈是否为空，如果栈为空（也就是没有数据），则无法出栈。

当栈顶为0时，说明当前栈中无数据，返回true，否则返回false

bool StackEmpty(ST* ps)
{
assert(ps);
return ps->top == 0;
}

5.栈的出栈

在栈的出栈操作前需要判断当前栈中是否存有数据，否则不能进行出栈操作

通过栈顶指针-1即可完成出栈操作

//出栈
void STPop(ST* ps)
{
assert(ps);
assert(!StackEmpty(ps));

--ps->top;
}

6.取栈顶元素

取栈顶元素前和出栈操作一样，需要判断当前栈是否为空，否则无法取栈顶元素

取栈顶元素返回的是top-1位置的数据，并非top位置

TypeData STTop(ST* ps)
{
assert(ps);
assert(!StackEmpty(ps));//栈为空栈时无法取栈顶元素

return ps->a[ps->top - 1];
}

7.获取栈的有效个数

直接返回top即可，因为top不仅代表了栈顶，还代表了当前栈中的有效个数

//获取栈中有效元素个数
int STSize(ST* ps)
{
assert(ps);
return ps->top;
}

8.栈的销毁

栈的销毁和顺序表基本一致：

void STDestroy(ST* ps)
{
assert(ps);
if (ps->a)
free(ps->a);
ps->a = NULL;
ps->top = ps->capacity = 0;
}

9.栈的全码

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int TypeData;
typedef struct Stack {
TypeData* a;
int top;      //有效个数
int capacity;  //最大空间
}ST;

//初始化
void STInit(ST* ps)
{
assert(ps);
ps->a = NULL;
ps->capacity = ps->top = 0;
}

//销毁
void STDestroy(ST* ps)
{
assert(ps);
if (ps->a)
free(ps->a);
ps->a = NULL;
ps->top = ps->capacity = 0;
}

//入栈
void STPush(ST* ps, TypeData x)
{
assert(ps);
//检查空间是否足够
if (ps->capacity == ps->top) {
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
//创建newcapacity个空间
ST* tmp = (ST*)realloc(ps->a, sizeof(TypeData) * newcapacity);
//如果开辟空间失败
if (tmp == NULL) {
perror("realloc");
exit(-1);
}
ps->capacity = newcapacity;
ps->a = tmp;
}
//空间足够
ps->a[ps->top++] = x;
}

//检查是否为空栈
bool StackEmpty(ST* ps)
{
assert(ps);
return ps->top == 0;
}

//出栈
void STPop(ST* ps)
{
assert(ps);
assert(!StackEmpty(ps));

--ps->top;
}

//取栈顶元素
TypeData STTop(ST* ps)
{
assert(ps);
assert(!StackEmpty(ps));//栈为空栈时无法取栈顶元素

return ps->a[ps->top - 1];
}

//获取栈中有效元素个数
int STSize(ST* ps)
{
assert(ps);
return ps->top;
}
int main(){
    return 0;

}

三队列的概念

队列是一种只允许在一侧入数据操作，另一侧出数据操作的线性表，具有先进先出的的原则

在入数据操作的一端称作队尾，在出数据的一端称作队头

而对于队列的底层，我们可以选择数组或者链表来实现，在这里我们使用链表来实现，因为采用数组来实现是，在出队操作后数组需要相继往前移动一位，这样才能使后面的的数据接着出队，因此采用数组的话在出队操作时效率会比链表低

队列的内部数据用链表来表示：

1.队列的声明

在上面队列的概念中我们了解到，队列的底层由链表来实现，而队列有队头和队尾，因此队列的结构体声明有些许不同，可以理解为队列由两部分组成：链表和队列本身，因此我们需要声明两个结构体：

//队列的在链表的基础上实现，所以结构体有两个，一个是链表结点(头删尾插)
typedef int TypeData;

//链表结点结构声明
typedef struct QueueNode {
TypeData data;
struct QueueNode* next;
}Node;
//队列本身的声明
typedef struct Queue {
struct QueueNode* phead;//队头
struct QueueNode* ptail;//队尾
int size;//记录队列的元素个数，每次入队+1，出队-1
}Queue;

2.队列的初始化

当我们创建一个队列时，队列中是不存在数据的，也就是不存在链表结点，因此我们在初始化时不需要初始化链表结点结构体：

//队列初始化
void QueueInit(Queue* ps) {
assert(ps);
ps->phead = ps->ptail = NULL;
ps->size = 0;
}

初始化时，队尾指针和队头指针应当为空，因为此时队列中还不存在数据（结点）

初始化后图示：

3.队列的入队

在队列的入队操作中，其实是对队列中链表的尾插操作

入队步骤：

1）创建新结点

2）在结点插入时需要判断当前队列是否为空（也就是链表是否为空），如果队列为空，那么新创建的结点就是链表的头结点，此时队尾指针和队头指针都指向头结点

3）如果当前队列不为空，那么直接在原队列上进行尾插，即在链表进行尾插，原链表最后一个结点被尾指针指向，所以原最后一个结点的指针指向新结点，原尾指针更新指向新结点

4）记录队列元素个数的size +1

//队列的入队，尾插
void QueuePush(Queue* ps, TypeData x) {
//申请新结点
Node* newNode = (Node*)malloc(sizeof(Node));
if (newNode == NULL) {
perror("malloc");
exit(1);
}
newNode->data = x;
newNode->next = NULL;

//两种情况，队列为空与不为空
if (ps->phead == NULL) {
ps->phead = ps->ptail = newNode;
}
else {
//队列不为空
ps->ptail->next = newNode;
ps->ptail = newNode;
}
ps->size++;
}

4.队列的出队前提

队列的出队与栈一样，在出队前对队列判断当前队列是否为空，只有队列非空的时候才能进行出队操作

//判断队列是否为空
bool QueueEmpty(Queue* ps) {
//头节点为空证明队列为空
return ps->phead == NULL;
}

5.队列的出队

对于队列的出队操作，其实就是链表的头删

先记录下队头结点的下一个结点Next，再释放队头结点并将队头结点指向队头结点的下一个结点Next,最后再将记录队列元素size成员-1

//队列出队，头删
void QueuePop(Queue* ps) {
assert(ps);
assert(!QueueEmpty(ps));

Queue* Next = ps->phead->next;
free(ps->phead);
ps->phead = Next;
ps->size--;
}

但是这样子其实考虑的并不完全，如果队列中只有一个结点，队尾指针和队头指针都指向该结点，那么 Next的指向为NULL，当结点释放后，队头指针指向Next达到了置空的作用，但是队尾指针却没有置空，那么此时队尾指针就成为了野指针，这是不被允许的！

因此我们需要分两种情况进行讨论：队列只有一个结点和队列有多个结点

怎样判断队列是否只有一个结点：当队头指针和队尾指针的指向相同时

//队列出队，头删
void QueuePop(Queue* ps) {
assert(ps);
assert(!QueueEmpty(ps));
//如果队列只有一个结点
if (ps->phead == ps->ptail) {
free(ps->phead);
ps->phead = ps->ptail = NULL;
}
else {
//队列有多个结点
Queue* Next = ps->phead->next;
free(ps->phead);
ps->phead = Next;
}
ps->size--;
}

6.取队头元素

无需多言，队头指针指向的数据就是队头元素，直接返回即可

//取队头元素
TypeData QueueFront(Queue* ps) {
assert(ps);
assert(!QueueEmpty(ps));
return ps->phead->data;
}

7.取队尾元素

无需多言，队尾指针指向的元素就是队尾元素，直接返回即可

//取队尾元素
TypeData QueueBack(Queue* ps) {
assert(ps);
assert(!QueueEmpty(ps));
return ps->ptail->data;
}

8.队列的销毁

利用指针del指向要删除的结点，指针Next记录删除结点的下一个结点，当del为空时证明队列已经销毁，再将队列所有的指针置空，队列有效个数置0

//队列的销毁
void DestoryQueue(Queue* ps) {
assert(ps);
assert(!QueueEmpty(ps));
Node* del = ps->phead;
while (del) {
Queue* Next = del->next;
free(del);
del = Next;
}
ps->phead = ps->ptail = del = NULL;
ps->size = 0;
}

9.获取队列的有效元素个数

直接返回结构体成员变量size即可

TypeData QueueNums(Queue* ps) {
return ps->size;
}

10.队列的全码

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

//队列的在链表的基础上实现，所以结构体有两个，一个是链表结点(头删尾插)
typedef int TypeData;

//链表结点结构声明
typedef struct QueueNode {
TypeData data;
struct QueueNode* next;
}Node;

typedef struct Queue {
struct QueueNode* phead;
struct QueueNode* ptail;
int size;
}Queue;

//队列初始化
void QueueInit(Queue* ps) {
assert(ps);
ps->phead = ps->ptail = NULL;
ps->size = 0;
}


//队列的入队，尾插
void QueuePush(Queue* ps, TypeData x) {
//申请新结点
Node* newNode = (Node*)malloc(sizeof(Node));
if (newNode == NULL) {
perror("malloc");
exit(1);
}
newNode->data = x;
newNode->next = NULL;

//两种情况，队列为空与不为空
if (ps->phead == NULL) {
ps->phead = ps->ptail = newNode;
}
else {
//队列不为空
ps->ptail->next = newNode;
ps->ptail = newNode;
}
ps->size++;
}

//判断队列是否为空
bool QueueEmpty(Queue* ps) {
//头节点为空证明队列为空
return ps->phead == NULL;
}

//队列出队，头删
void QueuePop(Queue* ps) {
assert(ps);
assert(!QueueEmpty(ps));
//如果队列只有一个结点
if (ps->phead == ps->ptail) {
free(ps->phead);
ps->phead = ps->ptail = NULL;
}
else {
//队列有多个结点
Queue* Next = ps->phead->next;
free(ps->phead);
ps->phead = Next;
}
ps->size--;
}

//取队头元素
TypeData QueueFront(Queue* ps) {
assert(ps);
assert(!QueueEmpty(ps));
return ps->phead->data;
}

//取队尾元素
TypeData QueueBack(Queue* ps) {
assert(ps);
assert(!QueueEmpty(ps));
return ps->ptail->data;
}

//队列的销毁
void DestoryQueue(Queue* ps) {
assert(ps);
assert(!QueueEmpty(ps));
Node* del = ps->phead;
while (del) {
Queue* Next = del->next;
free(del);
del = Next;
}
ps->phead = ps->ptail = del = NULL;
ps->size = 0;
}

TypeData QueueNums(Queue* ps) {
return ps->size;
}

原文地址：https://blog.csdn.net/2201_75357870/article/details/142740998

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：【网络安全】基础知识详解（非常详细）零基础入门到精通
下一篇：SpringBoot3实战：实现接口签名验证

深度学习的应用
深度学习是机器学习的一个子领域，它基于人工神经网络的学习算法，通过模拟人脑的神经网络结构来处理数据和创建模式。深度学习的核心是神经网络，它由多个节点（神经元）和连接这些节点的权重组成。这些节点和权重可
阅读更多2024-10-09
【深度学习基础模型】深度残差网络（Deep Residual Networks, DRN）详细理解并附实现代码。
深度残差网络（Deep Residual Networks, DRN）学习笔记！
阅读更多2024-10-09
JSP简介
可以让你构建复杂的Web应用程序，如在线商店、社交网络或企业级应用。这些应用程序可以处理大量的用户请求，提供个性化的内容，并与数据库进行交互以存储和检索数据。此外，JSP是Java EE（现在称为Ja
阅读更多2024-10-09
LSTM-EAAtention-Transfomer——基于有效附加注意力的时间序列预测
在自然语言处理（NLP）领域，传统的加性注意力机制通过元素乘法而非点积来捕捉令牌间的成对交互，以获取全局上下文信息。这种机制依赖于三个关键的注意力分量——查询（Q）、键（K）和值（V）——来编码输入序
阅读更多2024-10-09
【黑马点评】5 Redisson分布式锁
【黑马点评】5 Redisson分布式锁
阅读更多2024-10-09
【Linux系统编程】第二十九弹---深入探索Linux文件系统：从磁盘存储到inode结构与文件操作
文件系统相关知识，磁盘，inode：引导块(Boot Block)，块组(Block Group)，超级块(Super Block)，块组描述符(GDB)，块位图（Block Bitmap），inod
阅读更多2024-10-09
解决vsstudio2019调用hidsdi.h出现的问题
在调用hidsdi.h库后，编辑器不报错，ctrl也能打开。但是调用里面的方法出现了未定义的报错。利用你自己的渠道，搜索Hid.lib这个文件。到项目-xxx属性-链接器-常规-附加库目录。添加上面复
阅读更多2024-10-09
new Date()解析
JavaScript 中的new Date()构造函数用于创建一个表示日期和时间的对象。Date对象使得你可以以多种方式获取、设置和格式化日期和时间。让我们深入解析一下new Date()及其用法。
阅读更多2024-10-09
ctf.bugku - game1
给了score一个99999分数， sign 为 99999的base 64编码，还是失败；GET请求带有 score、IP、sign 三个参数，最后的flag 应该跟分数有关；同样的，也可以直接打
阅读更多2024-10-09
门窗对象检测系统源码分享
数据集信息展示在本研究中，我们使用了名为“CAD object window door”的数据集，以支持对门窗对象检测系统的改进，特别是针对YOLOv8模型的训练与优化。该数据集专注于两个主要类别：门
阅读更多2024-10-09