当前位置: 首页> 娱乐> 八卦 > h5免费_怎么查询企业信息_seo搜索引擎是什么_2023年国际新闻大事件10条

h5免费_怎么查询企业信息_seo搜索引擎是什么_2023年国际新闻大事件10条

时间:2025/7/11 1:31:48来源:https://blog.csdn.net/2401_87255690/article/details/145591556 浏览次数:0次
h5免费_怎么查询企业信息_seo搜索引擎是什么_2023年国际新闻大事件10条

栈和队列

  • 一、栈
    • 1.概念与结构
      • (1)概念
      • (2)底层结构
    • 2.栈的实现
      • (1)初始化
      • (2)销毁
      • (3)入栈
      • (4)出栈
      • (5)取栈顶元素
      • (6)获取栈中有效数据个数
  • 二、队列
    • 1.概念与结构
      • (1)概念
      • (2)底层结构
    • 2.栈的实现
      • (1)初始化
      • (2)销毁
      • (3)入队列
      • (4)出队列
      • (5)取队头/队尾数据
      • (6)队列有效元素个数

栈和队列需要借助前面学习过的顺序表和链表这两种数据结构。

一、栈

1.概念与结构

(1)概念

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

后进先出 / 先进后出的原则可以类比为放碗的过程。一个一个碗堆放起来,最先放入的碗一定是最后拿到的,最后放入的碗一定是最先拿到的。

压栈:栈的插⼊操作叫做进栈/压栈/入栈,入数据在栈顶。

出栈:栈的删除操作。出数据也在栈顶。

在这里插入图片描述

(2)底层结构

既然说到栈是一种特殊的线性表,既然是线性表,就要从两个维度分析:
栈的逻辑结构:一定是线性的。
栈的物理结构:栈的底层结构决定了栈的物理结构是线性的还是非线性的,前面所学的底层结构有数组结构和链表(由结点组成的)结构两种,可以用它们来实现栈的数据结构。

为了实现栈的数据结构,用数组实现更好一些呢?还是用链表实现更好一些呢?

  1. 假定使用数组来实现栈,数组必须符合栈的先进后出/后进先出的特性。接下来定义栈顶,栈顶是出数据/入数据的一端,另一端必须要封死。对于数组结构,仅仅分析数组的话,数组既可以在前面插入、删除数据,也可以在后面插入、删除数据。所以,要想使用数组来实现栈,就要对数组加以限制,使之变成栈的特性。那么栈顶定义在数组的头部还是数组的尾部呢?衡量一个算法的好与坏要从复杂度出发,假设把栈顶定义在数组尾部,出入数据只会在数组尾部进行,根据前面顺序表的知识,入栈/出栈的时间复杂度是O(1);反之定义在头部,入栈/出栈的时间复杂度是O(n)。下图是个栈,底层结构是个数组:

在这里插入图片描述

结论:使用数组实现栈的数据结构,栈顶必须定义在数组尾部,栈的入栈/出栈的时间复杂度是O(1)。

  1. 假定使用链表来实现栈,这里指单链表来实现栈,那么哪一端设置为栈顶呢?若把当前链表的尾部结点看成栈顶,入数据相当于单链表的尾插,时间复杂度是O(n),这个时间复杂度不是最好的,那么就将栈顶定义在第一个结点,此时栈的出入数据相当于单链表的头插、头删,入栈/出栈的时间复杂度是O(1)。下图是个栈,底层结构是个链表:
    在这里插入图片描述

结论:使用链表实现栈的数据结构,栈顶必须定义在链表头部(第一个结点上),栈的入栈/出栈的时间复杂度是O(1)。

很明显,选择这两种数据结构实现栈都行,但是二者的效率和占用内存都不一样,最终会选择数组作为栈的底层结构,主要是内存的问题:

  1. 数组里面定义栈的结构,数组里每插入一个整型数据,数组里申请4个字节就行:

在这里插入图片描述

  1. 单链表中定义栈的结构,根据结构体对齐,每插入一个数据,都要向操作系统申请8个字节的空间,相比数组的消耗空间更大些:
    在这里插入图片描述

