数据结构-栈和队列
文章目录
一、栈
1.概念与结构
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则.
压栈: 栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈: 栈的删除操作叫做出栈。出数据也在栈顶。
栈底层结构选型
栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。
2.数组栈的实现
2.1 栈的结构定义
typedef int STDataType;
typedef struct Stack
{
STDataType* arr;
int top;
int capacity; //空间容量
}ST;
arr就是待开辟空间的指针。top可以有两种选择：一种是指向栈顶元素，另一种就是指向栈顶元素的下一个位置。现在我们定义一个栈的变量：
ST st;
2.2 栈的初始化
void STInit(ST* pst)
{
assert(pst != NULL);
pst->arr = NULL;
//pst->top = -1; //top指向栈顶元素
pst->top = 0; //top指向栈顶元素的下一个位置
pst->capacity = 0;
}
由于定义的是一个结构体变量st，要改变该结构体，就要传st的指针。所以要断言pst不能为空，开始先初始化数组的指针为空。对于top我们说过有两种定义方式：
当top初始化为-1时，说明top指向的是栈顶元素，top==-1时说明栈顶还没有存储元素。top==-1是数组第一个元素的前一个位置，是非法的：
当top初始化为0时，说明top指向的是栈顶元素的下一个位置，top==0时说明栈顶还没有数据：
capacity就是数组能存储的元素个数。
2.3 栈的销毁
void STDestroy(ST* pst)
{
assert(pst != NULL);
free(pst->arr);
pst->arr = NULL;
pst->top = pst->capacity = 0;
}
由于动态开辟的是一块连续的空间，所以释放空间很简单，直接free掉arr，再把arr置空，top和capacity赋值为0即可。pst仍然要断言不能为空。
2.4 栈的判空
bool STEmpty(ST* pst)
{
assert(pst != NULL);
return pst->top == 0;
}
判空就是判断栈顶是否有数据，初始化的top是为0的，说明top指向的是栈顶元素的下一个位置。所以如果表达式top==0为真，则返回true，否则返回false。
2.5 栈的入栈
void STPush(ST* pst,STDataType x)
{
assert(pst != NULL);
if (pst->top == pst->capacity)
{
int newCapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
STDataType* tmp = (STDataType*)realloc(pst->arr, newCapacity*sizeof(STDataType));
if (tmp == NULL)
{
perror("realloc fail!");
return NULL;
}
pst->arr = tmp;
pst->capacity = newCapacity;
}
pst->arr[pst->top++] = x;
}
由于top是指向栈顶元素的下一个位置，所以在压栈之前，要先判断数组是否满了，也就是当top==capacity时，要么是数组里还没有元素，要么就是数组存储满了。realloc就能实现空间的扩容。如果还没有开辟空间，那realloc的功能就相当于malloc。在压栈后，记得要把top往后挪一位，指向栈顶元素的下一个位置。
2.6 栈的出栈
void STPop(ST* pst)
{
assert(pst != NULL);
assert(!STEmpty(pst));
pst->top--;
}
由于栈的特点是后进先出，所以栈里元素的出栈，要从栈顶出元素才行。直接让top往前挪一位即可。但在删除栈顶元素之前要先判空。因为如果栈里没有元素，则不能进行出栈操作。
2.7 查看栈顶元素
STDataType STTop(ST* pst)
{
assert(pst != NULL);
assert(!STEmpty(pst));
return pst->arr[pst->top - 1];
}
在返回栈顶元素之前要先判断栈是否为空，不为空再返回栈顶的元素。注意：top是指向栈顶元素的下一个位置的，所以栈顶元素的位置是top-1。
2.8 栈的大小
int STSize(ST* pst)
{
assert(pst != NULL);
return pst->top;
}
栈的大小即数组中的有效元素个数。由于top是指向栈顶元素的下一个位置的，所以top刚好就可以表示数组中的有效元素个数。注意：如果一开始top是初始化为-1的话，那数组的有效元素个数就要返回top+1。
3.两种栈的图示结构
记住：栈的特点是后进先出(Last In First Out)，所以链式栈的进栈出栈要在头结点处进行。
🧳🧳栈就像箱子一样：往箱子里放东西会从箱底放起，直到放满；然后从箱子里取东西就要从箱顶开始取，否则你取不到箱底的东西。 这就是后进先出的意思。
代码仓库：Stack
二、队列
1.概念与结构
概念: 只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FlFO(First In First Out)的性质.
入队列: 进行插入操作的一端称为队尾
出队列: 进行删除操作的一端称为队头
队列底层结构选型
队列也可以使用数组或链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列要在数组头出数据，效率会比较低。
2.链式队列的实现
2.1 队列的结构定义
//1.节点结构
typedef int QDataType;
typedef struct QueueNode
{
QDataType data;
struct QueueNode* next;
}QNode;
//2.队列结构
typedef struct Queue
{
QNode* phead;
QNode* ptail;
int size;
}Queue;
队列的结构中只有三个成员，phead是用来指向链表的头的，ptail是用来指向链表的尾的。因为队列是先进先出的特点，所以链式队列是在队头出数据，在队尾进数据。有了phead和ptail指针就方便我们管理链表。size是链表的元素个数(节点个数)。
若现在创建了一个结构体变量：
Queue q;
2.2 队列的初始化
void QueueInit(Queue* pq)
{
assert(pq != NULL);
pq->phead = NULL;
pq->ptail = NULL;
pq->size = 0;
}
注意：我们创建的是一个结构体变量q，所以要改变该变量，就要传该变量的地址才行。所以要对pq进行断言不能为空。
2.3 队列的销毁
void QueueDestroy(Queue* pq)
{
assert(pq != NULL);
QNode* cur = pq->phead;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
pq->phead = pq->ptail = NULL;
pq->size = 0;
}
队列的销毁就是释放链表中的所有节点，然后要记得把phead和ptail置为空，size赋值为0。链式队列的销毁就跟单链表的销毁是一样的。
2.4 队列的判空
bool QEmpty(Queue* pq)
{
assert(pq != NULL);
return pq->phead == NULL
&& pq->ptail == NULL;
}
理论上如果链表为空，那phead和ptail都为空，但是两个一起判断更好，以免出啥bug。当然也可以通过判断size是否等于0来判断队列是否为空。
2.5 队列的入队
void QueuePush(Queue* pq, QDataType x)
{
assert(pq != NULL);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc fail!");
return;
}
newnode->data = x;
newnode->next = NULL;
if (pq->ptail == NULL)
{
assert(pq->phead == NULL);
pq->phead = pq->ptail = newnode;
}
else
{
pq->ptail->next = newnode;
pq->ptail = newnode;
}
pq->size++;
}
先创建一个新节点，然后需要判断此时队列是否为空，为空是一种情况，不为空也是一种情况。为空就让phead和ptail都指向newnode；不为空就要在尾结点ptail处进行尾插。数据入队后，记得要让size+1。
2.6 队列的出队
void QueuePop(Queue* pq)
{
assert(pq != NULL);
assert(!QEmpty(pq));
if (pq->phead->next == NULL)
{
free(pq->phead);
pq->phead = pq->ptail = NULL;
}
else
{
QNode* next = pq->phead->next;
free(pq->phead);
pq->phead = next;
}
pq->size--;
}
元素出队也是需要分类讨论的，如果队列为空就不能进行出队操作，所以要先判空。如果是队列中只有一个节点，那phead和ptail此时都指向这个节点，所以直接释放掉phead即可，但是要记得把两个指针都置空，否则会出现野指针。如果队列中不止一个节点，那直接在头结点phead处进行头删。出队一个元素，记得要让size-1。
2.7 查看队头元素
QDataType QueueFront(Queue* pq)
{
assert(pq != NULL);
assert(!QEmpty(pq));
return pq->phead->data;
}
如果队列为空，则链表为空，没有队头数据。所以要判先空。
2.8 查看队尾元素
QDataType QueueBack(Queue* pq)
{
assert(pq != NULL);
assert(!QEmpty(pq));
return pq->ptail->data;
}
查看队尾元素也是要先判断队列是否为空，队列为空就没有队尾元素。
2.9 队列的大小
int QueueSize(Queue* pq)
{
assert(pq != NULL);
return pq->size;
}
队列的大小就是队列中的元素个数(节点个数)size，返回size即可。
3.链式队列的图示结构
记住：队列的特点是先进先出(First In Fitst Out)，所以链式队列的入队要在链表的尾结点处尾插，而出队要在链表的头节点处头删。
⬅️🚶🚶♂️🚶♀️⬅️队列就像排队打饭一样：先来的同学会排在队伍的前面，而后来的同学会排在队伍的后面。排在最前面的同学会先打到饭离开队伍，而排在队伍后面的同学需要等待前面的同学离开了才能打到饭。这就是先进先出的意思。
代码仓库：Queue
原文地址：https://blog.csdn.net/m0_62183318/article/details/144987644
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！