文章目录
前言
继上篇博客，已经把链表的有关习题完成，链表也已经收尾啦。
今天来学习新的数据结构——栈和队列，fellow me
一、栈
1.1 概念与结构
栈：⼀种特殊的线性表，其只允许在固定的⼀端进⾏插⼊和删除元素操作。进⾏数据插⼊和删除操作的⼀端称为栈顶，另⼀端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
压栈：栈的插⼊操作叫做进栈/压栈/⼊栈，⼊数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
我们要用什么来实现栈这个数据结构呢？
前面我们学习了顺序表和链表，感觉两者都行，仔细想想，还是用顺序表来实现，也就是数组，因为数组在尾上的插入更优一些，更加贴合后进后出的特殊性。
1.2 栈的实现
关于栈的实现，主要是入栈和出栈的操作，以及取栈顶元素。
既然用顺序表来实现，想必大家已经熟练操作了，跟着我来实现这些函数吧
typedef int STDataType;
//定义栈的数据结构
typedef struct Stack
{
STDataType* arr;
int top; //指向栈顶位置
int capacity; //容量
}ST;
void STInit(ST* ps); // 栈的初始化
void STDestroy(ST* ps); // 栈的销毁
void STPush(ST* ps, STDataType x); //入栈--栈顶
void STPop(ST* ps); //出栈--栈顶
STDataType STTop(ST* ps); //取栈顶元素
bool STEmpty(ST* ps); //栈是否为空
int STSize(ST* ps); //获取栈中有效元素个数
void STPrint(ST* ps); // 打印 栈
老样子，实现一个东西，必然是要初始化，想必大家已经对这代码再也熟悉不过了。
void STInit(ST* ps) // 初始化
{
assert(ps);
ps->arr = NULL;
ps->capacity = ps->top = 0;
}
入栈和出栈也大相径庭，这里就没有单独写扩容函数了，因为栈的实现只有入栈需要插入数据
void STPush(ST* ps, STDataType x) // 入栈 以及容量的扩展的获取
{
assert(ps);
if (ps->top == ps->capacity) // 容量不够，扩容
{
int newcapacity = ps->top == 0 ? 4 : ps->capacity * 2;
STDataType* tmp = (STDataType*)realloc(ps->arr, sizeof(STDataType) * newcapacity);
ps->capacity = newcapacity;
ps->arr = tmp;
}
ps->arr[ps->top++] = x; // 直接在数组的末尾赋值就好
}
在出栈之前，肯定是要判断数组是否为空的
bool STEmpty(ST* ps) // 判断栈是否为空
{
assert(ps);
return ps->top == 0;
}
你没有看错，出栈就是这么简单
void STPop(ST* ps) // 出栈
{
assert(!STEmpty(ps));
ps->top--; // 只接让top--即可
}
后面就是取栈顶元素和有效元素个数了
STDataType StackTop(ST* ps) // 取栈顶元素
{
assert(!STEmpty(ps));
return ps->arr[ps->top - 1]; // top代表元素个数 所以要返回下标为top减一的数据
}
int STSize(ST* ps) // 获取栈的元素个数
{
assert(ps);
return ps->top;
}
再写一个打印函数，方便测试的时候观察数据处理过程
void STPrint(ST* ps) // 打印 测试函数
{
assert(ps);
for (int i = 0; i < ps->top; i++)
{
cout << ps->arr[i] << ' ';
}
cout << endl;
}
最后就是销毁栈了。
void STDestroy(ST* ps) /// 有借有还 再借不难
{
if (ps->arr != NULL)
free(ps->arr);
ps->arr = NULL;
ps->capacity = ps->top = 0;
}
下面来测试测试我这个栈实现的在怎么样吧，话不多说，上图。
基本上是没什么问题的，栈的实现就结束啦
二、队列
2.1 概念与结构
概念：只允许在⼀端进⾏插⼊数据操作，在另⼀端进⾏删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)
⼊队列：进⾏插⼊操作的⼀端称为队尾
出队列：进⾏删除操作的⼀端称为队头
队列这个数据结构，我感觉还是链表结构实现更好一些，因为涉及到出队列，如果使用顺序表的话，出队列需要整体往前移，效率太低。
我们把链表的头设为队列的头，链表的尾设置为队尾。入队列就尾插，出队列就头删。
想到这些，那队列的实现岂不是 洒洒水 啦。
2.2 队列的实现
关于队列的实现，无非就是入队和出队列以及获取队头、队尾的元素。
用链表来实现，大家也应该不陌生，毕竟上一篇可是对链表又熟练了一些。
一起来实现队列吧
typedef int QDataType;
typedef struct QueueNode // 队列内每个元素用链式结构 一个一个结点连接
{
QDataType data;
struct QueueNode* next;
}QueueNode;
typedef struct Queue // 队列
{
QueueNode* phead; // 队头
QueueNode* ptail; // 队尾
int size;
}Queue;
void QueueInit(Queue* pq); // 队列初始化
void QueuePush(Queue* pq, QDataType x); // 入队
void QueuePop(Queue* pq); // 出队
bool QueueEmpty(Queue* pq); // 判空函数
QDataType QueueFront(Queue* pq); // 获取对头元素
QDataType QueueBack(Queue* pq); // 获取队尾元素
int QueueSize(Queue* pq); // 队内有效元素
void QueueDestory(Queue* pq); // 销毁队列
void QueuePrint(Queue* pq); // 打印 方便测试代码
先来个初始化
void QueueInit(Queue* pq) // 队列初始化
{
assert(pq);
pq->phead = pq->ptail = NULL;
pq->size = 0;
}
简简单单的入队操作
void QueuePush(Queue* pq, QDataType x) // 入队
{
assert(pq);
QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode)); // 获取新结点
newnode->data = x;
newnode->next = NULL;
if (pq->phead == NULL)
{
pq->phead = pq->ptail = newnode; // 第一次入队情况
}
else
{
pq->ptail->next = newnode;
pq->ptail = pq->ptail->next; // 和尾插一样
}
pq->size++;
}
在出队实现之前，还是老样子，先来一个判空函数
bool QueueEmpty(Queue* pq) // 判空函数
{
assert(pq);
return pq->size == 0;
}
出队来咯，是不是和头删大相径庭呢
void QueuePop(Queue* pq) // 出队
{
assert(pq);
if (pq->phead == pq->ptail)
{
free(pq->phead);
pq->phead = NULL;
}
else
{
QueueNode* node = pq->phead;
pq->phead = pq->phead->next;
free(node);
node->next = NULL;
}
--pq->size;
}
入队和出队都觉得轻轻松松，接下来就是取队头队尾元素了，感觉没有难度嘛。
QDataType QueueFront(Queue* pq) // 获取对头元素
{
assert(!QueueEmpty(pq));
return pq->phead->data;
}
QDataType QueueBack(Queue* pq)// 获取队尾元素
{
assert(!QueueEmpty(pq));
return pq->ptail->data;
}
最后就是方便测试的打印队列、队内有效元素以及销毁队列了
int QueueSize(Queue* pq) // 队内有效元素
{
assert(pq);
return pq->size;
}
void QueuePrint(Queue* pq) // 打印 方便测试代码
{
assert(pq);
QueueNode* pcur = pq->phead;
while (pcur)
{
cout << pcur->data << ' ';
}
cout << endl;
}
void QueueDestory(Queue* pq) // 销毁队列
{
assert(pq);
QueueNode* pcur = pq->phead;
while (pcur)
{
QueueNode* next = pcur->next;
free(pcur);
pcur = next;
}
pq->phead = pq->ptail = NULL;
}
至此，队列的实现就完成啦，接下来就是测试代码咯。
测试是没什么问题的，队列就完结啦。
总结
感觉学过了顺序表和链表之后，实现栈和队列感觉轻轻松松。
有了前面的基础，感觉今天的内容让我爽歪歪，今天的学习就到这里了
下一篇博客让我们来迎接栈和队列的习题吧，小编持续更新中
