数据结构：栈和队列

server/2024/12/22 9:49:54/

前言

        本章节较为抽象，我们先讲解概念，再进行举例。如有问题，欢迎评论区提问质疑。

栈

     1.概念与结构

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

        大家不妨把它想象成这么个杯子（栈），杯子里面是不同的液体（数据）。我们在加入新液体（入栈）的时候呢，新加入的液体会在最上层（大家别较真密度问题，就是一个比喻帮助大家理解）。我们如果想取出下层的液体呢，就需要将上面的液体倒掉（这就是栈结构的先进后出原则）。

        入栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。

        出栈：栈的删除操作叫做出栈。出数据也在栈顶。

     2.栈的框架

        一个数据结构通常具备增、删、查、改等基本功能。栈遵循后进先出原则，操作主要集中在栈顶，其入栈和出栈操作分别对应增和删。而由于栈不能遍历且只能在一端操作，它没有常规意义上的查找功能。

typedef char STDataType;//方便更改存放数据的类型
typedef struct Stack
{STDataType* a;//数组指针int top;//栈顶位置int capacity;//数据结构容量
}ST;// 初始化栈
void STInit(ST* ps);// 销毁栈
void STDestroy(ST* ps);// ⼊栈
void STPush(ST* ps, STDataType x);//出栈
void STPop(ST* ps);//取栈顶元素
STDataType STTop(ST* ps);//栈是否为空
bool STEmpty(ST* ps);

   3.栈的详解

      (1)初始化栈

        顾名思义，该函数的作用是将结构体中的数据全部初始化，指针置为空，整型置为0。

void STInit(ST* ps)
{assert(ps);//判断ps不为空ps->arr = NULL;ps->capacity = ps->top = 0;
}

      (2)销毁栈

        该函数是在不再需要某个栈时的操作。将动态分配的内存释放掉，指针指向空，将其余数据归为初始状态。

