目录
- 什么是栈
- 栈的结构图示
- 栈的实现
- 创建栈的结构体
- 初始化栈
- 入栈
- 出栈
- 获取栈顶元素
- 获取栈中有效元素个数
- 检测栈是否为空
- 栈的销毁
- 什么是队列？
- 队列的实现
- 创建队列结构体
- 初始化队列
- 队尾入队列
- 队头出队列
- 获取队列头部元素
- 获取队列尾部元素
- 获取队列中元素个数
- 检测队列是否为空
- 销毁队列
什么是栈
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素的操作。进行数据插入和删除的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守先进后出LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
栈的结构图示
栈的实现
栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。
创建栈的结构体
我们用栈来存储数据，首先需要实现一个动态增长的栈。所以我们先创建一个栈的结构体。
typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top; //栈顶
int capacity; //容量
}Stack;
初始化栈
初始化栈的方式有很多种，我们可以根据不同的需求来选择。这里写一种常规的。
void StackInit(Stack* ps)
{
assert(ps);//检测传过来的ps是否为空
ps->a = NULL;//把a标识的这块空间先置为空
ps->top = ps->capacity = 0;
}
入栈
一开始top为0标识栈顶的位置，所以我们要先将数据放入栈顶，在让top向后走一位。
void StackPush(Stack* ps, STDataType x)
{
assert(ps);//检测ps是否为空
//如果空间满了，我们需要扩容
if (ps->capacity == ps->top)//判断空间是否满了的条件
{
int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//指定新空间的大小
ps->a = (STDataType*)realloc(ps->a, newCapacity*sizeof(STDataType));//进行扩容
if (ps->a == NULL)//扩容失败
{
printf("realloc fail\n");
exit(-1);//终止程序
}
ps->capacity = newCapacity;//让其标识新的空间的大小
}
ps->a[ps->top] = x;//将数据放入栈
ps->top++;//top向后走一步
}
出栈
void StackPop(Stack* ps)
{
assert(ps);
if (ps->top > 0)//避免栈里面数据已经删除完了，top依旧向下减为负数
{
--ps->top;
}
}
获取栈顶元素
STDataType StackTop(Stack* ps)
{
assert(ps);
assert(ps->top > 0);//保证下标为正
return ps->a[ps->top - 1];//返回栈顶元素
}
获取栈中有效元素个数
int StackSize(Stack* ps)
{
assert(ps);
return ps->top;
}
检测栈是否为空
检测栈是否为空，如果为空返回非零结果，如果不为空则返回0.
bool StackEmpty(Stack* ps)
{
assert(ps);
return ps->top == 0;//如果条件成立就返回真，否则就为假（不为空）
}
栈的销毁
void StackDestroy(Stack* ps)
{
assert(ps);
free(ps->a);//释放开辟的这一块空间
ps->a = NULL;
ps->top = ps->capacity = 0;
}
什么是队列？
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO（First In First Out）入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为对头。
队列的实现
队列也可以用数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。
创建队列结构体
我们使用链表来实现队列，我们需要创建一个存储队列信息的结构体。
typedef int QDataType;
//链式结构：表示队列
typedef struct QueueNode
{
QDataType data; //存储数据
struct QueueNode* next; //指针域
}QNode;
//队列的结构
typedef struct Queue
{
QNode* head;//标识队头的位置
QNode* tail;//标识队尾的位置
}Queue;
初始化队列
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = pq->tail = NULL;//将两个指针置为空
}
队尾入队列
让一个数据进入队列，我们只需要用链表结构来实现队列，在队尾进行尾插数据就可以了。
如果队列为空，需要单独处理一下。
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));//申请一个新的结点
assert(newnode);//检测结点是否申请成功
newnode->data = x;//
newnode->next = NULL;
if (pq->tail == NULL)//如果队列为空的情况
{
assert(pq->head==NULL);
pq->tail = pq->head = newnode;
}
else//队列不为空的情况
{
pq->tail->next = newnode;//尾插一个新结点
pq->tail = newnode;//更新尾的位置
}
}
队头出队列
当队列为空，没有存储数据时，我们就不能够出数据。如果队列中只有一个结点，那么我们需要对其单独处理，否则就会出现错误。
void QueuePop(Queue* pq)
{
assert(pq);
assert(pq->head && pq->tail);//保证队列中有数据在往下走
if (pq->head->next == NULL)//如果队列里面只有一个数据的情况
{
free(pq->head);//释放队头数据
pq->head = pq->tail = NULL;//将队列的头指针和尾指针均置为空
}
else
{
QNode* next = pq->head->next;//让next指向队头结点的下一个结点
free(pq->head);//释放队头结点
pq->head = next;//让head指向next结点
}
}
获取队列头部元素
检测队列是否为空，如果不为空则直接返回队列头指针指向的元素。
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(pq->head);//检测队列是否为空
return pq->head->data;//返回队列头部元素
}
获取队列尾部元素
检测队列是否为空，如果不为空则直接返回队列尾指针指向的元素。
//获取队列队尾元素
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(pq->tail);//检测队列是否为空
return pq->tail->data;//返回队列尾部元素
}
获取队列中元素个数
可以对队列进行遍历，统计元素个数，如果队列比较长那么这个方法效率就比较低。如果想要效率比较高，那么我们可以在定义队列结构体的时候加上一个size变量，每往队列里面入一个数据就统计一下，那么我们需要队列中元素个数的时候就可以直接返回。
int QueueSize(Queue* pq)
{
assert(pq);
QNode* cur = pq->head;//让cur指向队头的元素
size_t size = 0;//定义一个无符号的size变量用来计数
while (cur)//cur不为空则进入循环继续执行
{
size++;//size=size+1
cur = cur->next;//继续向后遍历
}
return size;//返回有效元素个数
}
检测队列是否为空
检测队列是否为空，如果为空返回非零结果，如果非空返回0
bool QueueEmpty(Queue* pq)
{
assert(pq);
return (pq->head == NULL) && (pq->tail == NULL);
}
销毁队列
在使用完队列之后，我们应该对其进行销毁，防止造成内存泄漏。
void QueueDestroy(Queue* pq)
{
assert(pq);
QNode* cur = pq->head;
while (cur)
{
QNode* next = cur->next;//定义一个next指向cur的下一个结点
free(cur);//释放cur
cur = next;
}
pq->head = pq->tail = NULL;//将头尾指针均置为空
}
评论(0)