栈与队列的简单实现
2023-05-18 18:24:01 182浏览
一、数组实现栈
1.什么是栈
栈是一种存储数据的结构。
栈就好比是一个仓库，只能从仓库的门口像仓房放东西和拿东西，先放的东西在仓库深处，直到堆满仓库，当我们想要取出某一件东西时，只能从最外面的东西开始把东西一件件拿出来。
也就是说栈只能从一端进行插入和删除，而插入和删除数据的内一端被称为栈顶，另一端叫做栈底。也就是后进先出。
2.如何定义栈
栈的定义：
typedef int DataType;
typedef struct Stack
{
DataType* a;
int top;
int capacity;
}ST;我们用动态数组思想来实现栈。
如上是栈的定义，指针变量a用来存储栈上的数据，整型变量capacity用来表示栈的空间大小，整型变量top用来表示栈顶，指向的如果top初始化为0，则栈表示的是栈顶元素的下一位置的下标，同时top表示的也是栈中元素的个数
3.栈的初始化
void STInit(ST* pst);
void STInit(ST* pst)
{
assert(pst);
pst->a = NULL;
pst->capacity = 0;
pst->top = 0;
}对于指针pst来说，它接收的是栈这个数据类型变量的地址，而地址是肯定不会为空的，因此用assert断言。
栈在最开始是一个空栈，没有存储任何数据，没有栈空间，因此我们让存储数据的指针变量a指向NULL,表示栈空间大小的capacity置为0，而栈顶显然也是0
4.栈的销毁
void STDestory(ST* pst);
void STDestory(ST* pst)
{
assert(pst);
free(pst->a);
pst->a = NULL;
pst->top=0;
pst->capacity = 0;
}形参pst接收的是地址，因此不可能为空，所以添加断言。
栈是一种数据结构，也可以理解为一个结构体，真正存储栈上数据的是结构体当中的指针。
对于栈的销毁来说，先要消除栈的数据，在去销毁栈本身，因此需要先将结构体中的指针释放（pst->a），再去释放指向这个结构体（栈）的指针（pst），同时，栈空间再次为NULL，容量和栈顶再次置为0.
5.入栈和出栈
入栈
void STPush(ST* pst,DataType x);
void STPop(ST* pst);
void STPush(ST* pst, DataType x)
{
assert(pst);
if (pst->top == pst->capacity)//判断栈空间是否满了
{
int newcapacity = pst->capacity == 0 ? 4 : (2 * pst->capacity);
//栈的容量为0时，初始化为4，之后栈容量都扩大二倍
DataType* tem = (DataType*)realloc(pst->a,
newcapacity*sizeof(DataType));
//开辟并使得指针tem指向可以存储newcapacity个数据的空间
if (tem == NULL)//空间开辟失败
{
perror("realloc fail");
return;
}
pst->a = tem;//使得存储栈数据的指针指向新开辟好的空间
pst->capacity = newcapacity;//更新栈容量
}
pst->a[pst->top] = x;//更新数据
pst->top++;//更新个数
}这里是利用数组思想实现的栈，栈空间大小是动态申请的。
所以在入栈时，我们都必须判断栈的空间是否已经满了，在这里我们对栈空间容量和栈元素个数进行判断，如果相等，则代表栈已满，需要为增添新的数据动态开辟空间。
当为栈添加第一个数据时，我们默认为栈创建的容量为4，否则为栈空间容量的2倍。这也正是语句：newcapacity = pst->capacity == 0 ? 4 : (2 * pst->capacity)存在的使命 ，它确定的是新的栈空间容量的大小。而为存储数据的指针变量a动态开辟空间的重任则是落在了reallloc函数上，语句：DataType* tem = (DataType*)realloc(pst->a, newcapacity*sizeof(DataType)) 利用realloc函数将指针变量a的空间扩大为原来的2倍（初始为4，之后都是二倍），指针变量tmp接收动态申请空间的起始地址，并对齐进行判断，如果开辟成功，则让栈中的a指向这块空间，同时更新栈的容量与个数（pst->a[pst->top] = x;
pst->top++）
出栈
void STPop(ST* pst)
{
assert(pst);
assert(!STEmpty(pst));
pst->top--;
}只有在栈不为空的时候才可以出栈，因此断言栈非空，而出栈只需更新栈的个数，或者说栈顶数据的下标top即可
6.判断栈空
bool STEmpty(ST* pst);
bool STEmpty(ST* pst)
{
assert(pst);
return pst->top == 0;
}栈中的top描述的是栈数据的个数，top为0，则栈空
7.返回栈顶元素
DataType STTop(ST* pst);
DataType STTop(ST* pst)
{
assert(pst);
assert(!STEmpty(pst));
return pst->a[pst->top-1];
}要返回栈顶元素，就必须保证栈非空，因此添加断言，而栈顶元素的下标为top-1，直接利用数组下标访问即可
8.返回栈的数据个数
int STSize(ST* pst);
int STSize(ST* pst)
{
return pst->top;
}栈中的top就是数据个数，直接返回即可
二、链表实现队列
1.什么是队列
队列也是一种用来存储数据的结构。那么它的结构是怎么样的？
其实队列就好比排队做核酸时的核酸队伍，只能从一端进，另一端出，并且先进去的人先出去，后进去的人后出去。也就是先进先出。如下图：
对于队列，队尾是进数据的一端，队头是出数据的一端
2.如何定义队列
typedef int DataType;
typedef struct QueueNode
{
DataType data;
struct QueueNode* next;
}QNode;
typedef struct Queue
{
QNode* front;
QNode* rear;
int size;
}Queue;对于队列这种结构，我们使用单链表思想来实现，链表中的每一个节点对应队列的一个数据，因此我们需要先定义节点的结构体，用来存储数据和指向下一个节点，然后才可以定义队列的结构体，用两个指针front和rear分别表示队头和队尾，并用size表示队列人数
3.队列的初始化
void InitQueue(Queue* q);
void InitQueue(Queue* q)
{
assert(q);
q->front = NULL;
q->rear = NULL;
q->size = 0;
}队列最初为空，所以指向队头和队尾的指针都应该指向空，同时队列数据个数为0
4.队列的销毁
void Destory(Queue* q);
void Destory(Queue* q)
{
assert(q);
QNode* cur = q->front;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
q->front = NULL;
q->rear = NULL;
}销毁队列，其实就是销毁链表，因为数据都是储存在链表当中，所以我们先通过指向队头的指针front找到并且销毁单链表，再将指向队头和队尾的指针置为空。
5.入队与出队
void PushQueue(Queue* q, DataType x);//入队
void PopQueue(Queue* q);//出队
void PushQueue(Queue* q, DataType x)
{
assert(q);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
//动态申请节点空间
if (!newnode)//申请失败
{
perror("malloc fail");
return;
}
else//申请成功
{
newnode->data = x;
newnode->next = NULL;
if (q->front == NULL)//队列为空时
{
q->front = q->rear = newnode;
}
else//队列不为空时
{
q->rear->next = newnode;
q->rear = newnode;
}
q->size++;//入队后队列数据个数加1
}
}
void PopQueue(Queue* q)
{
assert(q);
assert(q->front&&q->rear);//断言队列非空
if (!q->front->next)//队列只有一个数据
{
free(q->front);
q->front = q->rear = NULL;
}
else//队列有两个及以上的数据
{
QNode* next = q->front->next;//保存队头节点的下一个节点的地址
free(q->front);//释放队头指向节点，出队
q->front = next;//更新队列front
}
q->size--;//出队后数据个数减1
}队列的入队和出队其实和链表的尾插和头插类似，只不过队列需要我们通过队列中的rear来找到队尾尾插来插入数据，通过front找到队头来删除数据，其实就是单链表的尾插和头删，只不过我们需要更新队列中的front和rear以及size,使得队列在插入和删除操作后指向正确的位置,并且得到新的size。
6.返回队头与队尾数据
DataType FrontQueue(Queue* q);
DataType RearQueue(Queue* q);
DataType FrontQueue(Queue* q)
{
assert(q);
assert(!EmptyQueue(q));
return q->front->data;
}
DataType RearQueue(Queue* q)
{
assert(q);
assert(!EmptyQueue(q));
return q->rear->data;
}因为队列可以直接指向队列数据的头和尾，因此我们只要在断言地址和队列非空后，可以利用指针直接返回队头和队尾的数据。
7.判断队列是否为空
bool EmptyQueue(Queue* q);
bool EmptyQueue(Queue* q)
{
assert(q);
return q->size == 0;
}利用记录队列数据个数的变量size来直接判断
8.返回队列数据个数
int SizeQueue(Queue* q);
int SizeQueue(Queue* q)
{
assert(q);
return q->size;
}直接返回队列个数
好博客就要一起分享哦！分享海报
此处可发布评论
评论（0）展开评论
展开评论