void STDestroy(ST* ps)
{assert(ps);if (ps->arr){free(ps->arr);//释放内存}ps->arr = NULL;//指针指向空，防止野指针出现ps->top = ps->capacity = 0;
}

      (3)入栈

        该指针是向栈中压入数据时使用的。其主要功能是判断空间是否足够，如果不够，开辟新的空间。足够则将数据压入栈中即可。

void StackPush(ST* ps, STDataType x)
{assert(ps);//1.判断空间是否足够//满足该if条件，则空间已满if (ps->capacity == ps->top){//若空间为0，则赋初值为4.若非0，则开辟出原有空间2倍的空间int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));if (tmp == NULL)//判断空间是否开辟成功{//未成功开辟perror("realloc fail!");//显示报错exit(1);//若空间不足，非正常退出程序}//成功开辟ps->arr = tmp;//赋值为新开辟的地址ps->capacity = newCapacity;//将容量更新}//空间足够，直接赋值即可ps->arr[ps->top++] = x;
}

      (4)判断栈是否为空 

        这个函数通常在出栈函数和获取栈顶元素时被调用。因为当栈为空时，我们将不能再执行出栈或者获取栈顶元素操作。

bool StackEmpty(ST* ps)
{assert(ps);//判断ps指针不指向空return ps->top == 0;
}

      (5)出栈

        该出栈函数执行的是栈的标准出栈操作。遵循后进先出原则，出栈时将栈顶指针top减 1，使原栈顶元素被移除，新栈顶变为原栈顶元素的下一个。值得一提的是，出栈操作需在栈不为空时进行。

void StackPop(ST* ps)
{//判ps指针是否为空assert(ps);//判该数据结构是否为空assert(!StackEmpty(ps));//出栈时别忘了给栈顶减1--ps->top;
}

      (6)取栈顶元素

        前面说过，我们的栈是不能被遍历的。那么我们在操作时就不能直接去对指针解引用访问数组，不然这和顺序表也就没什么区别了。所有我们需要封装一个专门调取栈顶元素的函数。

//取栈顶元素
STDataType StackTop(ST* ps)
{assert(ps);assert(!StackEmpty(ps));return ps->arr[ps->top - 1];
}

 4.小试牛刀

   题目链接：. - 力扣（LeetCode）

  题目信息

源码附注释

#include <stdbool.h>
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#include <string.h>
typedef struct stack
{char* arr;int capacity;//栈容量int top;//数据个数
}ST;
void StackPush(char x,ST* ps)//进栈
{assert(ps);if(ps->capacity==ps->top)//满栈{int newcapacity=ps->capacity==0?4:ps->capacity*2;char* tem=(char*)realloc(ps->arr,newcapacity);assert(tem);//创建新空间失败ps->arr=tem;}ps->arr[ps->top++]=x;//将栈顶放置为新数据并将栈顶加一
}
bool StackEmpty(ST* ps)
{// 检查传入的指针是否有效，如果指针为空，则程序会在断言处终止并给出错误提示assert(ps);// 如果栈顶指针为 0，表示栈中没有任何元素，即栈为空return ps->top == 0;
}
void StackPop(ST* ps)//出栈
{assert(ps);assert(!StackEmpty(ps));//如果top==0返回值为ture，故非--ps->top;
}
void InitStack(ST* ps)//初始化栈
{assert(ps);ps->arr = NULL;ps->capacity=0;ps->top=0;
}
void DestroyStack(ST* ps)//销毁栈
{assert(ps);free(ps->arr);ps->arr = NULL;ps->capacity = 0;ps->top = 0;
}
char StackTop(ST* ps)//用于调取栈顶元素的函数
{assert(ps);assert(!StackEmpty(ps));//如果top==0返回值为ture，故非return ps->arr[ps->top-1];//返回栈顶元素
}
int main()
{ST stack;InitStack(&stack);char arr[100001];gets(arr);int flag=1;for(int i=0;i<strlen(arr);i++){if(arr[i]=='{'||arr[i]=='['||arr[i]=='(')//如果是左半括号{StackPush(arr[i],&stack);//入栈flag=0;}else{if(!StackEmpty(&stack)==false)//{flag=0;break;}//如果arr数组中有右半括号，看栈顶元素是否与之对应if(arr[i]=='}'&&StackTop(&stack)=='{'){StackPop(&stack);flag=1;}	else if(arr[i]==']'&&StackTop(&stack)=='['){StackPop(&stack);flag=1;}else if(arr[i]==')'&&StackTop(&stack)=='('){StackPop(&stack);flag=1;}else{flag=0;DestroyStack(&stack);break;}}}if(strlen(arr)==0)//当什么都没有输入，结果为false{flag=0;}if(flag==1){printf("true");}else{printf("false");}return 0;
}

         需要注意的是，我这里写的是完整代码，而力扣上提交则是提交一个函数。代码截图如下：

队列 

       1.概念与结构

        队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊性表，队列具有新进先出的特性。

        队列嘛，顾名思义，就像是一排数据结构在站队。新增添的数据只能排在队伍的最后，而想要出队列则需要从最前面出来。如图：

        如果将栈喻为杯子，那队列就是管子，从一端进，另一端出。

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

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

     2.队列框架

        队列遵循先进先出原则，操作主要在队首（出队）和队尾（入队）。其入队操作(QueuePush)对应增加元素，出队操作(QueuePop)对应删除元素。对于查找功能，由于队列一般只能从队首开始依次遍历节点，相对效率较低，但也可通过遍历队列节点来查找特定元素。队列没有像顺序表那样可直接定位的高效查找方式。整体而言，队列的操作主要围绕入队、出队以及获取队首和队尾元素展开。

//队列结点结构
typedef struct QueueNode
{//存放队列的结点所需变量
}QNode;
//队列结构
typedef struct Queue
{//存放队列所需变量
}Queue;
//初始化队列
void QueueInit(Queue* pq);
//销毁队列
void QueueDestroy(Queue* pq);
// ⼊队列，队尾
void QueuePush(Queue *pq, QDataType x);
// 出队列，队头
void QueuePop(Queue* pq);
//取队头数据
int QueueFront(Queue* pq);
//取队尾数据
int QueueBack(Queue* pq);
//队列判空
bool QueueEmpty(Queue* pq);

    3.队列详解

      (1)队列节点结构讲解

        我们的队列是通过链表来实现的。因此包含两个元素，一是我们存放的数据，二便是指向下一节点的指针。代码如下

//我们这里用链表举例来讲解队列
typedef struct QueueNode//队列节点
{int data;//存放数据struct QueueNode* next;//指向下一节点的指针
}QueueNode;

      (2)队列结构体讲解

        这里的队列结构体包含头结点的地址，可在此位置进行数据的插入操作；还包含尾节点的地址，用于在该位置进行数据的删除操作；同时，还有一个整型变量size，用于统计队列中的数据个数。

//完整队列包含的基本数据
typedef struct Queue
{struct QueueNode* phead;//该指针指向队列头struct QueueNode* ptail;//该指针指向队列尾int size;//队列中存放的数据个数
}Queue;

      (3)队列初始化

        不用我过多解释了吧？指针置空，整型归0。

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

      (4) 队列判空

        我们虽然判断了指针pq不为空，但是不排除pq指向了一个空队列的情况。这种情况下我们判断一下头指针只想是否为空即可。

//队列判空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->phead==NULL;
}

      (5)入队列

        这里的逻辑就是尾插。做法很简单，创建新节点以后将存储的数据放入节点即可。最后别忘了将为节点更新为最新创建的节点并给size++，我们来看一下示意图：

  若队列为空，我们直接创建一个新的节点，并让头尾指针都直系那个该节点即可，如图：

  若队列不为空，我们就创建一个新节点，先让当前尾节点指向最新结点，再将最新节点作为尾结点，示意图如下：

插入前：

 插入后：

 详细步骤请看源码：

//入队列,从队尾入
void QueuePush(Queue* pq, int x)
{assert(pq);//申请新结点QueueNode* 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++;
}

      (6)出队列

        这里的出队列要从头出。换句话说，就是将头结点删除了。示意图如下：

删除前：

删除后：

 详细步骤请见代码：

//出队列,从队头出
void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));//当前队列只有一个结点的情况if (pq->ptail == pq->phead){free(pq->phead);//释放该结点pq->phead = pq->ptail = NULL;//置空}else{//删除队头元素QueueNode* next = pq->phead->next;//将第二个结点的地址存入nextfree(pq->phead);//释放当前头结点pq->phead = next;//将next作为头结点}pq->size--;
}

      (7)功能演示

        其实就是刚刚的代码片段拼凑起来，并调用了几个出入队列的函数

        演示代码如下：

