一、栈
栈的概念及结构
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶
出栈：栈的删除操作叫做出栈。出数据也在栈顶
栈的实现
栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。
顺序表可以把使用的空间写成固定值，也可以构建动态开辟内存；但是如果写成固定的数组形式当存的数据满了就不能再使用了，所以下面我们实现的是动态开辟内存的形式。
所以我们先创建一个顺序表结构体类型，结构体类型中有指针，下标，容量。 指针： 用来维护在堆上连续的一段空间， 下标：表示数据存放到哪一个位置了，因为数据只能一个接着一个地存放，要有个下标来记录我数据放到哪一个位置了。 容量：与下标相比较，当下标与容量相等就表示空间存储满了，要进行扩容处理。 创建类型如下：
typedef int STDataType; //对int类型重新起个名字叫DataType
//创建一个栈结构体类型
struct Stack
{
STDataType* a; //数据的指针
int top; //栈顶
int capacity; //记录开辟空间的最大下标处
};
//对顺序表类型struct Stack类型重新起个名字叫SL
typedef struct Stack ST;
栈内存布局
栈的接口实现
1.栈的初始化和销毁
栈的初始化和销毁都与顺序表类似，这里就不再详细解释，只是顺序表中的size(有效元素个数)，换成了这里的栈顶。
//初始化变量st
void StackInit(ST* ps)
{
ps->a = NULL;
ps->capacity = 0;
ps->top = 0;
}
//栈的销毁
void StackDestroy(ST* ps)
{
free(ps->a);
ps->a = NULL;
ps->top = 0;
ps->capacity = 0;
}
2.入栈
与顺序表一样，增加元素时必须先判断容量是否足够，容量不够时需扩容。
这里的入栈和顺序表的尾插一样。
//入栈
void StackPush(ST* ps, STDataType x)
{
assert(ps);
//内存满了要扩容
if (ps->capacity == ps->top)
{
ps->capacity = ps->capacity > 0 ? ps->capacity * 2 : 2;
STDataType* tmp =
(STDataType*)realloc(ps->a,sizeof(STDataType) * ps->capacity);
if (tmp == NULL)
{
perror("erron ");
exit(-1);
}
ps->a = tmp;
}
//没有满就直接在后面入栈
ps->a[ps->top] = x;
ps->top++;
}
3.栈销毁
//栈销毁函数
void StackDestroy(ST* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->capacity = ps->top = 0;
}
4.出栈
出栈即尾删，删除元素需判断栈是否为空，空栈不能出栈。
判断栈是否为空在下面实现。
//出栈函数
void StackPop(ST* ps)
{
assert(ps);
assert(ps->top>0);
ps->top--;
}
5.获取栈顶元素
栈顶元素即顺序表中最后一个元素，直接根据下标即可找到。
当然栈不能为空。
//取栈顶部函数
STDataType StackTop(ST* ps)
{
assert(ps);
assert(!StackEmpty(ps));
return ps->a[ps->top - 1];
}
6.栈大小
//栈大小函数
int StackSize(ST* ps)
{
assert(ps);
return ps->top;
}
7.遍历栈打印
while (!StackEmpty(&stack))
{
printf("%d ", StackTop(&stack));
StackPop(&stack);
}
二、队列
队列的概念和结构
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)的性质。队列：进行插入操作的一端称为队尾
出队列： 进行删除操作的一端称为队头
入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为队头
队列的实现思路
队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。
而链表我们采用双向链接结构，一个指针来维护头节点，一个指针维护尾部节点
定义的结构体类型如下：
typedef int QDataType;
//创建一个结点型结构体
typedef struct QueueNode
{
struct QueueNode* next;
QDataType data;
}QueueNode;
//创建一个队列
typedef struct Queue
{
QueueNode* head;
QueueNode* tail;
}Queue;
队列的内存布局图
队列接口实现
1.初始化和销毁
初始化：初始化只需将两个指针置为NULL。
销毁：同链表一样，保存下一个结点地址，释放当前结点，直到指针为NULL。
//初始化队列
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = NULL;//有了头指针就不用二级指针来维护了
pq->tail = NULL;
}
//队列销毁
void QueueDestroy(Queue* pq)
{
assert(pq);
QueueNode* cur = pq->head;
while (cur != NULL)
{
QueueNode* next = cur->next;
free(cur);
cur = next;
}
pq->head = NULL;
pq->tail = NULL;
}
2.入队
入队和单链表的尾插一样，只是这里更简单，这里不需要找尾。
注意：
- 队列为空。
- 队列不为空。
//入队函数
void QueuePush(Queue* pq, QDatatype x)
{
assert(pq);
QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
newnode->data = x;
newnode->next = NULL;
if (!pq->head)
pq->head = pq->tail = newnode;
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}
}
3.出`队
和单链表头删一样，保存第二个结点地址释放，队头位置。
注意：队列不能为空。
//出数据，类似链表的头删
void QueuePop(Queue* pq)
{
assert(pq);
//要保证队列不能为空
assert(pq->head != NULL);
QueueNode* next = pq->head->next;
free(pq->head);
pq->head = next;
//防止野指针出现，当队列为空时要把tail指针置为空
if (pq->head == NULL)
{
pq->tail = NULL;
}
}
4.取队头数据
返回队头元素即可。
//取队头数据
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(pq->head != NULL);
return pq->head->data;
}
5.取队尾数据
返回队尾元素即可。
QDataType QueueBack(Queue* pq)
{
assert(pq);
//同样要检验队列不能为空
assert(pq->head != NULL);
return pq->tail->data;
}
6.获取队列元素个数
//获取队列元素个数
int QueueSize(Queue* pq)
{
assert(pq);
int count = 0;
QueueNode* cur = pq->head;
while (cur != NULL)
{
count++;
cur = cur->next;
}
return count;
}
7.判断队列是否为空
直接判断头指针是否为空，就可判断队列是否为空。
//判断队列是否为空
bool QueueEmpty(Queue* pq)
{
return pq->head == NULL;
}
