关注小庄 顿顿解馋૮(˶ᵔ ᵕ ᵔ˶)ა
💡个人主页：9ilk
💡专栏：数据结构之旅
上回我们学习了顺序表和链表，今天博主来讲解两个新的数据结构 — 栈和队列 ， 请放心食用
文章目录
- 🏠 栈
- 📒 何为栈
- 👿 栈后进先出是相对的
- 📒 栈的实现
- 🏠 队列
- 📒 何为队列
- 📒 队列的实现
🏠 栈
对于这么坨书，我们要拿到最下面的书是不是要最后才能拿到；而对于最上面的书它是最晚放上去的却能最先拿到，这样的一个场景就跟我们接下来要介绍的栈类似 — Last in First out(后进先出)
📒 何为栈
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
压栈：栈数据的插入操作叫做压栈/入栈/进栈，入数据在栈顶。
出栈：栈数据的删除操作叫做出栈，出数据也在栈顶。
👿 栈后进先出是相对的
由图中我们可知，栈的后进先出是对于同时在栈里的数据而言的
📒 栈的实现
通过前面的分析我们知道，我们需要一个栈顶来表示数据，这跟我们链表的头结点有点相似，但是对于单链表来说实现栈，尾部插入数据并不方便，因此我们选择数组实现栈
- 动态栈
typedef int Datatype;
typedef struct Stack
{
Datatype* arr;
int top;
int capacity;
}ST;
- 栈的初始化与销毁
//初始化
void StackInit(ST* ps)
{
assert(ps);
ps->arr = NULL;
ps->capacity = ps->top = 0;
}
关于top的初始化：1.top表示栈顶元素的下一个位置时，让top初始化为0，插入数据时先top后++ ；2.top表示栈顶元素 时，top初始化为-1，此时先++后再用top
// 销毁栈
void StackDestroy(ST* ps)
{
assert(ps);
free(ps->arr);
ps->arr = NULL;
ps->capacity = ps->top = 0;
}
- 栈的插入数据和删除数据
这里有了前面顺序表的基础就很简单了，不过要注意压栈和出栈都是在栈顶
//入栈
void StackPush(ST* ps, Datatype data)
{
assert(ps);
if (ps->capacity == ps->top)
{//扩容
int newcapacity = 0;
newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
Datatype* temp = (Datatype*)malloc(newcapacity * sizeof(Datatype));
if (temp == NULL)
{
perror("malloc failed");
return;
}
ps->arr = temp;
ps->capacity = newcapacity;
}
//入栈
ps->arr[ps->top++] = data;
}
//出栈
void StackPop(ST* ps)
{
assert(ps);
//栈不能为空
assert(ps->top != 0);
ps->top--;
}
- 获取栈顶元素
// 获取栈顶元素
Datatype StackTop(ST* ps)
{
assert(ps);
//栈不能为空
assert(ps->top != 0);
return ps->arr[ps->top - 1];
}
- 判断是否为空
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0
int StackEmpty(ST* ps)
{
assert(ps);
return ps->top == 0 ? 1 : 0;
}
- 获取栈中有效数据个数
// 获取栈中有效元素个数
int StackSize(ST* ps)
{
assert(ps);
return ps->top;
}
🏠 队列
栈是后进先出，那有我们的先进先出（First in First out）吗 ? 当然有，跟现实中我们排队买票一样，这样数据结构叫做队列
📒 何为队列
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头
📒 队列的实现
由于我们是先进先出，出在队头出，进在队尾进，所以我们需要两个“指针”front 和 rear 来标识位置有效率些。
那用数组来实现好还是链表呢？
用数组的话不好出数据，所以我们这里推荐用链表实现；同时我们可以将front和rear封装进一个结构体这样比较省事
- 队列结构
typedef int Datatype;
typedef struct QNode
{
Datatype data;
struct QNode* next;
}QNode;
typedef struct Quque
{
QNode* head;
QNode* tail;
int size;
}Quque;
注：我们可以定义一个size表示数据个数，弥补链表需要循环遍历确定数据个数的缺陷
- 队列的初始化和销毁
//队列的初始化和摧毁
void QuqueInit(Quque* pq)
{
assert(pq);
pq->size = 0;
pq->head = pq->tail = NULL;
}
void QuqueDestroy(Quque* pq)
{
assert(pq);
QNode* cur = pq->head;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
pq->head = pq->tail = NULL;
pq->size = 0;
}
- 入队和出队
出队就是链表的头删 入队就是尾插
//队列的入队列和出队列
void QuquePop(Quque* pq)
{
assert(pq);
assert(pq->head != NULL);//对嘞不能为空
//0个结点
//1个结点
if (pq->head->next == NULL)
{
free(pq->head);
pq->head = pq->tail = NULL;
}
else
{
QNode* next = pq->head->next;
free(pq->head);
pq->head = next;
}
pq->size--;
}
void QuquePush(Quque* pq, Datatype x)
{
assert(pq);
//申请新结点
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc failed");
return;
}
newnode->data = x;
newnode->next = NULL;
if (pq->head == NULL)
{//0个结点
pq->head = pq->tail = newnode;
}
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}
pq->size++;
}
- 获取头元素和尾元素
//队列的头元素和尾巴元素
Datatype QuqueFront(Quque* pq)
{
assert(pq);
assert(pq->head != NULL);
return pq->head->data;//设置两个指针进结构体的好处
}
Datatype QuqueBack(Quque* pq)
{
assert(pq);
assert(pq->head != NULL);
return pq->tail->data;//设置两个指针进结构体的好处
}
- 队列是否为空
//队列是否为空
bool QuqueEmpty(Quque* pq)
{
assert(pq);
if (pq->size == 0)
{
return true;
}
else
{
return false;
}
}
- 队列有效数据个数
//队列数据个数
int QuqueSize(Quque* pq)
{
assert(pq);
return pq->size;
}
本次分享到这就结束咯，下次我们将讲解链表，栈和队列的OJ题，敬请期待 ~
