数据结构——栈和队列

目录

栈

栈的基本知识

栈的实现

定义

各个接口的实现

队列

队列的基本知识

队列的实现

定义

各个接口的实现

---

栈

栈的基本知识

栈的定义

栈（Stack）是一种遵循后进先出（Last In First Out，LIFO）原则的数据结构。它的操作主要限制在数据结构的一端，称为栈顶（Top）。

压栈：栈的插入操作叫进栈\压栈\入栈，入数据在栈顶
出栈：栈的删除操作叫做出栈，出数据也在栈顶

基本特点

• 后进先出：最后添加到栈中的元素将是第一个被移除的元素。
• 限制性访问：只能在栈顶进行添加和删除操作。
• 动态大小：虽然传统的栈有固定大小，但现代编程语言通常提供动态栈，其大小可以随着元素的添加和移除而变化。

基本操作

1. Push：向栈顶添加一个新元素，使其成为新的栈顶。
2. Pop：移除栈顶元素，并返回它的值。
3. Peek/Top：查看栈顶元素的值，但不从栈中移除它。
4. IsEmpty：检查栈是否为空，即没有任何元素。
5. Size：获取栈中元素的数量。

适用场景

• 栈常用于管理函数调用的上下文，如递归调用和返回地址。
• 用于表达式求值，如算术表达式和逆波兰表达式。
• 用于回溯算法，如迷宫求解、图搜索等。
• 用于撤销操作（Undo操作）和恢复操作（Redo操作）。
• 用于括号匹配和语法分析。

栈的实现

• 数组实现：使用数组来存储栈的元素，并通过一个索引来追踪栈顶的位置。
• 链表实现：使用链表实现栈，允许在不需要移动其他元素的情况下动态地添加和删除元素。

相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小，而链表尾插每次都需要申请空间创建新的节点。

下面我们就用数组实现个动态栈。

定义

typedef int STDataType;typedef struct Stack
{STDataType* arr;int top;         //堆顶int capacity;    //容量（能容纳数据个数的最大数量）
}ST;

各个接口的实现

初始化

//初始化
void STInit(ST* pst)
{assert(pst);pst->arr = NULL;//指向栈顶数据的下一个位置pst->capacity = pst->top = 0;//指向栈顶数据//pst->top = -1
}

注意这里的top的指向，是指向堆顶数据的下一个位置，所以top也可以代表栈的数据个数。

入栈

