目录
一、栈
1.栈的基本概念
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。
进行数据插入和删除操作的一端
称为栈顶，另一端称为栈底。
栈中的数据元素遵守后进先出
LIFO
（
Last In First Out
）的原则。
压栈：栈的插入操作叫做进栈
/
压栈
/
入栈，
入数据在栈顶
。
出栈：栈的删除操作叫做出栈。
出数据也在栈顶
。
2.如何实现一个栈
1.>用数组实现一个可以动态增长的栈（建议）
此时的入栈和出栈操作只需要在数组尾部进行操作，但需要考虑到数组的大小可能发生变化。
这时我们就需要设计一个可以动态增长的数组。
// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{
STDataType* _a;
int _top; // 栈顶
int _capacity; // 容量
}Stack;
2.>栈的链式存储
?链栈是指采用链式存储结构实现的栈。通常链栈用单链表来表示，如上图所示。链栈的节点结构与单链表的结构相同。
//------链栈的存储结构------
typedef struct StackNode
{
Eletype data;
struct StackNode *next;
}StactNode, *LinkStack;3.栈的基本操作
1.>栈的创建
栈的基本结构;包含了保存数据用的数组，栈的容量以及栈的栈顶
// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{
STDataType* _a;
int _top; // 栈顶
int _capacity; // 容量
}Stack;2.>栈的初始化
void StackInit(Stack* ps){
assert(ps);
ps->_a = (STDataType*)malloc(sizeof(STDataType)* 3);
if (NULL == ps->_a){
assert(0);
return;
}
ps->_capacity = 3;
ps->_top = 0;
}3.>入栈操作
因为是用数组实现的栈，所以需要考虑数组满了的情况，则在进行入栈操作之前需要先对栈是否满了进行判断，如果满了则需要进行新空间的申请。
//如果栈满了则需要进行新空间的申请
void BuySize(Stack*ps){
//1.申请新空间
int newsize = (ps->_capacity) * 2;
STDataType*new_a = (STDataType*)malloc(sizeof(STDataType)*newsize);
if (NULL==new_a){
assert(0);
return ;
}
//2.数据的拷贝
new_a = (STDataType*)memcpy(new_a, ps->_a, ps->_capacity);
//3.释放旧空间
free(ps->_a);
ps->_a = new_a;
//4.新空间的使用
ps->_capacity = newsize;
}
void StackInit(Stack* ps){
assert(ps);
ps->_a = (STDataType*)malloc(sizeof(STDataType)* 3);
if (NULL == ps->_a){
assert(0);
return;
}
ps->_capacity = 3;
ps->_top = 0;
}
//栈满的判断
static int StactFull(Stack*ps){
return ps->_capacity == ps->_top;
}
// 入栈
void StackPush(Stack* ps, STDataType data){
if (StactFull(ps))
{
//如果栈满了则需要扩容
BuySize(ps);
}
ps->_a[ps->_top] = data;
ps->_top++;
}
4.>出栈操作
出栈需要先对栈是否为空进行判断
// 出栈
void StackPop(Stack* ps){
if (StackEmpty(ps))
{
return;
}
ps->_top--;
}5.>获取栈顶元素
这里也需要进行栈空的判断
// 获取栈顶元素
STDataType StackTop(Stack* ps){
assert(!StackEmpty(ps));
return ps->_a[ps->_top-1];
}6.>栈空的判断
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0
int StackEmpty(Stack* ps){
assert(ps);
return 0==ps->_top;
}7.>栈的销毁
// 销毁栈
void StackDestroy(Stack* ps){
assert(ps);
free(ps->_a);
ps->_a = NULL;
ps->_capacity = 0;
ps->_top = 0;
}二、队列
1.队列的基本概念
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出
FIFO(First In First Out)
入队列：进行插入操作的一端称为
队尾
出队列：进行删除操作的一端称为
队头
?
2.如何实现一个基本队列
1.>顺序队的实现
用数组来实现一个队列，定义两个“指针”指向队列的头和尾，从而进行队列的基本操作。
//------队列的顺序存储结构------
#define MAXQSIZE
typedef struct
{
QElemType *base; //存储空间的基地址
int front; //头指针
int rear; //尾指针
}sqQueue;?2.>链队的实现?
?链队的基本结构：需要两个指针分别指向链表的头结点和尾结点
// 链式结构：表示队列
typedef struct QListNode
{
struct QListNode* _pNext;
QDataType _data;
}QNode;
// 队列的结构
typedef struct Queue
{
QNode* _front;
QNode* _rear;
}Queue;3.>循环队列的实现
因为普通的顺序队存在假溢出的问题
这时就有大佬提出了循环队列：?
?由上图可以判断队满和队空的条件是相同的
?
3.队列的基本操作（链式结构）
1.>队列的创建
typedef int QDataType;
// 链式结构：表示队列
typedef struct QListNode
{
struct QListNode* _next;
QDataType _data;
}QNode;
// 队列的结构
typedef struct Queue
{
QNode* _front;
QNode* _rear;
}Queue;2.>队列的初始化
// 初始化队列
void QueueInit(Queue* q)
{
q->_front = NULL;
q->_rear = NULL;
}3.>队尾入队
这时需要先判断队列是否为空，因为如果队列为空则头指针也需要修改
void QueuePush(Queue* q, QDataType data)
{
if (QueueEmpty(q))
{
q->_front = q->_rear = ByeNode(data);
}
else
{
q->_rear->_next = ByeNode(data);
q->_rear = q->_rear->_next;
}
}4.>队头出队
需要先判断是否有元素可出
// 队头出队列
void QueuePop(Queue* q)
{
assert(q);
if (QueueEmpty(q))
{
return;
}
QNode*cur = q->_front;
q->_front = cur->_next;
free(cur);
}5.>判断队列是否为空
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
int QueueEmpty(Queue* q)
{
return q->_front == NULL;
}6.>获取队列队尾元素
// 获取队列队尾元素
QDataType QueueBack(Queue* q)
{
assert(q);
return q->_rear->_data;
}7.>获取队列队头元素
// 获取队列头部元素
QDataType QueueFront(Queue* q)
{
assert(q);
return q->_front->_data;
}8.>获取队列中元素的个数
// 获取队列中有效元素个数
int QueueSize(Queue* q)
{
assert(q);
int size = 0;
QNode*cur = q->_front;
while (cur)
{
cur = cur->_next;
size++;
}
return size;
}9.>队列销毁
// 销毁队列
void QueueDestroy(Queue* q)
{
if (QueueEmpty(q))
{
q = NULL;
return;
}
QNode *cur = q->_front;
while (cur)
{
q->_front = cur->_next;
free(cur);
cur = q->_front;
}
q->_rear = NULL;
q = NULL;
}