目录
栈
栈的基本知识
栈的实现
定义
各个接口的实现
队列
队列的基本知识
队列的实现
定义
各个接口的实现
栈
栈的基本知识
栈的定义
栈(Stack)是一种遵循后进先出(Last In First Out,LIFO)原则的数据结构。它的操作主要限制在数据结构的一端,称为栈顶(Top)。
压栈:栈的插入操作叫进栈\压栈\入栈,入数据在栈顶
出栈:栈的删除操作叫做出栈,出数据也在栈顶
基本特点
- 后进先出:最后添加到栈中的元素将是第一个被移除的元素。
- 限制性访问:只能在栈顶进行添加和删除操作。
- 动态大小:虽然传统的栈有固定大小,但现代编程语言通常提供动态栈,其大小可以随着元素的添加和移除而变化。
基本操作
- Push:向栈顶添加一个新元素,使其成为新的栈顶。
- Pop:移除栈顶元素,并返回它的值。
- Peek/Top:查看栈顶元素的值,但不从栈中移除它。
- IsEmpty:检查栈是否为空,即没有任何元素。
- 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)原则的线性数据结构。它在一端添加元素,在另一端移除元素。
基本特点
- 先进先出:最先添加到队列中的元素将是第一个被移除的元素。
- 两端操作:队列允许在一端(队尾)添加元素,在另一端(队首)移除元素。
- 有序性:元素保持它们被添加的顺序。
基本操作
- Enqueue:在队尾添加一个新元素。
- Dequeue:移除队首的元素,并返回它的值。
- Peek/Front:查看队首元素的值,但不从队列中移除它。
- IsEmpty:检查队列是否为空。
- 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😴✨🎞