? ? ? ?在《数据结构与算法篇》的前面四讲中，博主为大家详细分析了顺序表、链表(包括单链表和带头双向循环链表)的原理分析，接下来的这一讲在前面的基础上，带着大家详细分析栈和队列相关特性。
1、栈
1.1 栈基本概念和组成结构
1.1.1 基本概念
? ? ? ?栈是一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。其中进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的元素遵循后进先出(Last in First Out)的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据发生在栈顶位置。
出栈：栈的删除操作叫做出栈，出数据同样发生在栈顶。
1.1.2 组成结构
1.2 栈的实现方式的选择
? ? ? ? 通过上面的示意图可以发现栈的实现一般可以使用数组或者链表实现，但可以看出，发生在栈中的入数据和出数据都是在栈顶位置，而且栈顶位置是实时变化的，
? ? ? ? 根据栈的后进先出特性，利用单链表每次都需要遍历链表然后才能找到尾部位置，就类似单链表的尾删，程序执行效率低下；
? ? ? ? 如果使用数组，就可以通过数组下标直接访问尾部元素，就可以很快的实现栈顶元素的插入和删除，利用数组实现相比单链表实现代价会比较小。因此在下文的分析中，我们选择用数组方式也就是前面已经讲解过的顺序表实现栈的功能。
1.3 栈的具体实现思路
1.3.1 总体组成框架
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
//栈：先进后出，数据从栈顶进入，从栈顶取出
//栈的功能可以用数组表示
//创建结构体
typedef int STDataType;
typedef struct Stack
{
STDataType*a;
//记录栈顶的位置
int top;
//记录容量
int capacity;
}ST;
//初始化栈结构体
void StackInit(ST*ps);
//清空栈中元素，销毁栈
void StackDestory(ST*ps);
//入数据：压栈
void StackPush(ST*ps, STDataType x);
//出栈
void StackPop(ST*ps);
//判断栈是否为空
bool StackEmpty(ST*ps);
//求栈中元素的大小
int StackSize(ST*ps);
//取栈顶元素
STDataType StackTop(ST*ps);
1.3.2 栈顶元素结构体创建
typedef int STDataType;
typedef struct Stack
{
STDataType*a;
//记录栈顶的位置
int top;
//记录容量
int capacity;
}ST;1.3.3 栈的初始化
#define _CRT_SECURE_NO_WARNINGS
#include"stack.h"
//初始化栈结构体
void StackInit(ST*ps)
{
assert(ps);
ps->a = NULL;
ps->top = 0;
ps->capacity = 0;
}1.3.4 清空栈中组成元素(销毁栈中元素)
#define _CRT_SECURE_NO_WARNINGS
#include"stack.h"
void StackDestory(ST*ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->capacity = ps->top = 0;
}1.3.5 压栈
#define _CRT_SECURE_NO_WARNINGS
#include"stack.h"
//入数据：压栈
void StackPush(ST*ps, STDataType x)
{
//压栈：后进先出
assert(ps);
if (ps->capacity == ps->top)
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
STDataType*tmp = (STDataType*)realloc(ps->a,sizeof(STDataType)*newcapacity);
if (tmp == NULL)
{
printf("reallco fail\n");
exit(-1);
}
ps->a = tmp;
ps->capacity = newcapacity;
}
ps->a[ps->top] = x;
//存入数据以后，top会向后++；
ps->top++;
}1.3.6 出栈
#define _CRT_SECURE_NO_WARNINGS
#include"stack.h"
//当取出栈顶元素后，top--
void StackPop(ST*ps)
{
assert(ps);
assert(!StackEmpty(ps));
ps->top--;
}1.3.7 栈是否为空判断函数
#define _CRT_SECURE_NO_WARNINGS
#include"stack.h"
//判断栈是否为空
bool StackEmpty(ST*ps)
{
assert(ps);
//即判断栈顶top是否为0，如果为0，说明栈已经为空
return ps->top == 0;
}1.3.8 求栈中元素个数
#define _CRT_SECURE_NO_WARNINGS
#include"stack.h"
//求栈中元素的大小
int StackSize(ST*ps)
{
assert(ps);
return ps->top;
}1.3.9 取栈顶元素
#define _CRT_SECURE_NO_WARNINGS
#include"stack.h"
//取栈顶元素
STDataType StackTop(ST*ps)
{
assert(ps);
assert(!StackEmpty(ps));
//出栈：相当于取数据，此时top的数据要向前减1方可取出对应的数据
return ps->a[ps->top - 1];
}2、队列
2.1 队列基本概念和组成结构
2.1.1 基本概念
? ? ? ? 队列是一种只允许在一端进行插入数据操作，在另外一端进行删除数据操作的特殊线性表，队列具有先进先出(First In First Out)的特性。
入队列：进行插入数据的一端称之为队尾；
出队列：进行删除操作的一端称之为队头；
2.1.2 组成结构
?
2.2 队列实现方式的选择
? ? ? ?通过上面的示意图我们可以看到：队列可以用数组或者链表的结构实现，但由于队列是先进先出特性，所以如果使用数组，在出队列时相当于就是把数组的首元素位置取出，然后数组后面的元素依次向前补位，这样的话，每取出一个数据，则后面所有的数据都需要补位一次，这样程序的效率就会很低下；
? ? ? ?但是如果是使用链表的话，每一次取数据相当于就是取出链表的头结点，然后将下一个结点当作新的头节点，这种效率相比用数组实现会更优一些。为此后面的分析我们借助前面章节分析的链表工作特性展开。
2.3 队列的具体实现思路
2.3.1 总体实现框架
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
//队列：先进先出
typedef int QDataType;
typedef struct QueueNode
{
struct QueueNode*next;
QDataType data;
}Qnode;
typedef struct Queue
{
Qnode*head;
Qnode*tail;
}Queue;
//初始化队列
void QueueInit(Queue*pq);
//清空队列
void QueueDestory(Queue*pq);
//入数据
void QueuePush(Queue*pq, QDataType x);
//将首元素移除队列，队列总数减1；
void QueuePop(Queue*pq);
//取队列头元素
QDataType QueueFront(Queue*pq);
//取尾部元素
QDataType QueueBack(Queue*pq);
//判断队列是否为空
bool QueueEmpty(Queue*pq);
//求解队列元素个数
int Queuesize(Queue*pq);
2.3.2 定义队列结构体
//队列：先进先出
typedef int QDataType;
typedef struct QueueNode
{
struct QueueNode*next;
QDataType data;
}Qnode;
typedef struct Queue
{
Qnode*head;
Qnode*tail;
}Queue;2.3.3 队列初始化
#define _CRT_SECURE_NO_WARNINGS
#include"Queue.h"
//初始化队列
void QueueInit(Queue*pq)
{
assert(pq);
pq->head = pq->tail = NULL;
}2.3.4 清空队列(队列销毁)
//清空队列
void QueueDestory(Queue*pq)
{
assert(pq);
Qnode*cur = pq->head;
while (cur)
{
Qnode*next = cur->next;
free(cur);
cur = next;
}
pq->head = pq->tail = NULL;
}2.3.5 队尾入队列
//入数据
void QueuePush(Queue*pq, QDataType x)
{
assert(pq);
Qnode*newnode = (Qnode*)malloc(sizeof(Qnode));
if (newnode == NULL)
{
printf("malloc fail\n");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
if (pq->tail == NULL)
{
pq->head = pq->tail = newnode;
}
else
{
pq->tail->next = newnode;
//tail一直标记最后一个元素的位置
pq->tail = newnode;
}
}2.3.6 队头出队列
void QueuePop(Queue*pq)
{
assert(pq);
assert(!QueueEmpty(pq));
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;
}
}2.3.7 获取队列头部元素
//取队列头元素
QDataType QueueFront(Queue*pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->head->data;
}2.3.8 获取队列队尾元素
//取尾部元素
QDataType QueueBack(Queue*pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->tail->data;
}2.3.9?获取队列有效元素个数
//求解队列元素个数
int Queuesize(Queue*pq)
{
assert(pq);
Qnode*cur = pq->head;
int sz = 0;
while (cur)
{
cur = cur->next;
sz++;
}
return sz;
}2.3.10?检测队列是否为空
//判断队列是否为空
bool QueueEmpty(Queue*pq)
{
assert(pq);
return pq->head == NULL;
}3、总结
? ? ? ? 今天这一讲主要在基于前面带着大家所学的顺序表和链表相关知识的补充与提升，为大家详细对比分析了栈和队列的相关特性组成，具体的原理实现大家可以通过阅读博主提供的代码进行详细阅读，博主就不带着大家再逐一展开分析了。制作不易，欢迎大家点赞、支持、关注！！！