数组底层结构是连续的,链表的物理结构不一定是连续的,所以使用链表还会面临内存碎片的问题。

因此,选择数组底层结构来实现栈,这样一来,栈的物理结构也是线性的,栈的结构的定义和顺序表的结构的定义是一模一样的。

栈顶一端可以出入数据,所以栈顶一端是开口的,画图的时候注意!

2.栈的实现

//Stack.h
#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;
//typedef struct Stack ST;//初始化
void STInit(ST* ps);
//销毁
void STDestroy(ST* ps);
//入栈---栈顶
void StackPush(ST* ps, STDataType x);
//出栈---栈顶
void StackPop(ST* ps);
//栈为空
bool StackEmpty(ST* ps);
//取栈顶元素
STDataType StackTop(ST* ps);
//获取栈中有效数据个数
int STSize(ST* ps);

(1)初始化

初始状态:栈为空,栈顶、栈底都在数组下标为0处,即栈顶 == 栈底

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

栈顶即可以表示栈中已保存的数据个数,也可以表示栈中要插入数据的位置

最后调试检查,形参的改变影响实参:
在这里插入图片描述

(2)销毁

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

在这里插入图片描述

(3)入栈

入栈的函数名StackPush为什么不像前面顺序表和链表的插入删除函数名一样加上Back/Front?因为栈不支持顺序表、链表的插入删除的操作,只在栈顶插入删除数据。

没有必要单独封装成检查栈的空间是否足够的函数,因为栈中所涉及的增加栈中的数据只有入栈函数一种。

在这里插入图片描述

//入栈---栈顶
void StackPush(ST* ps, STDataType x)
{assert(ps);//空间满了/初始状态栈为空,扩容if (ps->top == ps->capacity){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)出栈

出栈的函数名与入栈的函数名同理,没有Back / Front。

因为top表示栈中有效数据的个数,所以直接top----top即可,这样,栈中的有效数据个数就会减少,实现出栈。

断言需满足两个条件:

  1. 传参,栈不为空,即栈为存在的
  2. 保证栈中有数据
bool StackEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}
//出栈---栈顶
void StackPop(ST* ps)
{assert(!StackEmpty(ps));--ps->top;
}

(5)取栈顶元素

数组下标为top - 1的元素即为栈顶元素。

在这里插入图片描述

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

在这里插入图片描述

在这里插入图片描述

(6)获取栈中有效数据个数

top即为栈中有效数据个数。

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

在这里插入图片描述

二、队列

1.概念与结构

(1)概念

队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出FIFO(First In First Out)

先进先出的原则可以类比学生在食堂排队打饭的过程。最先排好队的最先打到饭,就可以最先从队伍中离开。

入队列:进行插入的操作
出队列:进行删除的操作
队尾:进行插入操作的⼀端
队头:进行删除操作的⼀端

在这里插入图片描述

(2)底层结构

同样的,队列也是一种特殊的线性表,也是要从两个维度分析,那么队列选取数组还是链表作为它的底层结构呢?

既然栈最后选取数组作为它的底层结构,那么我们可以有个大胆的猜想:链表就是队列的底层结构!

那就来看看链表到底能不能实现队列吧!

如下图所示,链表(以单链表为例)的第一个结点和最后一个结点分别作为对头/队尾分析:
在这里插入图片描述
可以得出:

  1. 当单链表的第一个结点作为对头,最后一个结点作为队尾时,入队列的时间复杂度:O(n),出队列的时间复杂度:O(1)。
  2. 当单链表的第一个结点作为队尾,最后一个结点作为对头时,入队列的时间复杂度:O(1),出队列的时间复杂度:O(n)。

这两种情况中都有出现时间复杂度:O(n),很明显都不是最好的复杂度。问题出现在都需要一个指针遍历到尾结点,这里遍历就会出现循环。那么不如直接建立一个指针指向队尾,这样就避免出现了循环!(数组就不能直接建立一个指向队尾的指针)

为了更符合单链表的使用,用第一种写法,第一个结点为对头phead、尾结点为队尾ptail
在这里插入图片描述

