一.栈
1.栈的概念
栈是一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除的一端称为栈顶,另一端称为栈底。栈里的元素遵循后进先出的原则。简单的说就相当于一个羽毛球筒,我们把羽毛球放进羽毛球筒,当我们想要把羽毛球一个一个的拿出来,那么我们第一个放进去的羽毛球就是我们最后拿出来的。
2.栈的实现
栈既可以用数组来实现,也可以用链表来实现,这两种方式各有所优:
使用链表实现栈的优点是可以动态地分配和释放内存空间,不受固定大小的限制。当栈的大小不确定或者需要频繁的push和pop操作时,链表实现更加灵活和高效。
使用数组实现栈的优点是空间效率高,不会浪费额外的存储空间。当栈的大小已经确定且不会变化,且需要高效的访问和操作时,数组实现更加合适。
先把栈的结构放在这里,方便后面的代码理解:
typedef int STDataType;
typedef struct stack
{
STDataType* a;//用数组来实现栈
int capacity;//栈的容量
int top;//栈顶
}ST;
2.1栈的初始化
void STInit(ST* pst)
{
assert(pst);
pst->a = NULL;
pst->capacity = 0;
//在后面往栈里面放元素的时候,最后的top是在栈顶的下一个位置
pst->top = 0;
//如果是-1,那么代表的就是下标
//pst->top = -1;
}
这里需要解释一下,上面代码写的关于top为0还是-1的问题。因为在后面我们要进行入栈的操作,而每一次的入栈都需要让top加一,使top跟着栈顶的移动而移动。所以top如果是0,那么在刚开始栈里是没有元素的,那么top就在数组下标为0的位置,随着入栈,top开始递增。同理的,如果top为-1的话,刚开始top的位置就是数组下标的位置。
2.2栈的销毁
void STDestory(ST* pst)
{
free(pst->a);
pst->a = NULL;
pst->capacity = pst->top = 0;
}
普通的释放掉就行了。
2.3入栈
//入栈
void STPush(ST* pst, STDataType x)
{
assert(pst);
if (pst->top == pst->capacity)//如果top的数值刚好等于栈的总容量,那么栈就是满了,包含为0的情况。
{
int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * newcapacity);//用realloc改变我们申请动态存储空间的大小
if (tmp == NULL)
{
perror("STPush::relloc");
return;
}
pst->a = tmp;//成功改变了空间,就赋值给栈里的a。
pst->capacity = newcapacity;//总体的容量也随之变化。
}
pst->a[pst->top] = x;
pst->top++;//因为我们的top的栈顶的位置,所以在每一次赋值完毕后就递增。
}
因为我们是用数组实现,所以入栈时先判断栈是不是满的或者是不是空的。如果栈满了,我们就用realloc来增容,增容之后再赋值。如果栈没有满,直接赋值就行了。
2.4出栈
//出栈
void STPop(ST* pst)
{
assert(pst);
assert(pst->top > 0);
pst->top--;
}
因为top的位置是栈顶的下一个位置,出栈实际上就是删除栈顶元素,这里我们直接把top的值递减就行了。还有就是需要注意,我们的第二个断言,我们的top一定要是大于0的,这里加个断言可以很方便我们找到错误。
2.5读取栈顶元素
//读取栈顶元素
STDataType STTop(ST* pst)
{
assert(pst);
assert(pst->top > 0);
return pst->a[pst->top-1];
}
在我们出栈之前如果我们需要读取栈顶元素,最好不要在主函数里读取,最好是单独写一个函数来调用,加个断言也可以很好的避免错误。
2.6判空
//判空
bool STEmpty(ST* pst)
{
assert(pst);
return pst->top == 0;
}
判空的意思是栈里也没有元素了,如果有返回false,没有的话返回true。
2.7获取数据个数
//获取数据个数
int STSize(ST* pst)
{
assert(pst);
return pst->top;
}
这个也很好理解,top就是数据个数,直接返回就行了。
3.代码分享
Stack.h:
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int STDataType;
typedef struct stack
{
STDataType* a;
int capacity;
int top;
}ST;
//初始化和销毁
void STInit(ST* pst);
void STDestory(ST* pst);
//入栈和出栈
void STPush(ST* pst, STDataType x);
void STPop(ST* pst);
//取栈顶元素
STDataType STTop(ST* pst);
//判空
bool STEmpty(ST* pst);
//获取数据个数
int STSize(ST* pst);
text.c
#include"Stack.h"
int main()
{
ST s;
STInit(&s);//初始化
STPush(&s, 1);//入栈
STPush(&s, 2);
STPush(&s, 3);
STPush(&s, 4);
STPush(&s, 5);
while (!STEmpty(&s))//栈里元素不为空就进入循环
{
printf("%d ", STTop(&s));
STPop(&s);
}
STDestory(&s);//摧毁栈
return 0;
}
然后就是上面写的栈的实现,想要的小伙伴自取。
二.队列
1.队列的概念
只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,它的特性跟栈相反,它是先进先出,进行插入的一端称为队尾,进行删除的一端称为队头。
如图所示:
2.队列的实现
队列同样也可以用数组和链表来表示,但是用数组的话再出队列的时候就很不方便了,因为它进和出的地方是反的,如果用数组它的效率会很低。
同样的,我先把队列的结构放在这里
typedef int QDataType;
typedef struct QueueNode
{
struct QueueNode* next;
QDataType a;
}QNode;
我们不妨先思考一下,我们在进行单链表的增删查改的时候,我们用到的东西都有什么?比如:如果我们对形参的改变需要影响实参的时候,我们需要二级指针。在尾插的时候,我们需要找尾。同样的,我们在实现这个队列的时候我们也需要这些东西,那么这些东西,我们是不是可以单独的分装到一个新的结构体。
typedef struct Queue
{
QNode* phead;
QNode* ptail;
int size;
}Queue;
这个结构体的作用相当于是一个功能性的东西,解决我们的二级指针的问题,还有首尾指针的问题。 这里的size可以方便我们统计队里的数据个数。
2.1队列的初始化
void QueueInit(Queue* pq)
{
assert(pq);
pq->phead = pq->ptail = NULL;
pq->size = 0;
}
初始化就把头尾指针都置为NULL,size为0就行了。
2.2队列的销毁
void QueueDestroy(Queue* pq)
{
assert(pq);
QNode* pcur = pq->phead;
while (pcur)
{
QNode* next = pcur->next;//把下一个节点提前保存起来
free(pcur);
pcur = pcur->next;//指针往后移动
}
pq->phead = pq->ptail = NULL;//全部释放完毕后注意指针也要置为NULL
pq->size = 0;
}
实际上也就是单链表的销毁,遍历整个数组,逐个释放就行了。
2.3队列插入
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("QueuePush::malloc");
return;
}
newnode->a = x;
newnode->next = NULL;
if (pq->ptail == NULL)
{
pq->phead = pq->ptail = newnode;
}
else
{
pq->ptail->next = newnode;
pq->ptail = pq->ptail->next;
}
pq->size++;
}
我们往队列里插入数据的位置是固定的(尾插),在函数内部我们需要创建新节点,然后对我们的队列进行判空,随后进行插入数据。
2.4队头删除
void QueuePop(Queue* pq)
{
assert(pq);
assert(pq->size != 0);
// 一个节点
if (pq->phead->next == NULL)
{
free(pq->phead);
pq->phead = pq->ptail = NULL;
}
else // 多个节点
{
QNode* next = pq->phead->next;
free(pq->phead);
pq->phead = next;
}
pq->size--;
}
这个函数需要注意是就是在进行释放时,释放最后一个节点了,我们需要把phead和ptail都置为NULL,当然这里只是一种写法。
2.5取队头元素
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(pq->phead);
return pq->phead->a;
}
这里就只需要注意一下,既然我们要取元素了,那么队里一定要有数据。
2.6取队尾元素
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(pq->ptail);
return pq->ptail->a;
}
跟2.5同样的道理。
2.7获取数据个数
int QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}
此时我们结构体里的size就起到了作用。
2.8判空
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->size == 0;
}
这个其实就跟上面的栈的判空一个道理了。
3.代码分享
Queue.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int QDataType;
typedef struct QNode
{
QDataType a;
struct QNode* next;
}QNode;
typedef struct Queue
{
QNode* phead;
QNode* ptail;
int size;
}Queue;
void QueueInit(Queue* pq);
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);
text.c
#include"Queue.h"
int main()
{
Queue p;
QueueInit(&p);
QueuePush(&p, 1);
QueuePush(&p, 2);
QueuePush(&p, 3);
QueuePush(&p, 4);
while (!QueueEmpty(&p))
{
printf("%d ", QueueFront(&p));
QueuePop(&p);
}
QueueDestroy(&p);
return 0;
}
关于栈和队列的实现还是比较简单的。感谢大家的观看,如有错误和不足的地方还请多多指出。