栈
栈的基本概念栈是一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
出栈和入栈的操作如下：
他们都只能从栈顶进行出栈和进栈操作，所以栈要遵守先进后出的原则
栈的先进先出原则如下：
栈的实现栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。所以我们在这里选择用数组来实现栈。
数组栈的结构图：
下面我们就用数组来是具体实现栈的增删查改等操作
头文件如下：
代码语言：javascript代码运行次数：0运行复制#include
#include
#include
#include
typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top; // 栈顶
int capacity; // 容量
}Stack;
// 初始化栈
void StackInit(Stack* ps);
// 入栈
void StackPush(Stack* ps, STDataType data);
// 出栈
void StackPop(Stack* ps);
// 获取栈顶元素
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数
int StackSize(Stack* ps);
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0
int StackEmpty(Stack* ps);
// 销毁栈
void StackDestroy(Stack* ps);创建栈首先我们在这里将int作为本次栈的数据类型
我们还要定义一个结构体里面有数组，栈顶元素的下标的+1和栈的容量（栈里面的最多元素个数）
代码语言：javascript代码运行次数：0运行复制typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top; //
int capacity; //
}Stack;栈的初始化栈的初始化就比较简单了，直接将top和容量置为0，并且把数组置为空
代码语言：javascript代码运行次数：0运行复制void StackInit(Stack* ps)
{
assert(ps);
ps->top = 0;
ps->capacity = 0;
ps->a = NULL;
}栈的销毁栈的销毁同样很简单，将数组free掉，防止出现野指针，同时置空，然后容量和栈顶元素下标置为0
代码语言：javascript代码运行次数：0运行复制void StackDestroy(Stack* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->capacity = 0;
ps->top = 0;
}判断栈是否为空在后面的增删查改等操作我们需要断言，为了增加代码的可读性，我们直接写一个函数 ，更加容易理解，如果栈顶元素下标为0，那么这个栈就为空 ，所以直接return top等于 0这个表达式的值，为空则返回 1，不为空则返回0
代码语言：javascript代码运行次数：0运行复制int StackEmpty(Stack* ps)
{
assert(ps);
return ps->top == 0;
}数据进栈数据进栈是从栈顶入，我们首先要判断这个 栈是否已满，如果满了的话那么栈顶的下标就和容量相等，对于top和capacity的不理解的可以看这个图，top的意思如下图：
当capacity和top相等时其实是有两种情况的，一种时为空，另一种是栈满，，我们在这里就用一个三目操作符，如果为0，就将capacity初始化为4，否则将capacity的原来的值乘2，然后动态开辟realloc一块新的空间，大小就是newcapacity，这样我们就完成了扩容
然后我们将新空间temp给数组a
最后直接把插入的数据data给a[top]，同时top++
代码语言：javascript代码运行次数：0运行复制void StackPush(Stack* ps, STDataType data)
{
if (ps->top == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
STDataType* temp = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));
if (temp == NULL)
{
perror("realloc");
return;
}
ps->capacity = newcapacity;
ps->a = temp;
}
ps->a[ps->top] = data;
ps->top++;
}数据出栈出栈及其简单，直接先判断栈是否为空，然后将top–即可
代码语言：javascript代码运行次数：0运行复制void StackPop(Stack* ps)
{
assert(ps);
assert(!StackEmpty(ps));
ps->top--;
}获取栈顶元素栈顶元素的下标其实就是top-1，所以直接返回a[top-1]
代码语言：javascript代码运行次数：0运行复制STDataType StackTop(Stack* ps)
{
assert(ps);
assert(!StackEmpty(ps));
return ps->a[ps->top - 1];
}获取栈内的元素个数栈内元素个数就是top的值，栈为空top为0
代码语言：javascript代码运行次数：0运行复制int StackSize(Stack* ps)
{
assert(ps);
return ps->top;
}栈的实现就完成了，完整代码如下：
代码语言：javascript代码运行次数：0运行复制typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top; // ջ
int capacity; //
}Stack;
void StackInit(Stack* ps)
{
assert(ps);
ps->top = 0;
ps->capacity = 0;
ps->a = NULL;
}
void StackDestroy(Stack* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->capacity = 0;
ps->top = 0;
}
int StackEmpty(Stack* ps)
{
assert(ps);
return ps->top == 0;
}
void StackPush(Stack* ps, STDataType data)
{
if (ps->top == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
STDataType* temp = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));
if (temp == NULL)
{
perror("realloc");
return;
}
ps->capacity = newcapacity;
ps->a = temp;
}
ps->a[ps->top] = data;
ps->top++;
}
void StackPop(Stack* ps)
{
assert(ps);
assert(!StackEmpty(ps));
ps->top--;
}
STDataType StackTop(Stack* ps)
{
assert(ps);
assert(!StackEmpty(ps));
return ps->a[ps->top - 1];
}
int StackSize(Stack* ps)
{
assert(ps);
return ps->top;
}队列栈的基本概念队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)
入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为队头
队列的实现队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。
这里我们就用列表的结构来实现队列
头文件如下：
注意，这里我们定义了两个结构体，，第一个结构体其实只是链表的结构，里面有一个next一个data，第二个则是队列的结构，一个队头（出数据）指针，一个队尾指针（进数据），还有一个队列的大小
代码语言：javascript代码运行次数：0运行复制#include
#include
#include
#include
// 链式结构：表示队列
typedef int QDataType;
typedef struct QListNode
{
struct QListNode* next;
QDataType data;
}QNode;
// 队列的结构
typedef struct Queue
{
QDataType size;
QNode* front;
QNode* rear;
}Queue;
// 初始化队列
void QueueInit(Queue* q);
// 队尾入队列
void QueuePush(Queue* q, QDataType data);
// 队头出队列
void QueuePop(Queue* q);
// 获取队列头部元素
QDataType QueueFront(Queue* q);
// 获取队列队尾元素
QDataType QueueBack(Queue* q);
// 获取队列中有效元素个数
int QueueSize(Queue* q);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
int QueueEmpty(Queue* q);
// 销毁队列
void QueueDestroy(Queue* q);队列的初始化初始目前以及是熟能生巧了，很简单，size置为0，头尾指针置为空即可
代码语言：javascript代码运行次数：0运行复制void QueueInit(Queue* q)
{
assert(q);
q->size = 0;
q->front = q->rear = NULL;
}队列的销毁队列的销毁我们需要花点功夫理解一下：
因为队列有多个节点，全部都要free掉 ，不然就可能会出现野指针的问题，所以我们在这里用一个while循环，将cur置为头指针，将next置为cur的next，这样当前cur的next就不会丢失。首先我们把cur给free掉，然后将cur置为next继续操作，直到cur为空，然后将front和rear置为空，size置为0即可。
代码语言：javascript代码运行次数：0运行复制void QueueDestroy(Queue* q)
{
assert(q);
QNode* cur = q->front;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
q->front = q->rear = NULL;
q->size = 0;
}判断队列是否为空和栈一样，提高代码的可读性，如果size=0，其实队列就为空，但是头尾指针都为空时也可以，为空时返回1，不为空时返回0
代码语言：javascript代码运行次数：0运行复制int QueueEmpty(Queue* q)
{
assert(q);
return q->front == NULL && q->rear == NULL;
/*return q->size == 0;*/
}队列数据插入要插入一个数据我们首先要做的就是开辟有一个新的链表节点，然后将他的next置为空，data置为你要插入的数据
插入数据分为两种情况，链表为空和不为空
链表为空时直接将front和rear置为新节点newnode同时size++
链表不为空时就将front的next置为newnode，rear置为newnode同时size++
代码语言：javascript代码运行次数：0运行复制void QueuePush(Queue* q, QDataType data)
{
assert(q);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc");
return;
}
newnode->data = data;
newnode->next = NULL;
if (q->rear == NULL)
{
assert(q->front == NULL);
q->front = q->rear = newnode;
}
else
{
q->rear->next = newnode;
q->rear = newnode;
}
q->size++;
}队列数据删除队列的删除我们就要判断队列是否为空，为空就不能删除了
同样的有两种情况：
链表只有一个节点时直接将头尾指针都置为空即可，size–
链表有多个节点时就将front的next置为front，size–
代码语言：javascript代码运行次数：0运行复制void QueuePop(Queue* q)
{
assert(q);
assert(!QueueEmpty(q));
if (q->rear == q->front)
{
free(q->front);
q->front = q->rear = NULL;
}
else
{
QNode* next = q->front->next;
free(q->front);
q->front = next;
}
q->size--;
}获取队头数据获取队头的元素 ，直接返回头指针的data即可
代码语言：javascript代码运行次数：0运行复制QDataType QueueFront(Queue* q)
{
assert(q);
assert(!QueueEmpty(q));
return q->front->data;
}获取队尾数据获取队尾元素 同样简单，直接返回rear的data即可
代码语言：javascript代码运行次数：0运行复制QDataType QueueBack(Queue* q)
{
assert(q);
return q->rear->data;
}求队列元素个数直接返回size的值即可
代码语言：javascript代码运行次数：0运行复制int QueueSize(Queue* q)
{
assert(q);
return q->size;
}队列的实现就完成了
完整代码如下：
代码语言：javascript代码运行次数：0运行复制void QueueInit(Queue* q)
{
assert(q);
q->size = 0;
q->front = q->rear = NULL;
}
void QueueDestroy(Queue* q)
{
assert(q);
QNode* cur = q->front;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
q->front = q->rear = NULL;
q->size = 0;
}
int QueueEmpty(Queue* q)
{
assert(q);
return q->front == NULL && q->rear == NULL;
/*return q->size == 0;*/
}
void QueuePush(Queue* q, QDataType data)
{
assert(q);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc");
return;
}
newnode->data = data;
newnode->next = NULL;
if (q->rear == NULL)
{
assert(q->front == NULL);
q->front = q->rear = newnode;
}
else
{
q->rear->next = newnode;
q->rear = newnode;
}
q->size++;
}
void QueuePop(Queue* q)
{
assert(q);
assert(!QueueEmpty(q));
//һڵʱ
if (q->rear == q->front)
{
free(q->front);
q->front = q->rear = NULL;
}
//ڵ
else
{
QNode* next = q->front->next;
free(q->front);
q->front = next;
}
q->size--;
}
QDataType QueueFront(Queue* q)
{
assert(q);
assert(!QueueEmpty(q));
return q->front->data;
}
QDataType QueueBack(Queue* q)
{
assert(q);
return q->rear->data;
}
int QueueSize(Queue* q)
{
assert(q);
return q->size;
}好了，今天的分享到这里就结束了，谢谢大家的支持！