队列和栈数据结构

目录

一、栈的概念

二、栈的实现

2.1 栈的初始化

2.2 栈的销毁

2.3 栈的插入

2.4 栈的出栈

2.5 取栈顶

2.6 取栈中有效元素个数

2.7 判断栈是否为空

三、队列的概念

四、队列的实现

4.1 队列结构体定义

4.2 队列的初始化        

4.3 队列的销毁

4.4 入队列

4.5 出队列

4.6 取队头数据

4.7 取队尾数据

4.8 队列判空

4.9 队列中有效元素个数

五、总结与反思（优缺点以及用法）

---

一、栈的概念

        ⼀种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进⾏数据插⼊和删除操作的⼀端称为栈顶，另⼀端称为栈底。归根结底就是先进后出。底层结构是数组也可以是链表，但是方便访问和节约空间，这里选择数组。因此选择数组的物理结构和逻辑结构都是线性的。

二、栈的实现

2.1 栈的初始化

定义一个栈结构

//栈结构
typedef char STDataType;
typedef struct Stack
{STDataType* arr;int top;int capacity;
}ST;

//初始化
void StackInit(ST* Stack)
{Stack->arr = NULL;Stack->capacity = Stack->top = 0;
}

2.2 栈的销毁

//销毁栈
void StackDestory(ST* Stack)
{if (Stack->arr)free(Stack->arr);Stack->arr = NULL;Stack->capacity = Stack->top = 0;
}

2.3 栈的插入

//入栈
void StackPush(ST* Stack, STDataType x)
{assert(Stack);//空间不够if (Stack->capacity == Stack->top){//扩容int newcapacity = Stack->capacity == 0 ? 4 : 2 * Stack->capacity;STDataType* tmp = (STDataType*)realloc(Stack->arr, newcapacity * sizeof(STDataType));if (tmp == NULL){perror("realloc");exit(1);}Stack->arr = tmp;Stack->capacity = newcapacity;}//空间够Stack->arr[Stack->top++] = x;
}

2.4 栈的出栈

//出栈
void StackPop(ST* Stack)
{assert(!StackEmpty(Stack));--Stack->top;
}

2.5 取栈顶

//获取栈顶元素
STDataType StackTop(ST* Stack)
{assert(!StackEmpty(Stack));return Stack->arr[Stack->top - 1];
}

2.6 取栈中有效元素个数

//获取栈中元素个数
int StackSize(ST* Stack)
{assert(!StackEmpty(Stack));return Stack->top;
}

2.7 判断栈是否为空

//判断
bool StackEmpty(ST* Stack)
{assert(Stack);return Stack->arr==NULL;
}

三、队列的概念

        只允许在⼀端进性插入数据操作，在另⼀端进行删除数据操作的特殊线性表。队列满足先进先出就行，它底层既可以用数组，也可以用链表，各有各的优缺点，链表的尾删和尾插这些时间复杂度是o（N），但是这些缺点可以通过一些列办法弥补回来，所以这里队列底层是用的链表。

四、队列的实现

4.1 队列结构体定义

        为了弥补链表尾删和尾插时间复杂度为o(N)这一缺陷，这里可以定义2个结构体，一个结构体用来结点内元素的结构体，另一个结构体是用来标记头结点（这里没有头结点，只是为了理解，设置的头结点，里面有数据。ps：头结点没有数据）和尾结点用于保存尾节点，方便访问和插入删除尾结点。

//结点结构
typedef struct QueueNode
{QDataType data;struct QueueNode* next;
}QueueNode;//队列结构
typedef struct Queue
{QueueNode* phead;QueueNode* ptail;//int size;
}Queue;

4.2 队列的初始化    

//初始化
void QueueInit(Queue* pq)
{assert(pq);pq->phead = pq->ptail = NULL;//pq->size = 0;
}

4.3 队列的销毁

//销毁
void QueueDestroy(Queue* pq)
{assert(pq);QueueNode* pcur = pq->phead;while (pcur){QueueNode* next = pcur->next;free(pcur);pcur = next;}pq->phead = pq->ptail = NULL;//pq->size = 0;
}

4.4 入队列

//入队
void QueuePush(Queue* pq,QDataType x)
{assert(pq);//创建结点QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));if (newnode == NULL){perror("malloc");exit(1);}newnode->data = x;newnode->next = NULL;if (pq->phead == NULL){pq->phead = pq->ptail = newnode;}else{pq->ptail->next = newnode;pq->ptail = newnode;}//pq->size++;
}

4.5 出队列

//出队
void QueuePop(Queue* pq)
{assert(!QueueEmpty(pq));if (pq->phead == pq->ptail){free(pq->phead);pq->phead = pq->ptail = NULL;}else{QueueNode* next = pq->phead->next;free(pq->phead);pq->phead = next;}//pq->size--;
}

4.6 取队头数据

//取队头元素
QDataType QueueFront(Queue* pq)
{assert(!QueueEmpty(pq));return pq->phead->data;
}

4.7 取队尾数据

//取队尾元素
QDataType QueueBack(Queue* pq)
{assert(!QueueEmpty(pq));return pq->ptail->data;
}

4.8 队列判空

//判空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->phead == NULL;
}

4.9 队列中有效元素个数

//队列元素个数
int QueueSize(Queue* pq)
{assert(!QueueEmpty(pq));int size = 0;while (pq->phead){pq->phead = pq->phead->next;size++;}return size;//return pq->size;
}

五、总结与反思（优缺点以及用法）

        栈：

优点	缺点
操作简单，插入删除这些时间复杂度都是o（1）	内存浪费（需要向内存动态申请空间）
内存管理方便（避免插入和删除移动数据）	局限性（只能访问栈顶数据，无法访问其他数据）
适用于递归（栈在递归函数调用中非常有用，因为每次函数调用都会在栈中创建新的栈帧，函数返回时会自动释放 ）	空间限制（空间不够，还需要用编程手段开辟空间使用）
应用场景： 括号匹配：使用栈可以有效地解决括号匹配问题 表达式求值：栈可以用于将中缀表达式转换为后缀表达式，并进行求值 递归调用：栈在递归函数调用中用于存储函数的局部变量和返回地址

        队列：

优点	缺点
顺序处理（队列能够按顺序处理数据，非常适合需要按顺序处理任务的场景，如任务调度、打印队列等）	访问限制（只能在一段添加元素，在另一端移除元素，无法访问中间元素）
实现代码简单（用的链表）
动态调整（内存方面，链表可以动态调整大小，不受固定容量限制）
应用场景： 广度优先搜索：在图的遍历中，广度优先搜索使用队列来存储待访问的节点。 任务调度：操作系统中的任务调度器使用队列来管理待执行的任务。 消息队列：在分布式系统中，消息队列用于在不同服务之间传递消息。