#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
#include<assert.h>
//我们这里用链表举例来讲解队列
typedef struct QueueNode//队列节点
{int data;//存放数据struct QueueNode* next;//指向下一节点的指针
}QueueNode;
typedef struct Queue
{struct QueueNode* phead;//该指针指向队列头struct QueueNode* ptail;//该指针指向队列尾int size;//队列中存放的数据个数
}Queue;
//队列初始化
void QueueInit(Queue* pq)
{assert(pq);pq->phead = pq->ptail = NULL;pq->size = 0;
}
//入队列,从队尾入
void QueuePush(Queue* pq, int x)
{assert(pq);//申请新结点QueueNode* 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->phead == NULL;
}
//出队列,从队头出
void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));//当前队列只有一个结点的情况if (pq->ptail == pq->phead){free(pq->phead);//释放该结点pq->phead = pq->ptail = NULL;//置空}else{//删除队头元素QueueNode* next = pq->phead->next;//将第二个结点的地址存入nextfree(pq->phead);//释放当前头结点pq->phead = next;//将next作为头结点}pq->size--;
}
main()
{Queue q;//创建队列qQueueInit(&q);//初始化q队列QueuePush(&q, 1);//入队列QueuePush(&q, 2);//入队列QueuePush(&q, 3);//入队列QueuePop(&q);//出队列QueuePop(&q);//出队列
}
        演示结果

        我们先看一下，将1 2 3都放入队列中队列中的队列，如下图：

        下面我们将出队列两次，看一下现在的队列：

        队列是一种遵循先进先出原则的数据结构，通常由队首指针、队尾指针和元素个数等组成，支持入队（在队尾添加元素）、出队（从队首移除元素）等操作。