入队列后,改变指针的指向即可:

在这里插入图片描述

队头队尾指针指向的结点会随着入队出队的变换而变换的。

结论:队列的底层结构是链表,因此,队列的物理结构不一定是线性的。

双向链表的各种实现方法的时间复杂度都是O(1),那么为什么不直接用双向链表实现呢?
如果是双向链表的话,每申请一个结点,就会比单链表中申请的一个结点多一个前驱指针,在32位操作系统之下,会额外申请4个字节的空间。一个双向链表结点的构成:一个整形数据(假设是整形数据),两个指针。那么一个结点就是12个字节,若最大对齐数为8,则每个结点的大小是16字节,而单链表的每个结点大小是8个字节。因此,选择单链表实现队列不会占用太多的空间。

队列的底层结构是链表,链表是由结点构成的,因此可以写出结点(链表)的结构;在队列中,只关注队头、队尾结点,也就是队列由两个分别指向对头、队尾的指针构成的,队列中的有效数据个数也是队列的一部分,每次入队/出队,有效数据个数也会跟着增/减,所以可以写出队列的结构:

//Queue.h
//定义结点的结构
typedef int QDataType;
struct QueueNode {QDataType data;struct QueueNode* next;
};
typedef struct QueueNode QueueNode;
//定义队列的结构
typedef struct Queue {QueueNode* phead;//对头QueueNode* ptail;//队尾int size;//有效的数据个数
}Queue;

其实数组也可以作为队列的底层结构,但是在数组头部插入、删除元素时间复杂度都为O(n),复杂度不是最好的。

2.栈的实现

//Queue.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>//定义结点的结构
typedef int QDataType;
struct QueueNode {QDataType data;struct QueueNode* next;
};
typedef struct QueueNode QueueNode;
//定义队列的结构
typedef struct Queue {QueueNode* phead;//对头QueueNode* ptail;//队尾int size;//有效的数据个数--稍后讲解
}Queue;//初始化
void QueueInit(Queue* pq);
//销毁
void QueueDestroy(Queue* pq);
//入队---队尾
void QueuePush(Queue* pq, QDataType x);
//出队---队头
void QueuePop(Queue* pq);
//取队头数据
QDataType QueueFront(Queue* pq);
//取队尾数据
QDataType QueueBack(Queue* pq);
//判断队列是否为空。为空,返回true;不为空,返回false
bool QueueEmpty(Queue* pq);
//队列有效元素个数
int QueueSize(Queue* pq);

(1)初始化

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

(2)销毁

别忘了最后把pheadptail置为NULL,不然pheadptail就是野指针!

在这里插入图片描述

//Queue.c
//销毁
void QueueDestroy(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;
}

(3)入队列

有两种可能:

  1. 队列为空,也就是指向队头的指针为空。pheadptail都指向新结点。
  2. 队列不为空,新结点作为队尾的后继结点。

每次入队,队列中的有效数据个数就会增加一个。

在这里插入图片描述

//入队列
void QueuePush(Queue* pq, QDataType 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 = newnode;}pq->size++;
}

错误写法:

在这里插入图片描述

当队列为空时,还会接着执行这段代码,这会导致最后一个结点的next指向newnode,但是newnode已经是最后一个结点了,会形成一个环。

(4)出队列

有两种可能:

  1. 队列中不止有一个结点
  2. 队列中只有一个结点

每次出队,队列中的有效数据个数就会减少一个。

在这里插入图片描述

//Queue.c
//出队---队头
void QueuePop(Queue* 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--;
}

(5)取队头/队尾数据

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

(6)队列有效元素个数

//Queue.c
//队列有效元素个数
int QueueSize(Queue* pq)
{return pq->size;
}

在队列结构中加上成员size可以减少不必要的麻烦,就比如实现“队列有效元素个数”,没有成员size代码就会很繁琐:

int QueueSize(Queue* pq)
{int size = 0;QueueNode* pcur = pq->phead;while (pcur){size++;pcur = pcur->next;}return size;
}
关键字:h5免费_怎么查询企业信息_seo搜索引擎是什么_2023年国际新闻大事件10条

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: