目录
本章主要讲解:
数据结构中的栈和队列的知识以及如何实现
栈,一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作 进行数据插入和删除操作的一端 称为栈顶,另一端称为栈底 栈中的数据元素遵守后进先出 LIFO ( Last In First Out )的原则
压栈:栈的插入操作叫做进栈 / 压栈 / 入栈, 入数据在栈顶 出栈:栈的删除操作叫做出栈, 出数据也在栈顶
栈的实现一般可以使用 数组或者链表实现 相对而言数组的结构实现更优一些(数组在尾上插入数据的代价比较小)
注:定长的静态栈实际中不实用,所以我们主要实现支持动态增长的数组栈
// 支持动态增长的栈
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);
动态数组栈具有三个元素:数组指针(指向开辟的空间),栈顶位置,栈的长度
//栈类型结构
typedef struct Stack
{
//数组栈(指向数组的指针)
STDataType* a;
//栈顶位置
int top;
//栈容量(数组长度)
int capacity;
}ST;
//栈初始化
void StackInit(ST* ps)
{
//避免传入空指针
assert(ps);
ps->a = NULL;
ps->top = 0;//定义top为栈最后数据的后一个位置
//也可以选择让top为当前最后数据的位置 则初始化top=-1;
ps->capacity = 0;
return;
}
注:动态开辟的空间结束时也需要进行销毁(避免内存泄漏)
//栈销毁
void StackDestroy(ST* ps)
{
//避免传入空指针
assert(ps);
free(ps->a);//释放开辟的数组栈空间
ps->a = NULL;//置空,避免造成野指针
}
//入栈
void StackPush(ST* ps, STDataType x)
{
assert(ps);
if (ps->top == ps->capacity)//栈满的情况
{
//如果原来容量为0则让新容量为4,否则为两倍
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
//调整数组栈大小(特别的:当数组指针为NULL时,realloc的作用和malloc的作用一样)
STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(ST) * newcapacity);
if (tmp == NULL)//tmp为NULL时则表示调整数组空间失败,那么就打印错误并结束进程
{
perror("realloc fail:");
exit(-1);
}
ps->a = tmp;
ps->capacity = newcapacity;
}
ps->a[ps->top] = x;//存入数据
ps->top++;//top位置更新
return;
}
//出栈
void StackPop(ST* ps)
{
//避免传入空指针
assert(ps);
//出栈到数据个数为0结束
if (StackEmpty(ps))
return;
ps->top--;//让top减减得到出栈的效果
return;
}
注:这里我们封装了一个判断空栈的函数便于调用
注:C语言没有定义bool类型(C99之前),要在C里面使用需要包含头文件 <stdbool.h>
//是否为空栈
bool StackEmpty(ST* ps)
{
//避免传入空指针
assert(ps);
return ps->top == 0;
}
注:这采用比较暴力的方式(断言),当然也可以选择if条件判断(比较温柔)
//获取栈顶数据
STDataType StackTop(ST* ps)
{
//避免传入空指针
assert(ps);
//空栈(top-1会越界访问)
assert(!StackEmpty(ps));//暴力断言不为空栈
return ps->a[ps->top - 1];//这里top-1才是栈顶数据的下标
}
//栈使用大小(存入数据个数)
int StackSize(ST* ps)
{
//避免传入空指针
assert(ps);
return ps->top;
}
void test()
{
ST st;
StackInit(&st);
StackPush(&st, 1);
StackPush(&st, 2);
StackPush(&st, 3);
StackPush(&st, 4);
printf("%d ", StackTop(&st));
StackPop(&st);
printf("%d ", StackTop(&st));
StackPop(&st);
StackPush(&st, 5);
StackPush(&st, 6);
while (!StackEmpty(&st))
{
printf("%d ", StackTop(&st));
StackPop(&st);
}
StackDestroy(&st);
}
队列,只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出FIFO(First In First Out)
入队列:进行插入操作的一端称为 队尾 出队列:进行删除操作的一端称为 队头
队列也可以数组和链表的结构实现,使用链表的结构实现更优一些(出队列效率低 )
//默认队列数据类型
typedef int QDataType;
//队列节点类型(链表队列)
typedef struct QueueNode
{
//址域
struct QueueNode* next;
//值域
QDataType data;
}QueueNode;
//队列类型(记录队头和队尾)
typedef struct Queue
{
QueueNode* head;//记录队列头结点地址
QueueNode* tail;//记录队列尾结点地址
// size_t _size;//记录队列数据个数(可有可无,自己选择)
}Queue;
//队列初始化
void QueueInit(Queue* pq);
//void QueueInit(QueueNode** pphead, QueueNode** pptail);
//队列销毁
void QueueDestroy(Queue* pq);
//入队列
void QueuePush(Queue* pq, QDataType x);
//出队列
void QueuePop(Queue* pq);
//队列头结点数据
QDataType QueueFront(Queue* pq);
//队列尾节点数据
QDataType QueueBack(Queue* pq);
//队列存入数据个数
int QueueSize(Queue* pq);
//判断空队列
bool QueueEmpty(Queue* pq);
首先我们是个链表队列,即需要创建节点类型 然后在队列常用到入栈和出栈操作(与头删和尾插相关),为了便于找到头结点和尾节点,这里创建一个队列结构体,类型成员为两个结点指针,用来记录头结点和尾节点地址
//默认队列数据类型
typedef int QDataType;
//队列节点类型(链表队列)
typedef struct QueueNode
{
//址域
struct QueueNode* next;
//值域
QDataType data;
}QueueNode;
//队列类型(记录队头和队尾)
typedef struct Queue
{
QueueNode* head;//记录队列头结点地址
QueueNode* tail;//记录队列尾结点地址
// size_t _size;//记录队列数据个数(可有可无,自己选择)
}Queue;
最开始没有数据,即头指针和尾指针都为NULL
//队列初始化
void QueueInit(Queue* pq)
{
//避免传入参数错误
assert(pq);
//初始化
pq->head = pq->tail = NULL;
return;
}
参考代码:
//队列销毁
void QueueDestroy(Queue* pq)
{
//避免传入参数错误
assert(pq);
//创建寻址指针
QueueNode* cur = pq->head;
while (cur)
{
//保存下个结点地址
QueueNode* next = cur->next;
//释放当前结点
free(cur);
//找到下一个结点
cur = next;
}
return;
}
//入队列
void QueuePush(Queue* pq, QDataType x)
{
//避免传入参数错误
assert(pq);
//创建结点并初始化
QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
newnode->data = x;
newnode->next = NULL;
//放入队尾
if (pq->head == NULL)//为空栈的特殊情况
{
pq->head = pq->tail = newnode;
}
else
{
pq->tail->next = newnode;//尾插
pq->tail = newnode;//记录新尾节点
}
return;
}
//出队列
void QueuePop(Queue* pq)
{
//避免传入参数错误
assert(pq);
//为空队列无法出队列
assert(!QueueEmpty(pq));
//保存下一个结点
QueueNode* next = pq->head->next;
//释放队列头
free(pq->head);
//队头更新
pq->head = next;
return;
}
//队列头结点数据
QDataType QueueFront(Queue* pq)
{
//避免传入参数错误
assert(pq);
//为空队列没有数据
assert(!QueueEmpty(pq));
return pq->head->data;
}
//队列尾节点数据
QDataType QueueBack(Queue* pq)
{
//避免传入参数错误
assert(pq);
//为空队列没有数据
assert(!QueueEmpty(pq));
return pq->tail->data;
}
//队列存入数据个数
int QueueSize(Queue* pq)
{
//避免传入参数错误
assert(pq);
int size = 0;
//遍历队列
QueueNode* cur = pq->head;
while (cur)
{
size++;
cur = cur->next;
}
return size;
}
注:同样的对于C语言使用布尔类型需要包含<stdbool.h>头文件
//判断空队列
bool QueueEmpty(Queue* pq)
{
//避免传入参数错误
assert(pq);
return pq->head == NULL;
}
void test()
{
Queue q;
QueueInit(&q);
QueuePush(&q, 1);
QueuePush(&q, 2);
QDataType front = QueueFront(&q);
printf("%d ", front);
QueuePop(&q);
QueuePush(&q, 3);
QueuePush(&q, 4);
while (!QueueEmpty(&q))
{
QDataType front = QueueFront(&q);
printf("%d ", front);
QueuePop(&q);
}
printf("\n");
}
对上述内容有什么问题记得留言呦~可以的话记得留下你的三连哈!~