4.小试牛刀

        今天搞累了，数据好的话明天就拓展一下。


http://www.ppmy.cn/server/129245.html

相关文章

C++模拟实现vector容器【万字模拟✨】

C++模拟实现vector容器【万字模拟✨】

更多精彩内容..... &#x1f389;❤️播主の主页✨&#x1f618; Stark、-CSDN博客 本文所在专栏&#xff1a; 学习专栏C语言_Stark、的博客-CSDN博客 项目实战C系列_Stark、的博客-CSDN博客 数据结构与算法_Stark、的博客-CSDN博客 座右铭&#xff1a;梦想是一盏明灯&#xff…
阅读更多...
C++ 3D冒险游戏开发案例

C++ 3D冒险游戏开发案例

3D冒险游戏的C开发案例&#xff0c;包括游戏设计、实现细节、图形渲染、音效处理等内容。 3D冒险游戏开发案例 一、游戏设计 游戏概述 游戏名称&#xff1a;“探索者的传奇”类型&#xff1a;3D冒险游戏目标&#xff1a;玩家控制角色在一个开放的世界中探索、解谜、战斗并完成…
阅读更多...
【斯坦福CS144】Lab2

【斯坦福CS144】Lab2

一、实验目的 实现一个 TCPReceiver&#xff0c;用以接收传入的 TCP segment 并将其转换成用户可读的数据流。 二、实验内容 1.接收TCP segment&#xff1b; 2.重新组装字节流&#xff08;包括EOF&#xff09;&#xff1b; 3.确定应该发回给发送者的信号&#xff0c;以进行…
阅读更多...
10.2 Linux_进程_进程相关函数

10.2 Linux_进程_进程相关函数

创建子进程 函数声明如下&#xff1a; pid_t fork(void); 返回值&#xff1a;失败返回-1&#xff0c;成功返回两次&#xff0c;子进程获得0(系统分配)&#xff0c;父进程获得子进程的pid 注意&#xff1a;fork创建子进程&#xff0c;实际上就是将父进程复制一遍作为子进程&…
阅读更多...
【操作系统】引导（Boot）电脑的奇妙开机过程

【操作系统】引导（Boot）电脑的奇妙开机过程

&#x1f339;&#x1f60a;&#x1f339;博客主页&#xff1a;【Hello_shuoCSDN博客】 ✨操作系统详见 【操作系统专项】 ✨C语言知识详见&#xff1a;【C语言专项】 目录 什么是操作系统的引导&#xff1f; 操作系统的引导&#xff08;开机过程&#xff09; Windows操作系…
阅读更多...
计算机视觉硬件知识点整理（五）：3CCD彩色相机介绍与成像原理

计算机视觉硬件知识点整理（五）：3CCD彩色相机介绍与成像原理

文章目录 前言一&#xff0c;3CCD彩色相机介绍二&#xff0c;3CCD彩色相机成像流程 前言 在当代影像技术领域&#xff0c;相机的核心组件——图像传感器&#xff0c;经历了从传统的胶片到现代数字化的革命性转变。其中&#xff0c;3CCD&#xff08;Three-Chip Charge-Coupled …
阅读更多...
QT 自动识别文本文件的编码格式

QT 自动识别文本文件的编码格式

这是我记录Qt学习过程心得文章的第一篇&#xff0c;也是前一段时间遇到的一个实实在在的问题&#xff0c;就是读取文本文件经常出现乱码&#xff0c;围绕读取文本文件时预先检测文本文件的编码格式&#xff0c;然后再在读取的时候自动设置对应的编码&#xff0c;我问遍度娘&…
阅读更多...
线性代数入门指南

线性代数入门指南

在数学的广袤领域中&#xff0c;线性代数犹如一座神秘而又充满魅力的殿堂&#xff0c;等待着初学者去探索。当你踏入线性代数的大门&#xff0c;便开启了一段充满挑战与惊喜的知识之旅。 线性代数是什么呢&#xff1f;简单来说&#xff0c;它是一门研究线性方程组、向量空间、线…
阅读更多...
最新文章

Copyright @ 2022~2023