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

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

一、栈

1.概念与结构

（1）概念

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

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

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

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

（2）底层结构

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

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

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

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

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

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

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

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

2. 单链表中定义栈的结构，根据结构体对齐，每插入一个数据，都要向操作系统申请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）销毁

别忘了最后把phead、ptail置为NULL，不然phead、ptail就是野指针！

//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. 队列为空，也就是指向队头的指针为空。phead、ptail都指向新结点。
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;
}