//入栈
void STPush(ST* pst, STDataType x)
{assert(pst);//扩容if (pst->capacity == pst->top){int newcapacity = (pst->capacity == 0) ? 4  : 2 * pst->capacity;STDataType* tep = (STDataType*)realloc(pst->arr, newcapacity * sizeof(STDataType));if (tep == NULL){perror("realloc");return;}pst->arr = tep;pst->capacity = newcapacity;}pst->arr[pst->top] = x;pst->top++;}

这里的扩容需要注意，当pst->capacity == pst->top时，说明栈空间已经满了，需要扩容，一般是扩容2倍。

详细解释可以看数据结构——顺序表-CSDN博客中CheckCapacity函数的解释。

解决完扩容问题后，直接再top位置插入数据，并更新top就可以了。

出栈

移除栈顶元素，只需让top减减就行了。

注意判断栈不为空（top > 0）就可以了。

// 出栈
void STPop(ST* pst)
{assert(pst);assert(pst->top > 0);pst->top--;
}

取栈顶数据

top指向栈顶数据的下一位置，返回top-1的数据就行了。

还是要注意栈不为空。

//取栈顶数据
STDataType STTop(ST* pst)
{assert(pst);assert(pst->top > 0);return pst->arr[pst->top - 1];
}

判空

看的是数据个数为不为0（top == 0），不是看容量（capacity）

//判空 看的是数据个数为不为0，不是看容量
bool STEmpty(ST* pst)
{assert(pst);return (pst->top == 0);
}

获取栈的数据个数

top就是栈的数据个数，返回就好了。

//获取数据个数
int STSize(ST* pst)
{assert(pst);return (pst->top);
}

 销毁栈

用free释放掉申请的空间，然后把top和capacity置0就行了。

//销毁
void STDestroy(ST* pst)
{assert(pst);free(pst->arr);pst->arr = NULL;pst->capacity = pst->top = 0;
}

队列

队列的基本知识

队列的定义

队列（Queue）是一种遵循先进先出（First In First Out，FIFO）原则的线性数据结构。它在一端添加元素，在另一端移除元素。

基本特点

• 先进先出：最先添加到队列中的元素将是第一个被移除的元素。
• 两端操作：队列允许在一端（队尾）添加元素，在另一端（队首）移除元素。
• 有序性：元素保持它们被添加的顺序。

基本操作

1. Enqueue：在队尾添加一个新元素。
2. Dequeue：移除队首的元素，并返回它的值。
3. Peek/Front：查看队首元素的值，但不从队列中移除它。
4. IsEmpty：检查队列是否为空。
5. Size：获取队列中元素的数量。

适用场景

• 任务调度，如打印机任务队列。
• 缓冲区管理，如视频播放器的缓冲。
• 广度优先搜索（BFS）算法中管理待访问的节点。
• 模拟现实世界中的排队行为，如超市结账队伍。

队列的实现

• 数组实现：使用数组来存储队列的元素，需要两个指针或索引来分别追踪队首和队尾。
• 链表实现：使用链表来实现队列，允许在队尾添加和在队首删除元素，而不需要移动其他元素。
• 循环数组：使用固定大小的数组并通过模运算来实现队列的循环，避免在数组末尾重新分配空间。

 队列的实现使用链表结构比较好，因为涉及到头插头删，使用数组有数据挪动，效率较为低下。

下面我们就用链表去实现队列。

定义

队列的节点和队列结构

typedef int QDataType;typedef struct QueueNode
{struct QueueNode* next;QDataType val;
}QNode;typedef struct Queue
{QNode* phead;    //队列的头节点QNode* ptail;    //队列的尾节点int size;        //队列的数据个数
}Queue;

各个接口的实现

初始化

把phead和ptail置空，size置0即可。

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

插入数据到队尾（入队列）

创建一个新节点，然后尾插就行。

注意判断队列为空的情况就可以了。

// 队尾插入
void QueuePush(Queue* pq, QDataType x)
{assert(pq);//创建一个新节点，赋值xQNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");return;}newnode->next = NULL;newnode->val = x;//判断链表为空的情况if (pq->phead == NULL){pq->phead = pq->ptail = newnode;}else{pq->ptail->next = newnode;pq->ptail = newnode;}//更新sizepq->size++;
}

删除队头的元素（出队列）

删除队列头节点，跟链表的删除基本一模一样。

注意判断队列元素不为0，以及元素个数为1的情况。

// 队头删除
void QueuePop(Queue* pq)
{assert(pq);assert(pq->size != 0);//判断是不是一个节点，特殊处理if (pq->size == 1){free(pq->phead);pq->phead = pq->ptail = NULL;}else{QNode* next = pq->phead->next;free(pq->phead);pq->phead = next;}//更新sizepq->size--;
}

取队头队尾的数据

QDataType QueueFront(Queue* pq)
{assert(pq);assert(pq->phead);return pq->phead->val;
}QDataType QueueBack(Queue* pq)
{assert(pq);assert(pq->ptail);return pq->ptail->val;
}

队列数据个数

int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}

队列的判空

判断队列的数据个数为不为0就行了，或者判断phead为不为空也可以。

bool QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0;
}

销毁队列

遍历队列，逐个销毁

void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur = pq->phead;while (cur){QNode* del = cur;cur = cur->next;free(del);}pq->phead = pq->ptail = NULL;pq->size = 0;
}

---

拜拜，下期再见😏

摸鱼ing😴✨🎞