【C语言数据结构】详解栈与队列（上）（栈与队列的实现）
目录
一、栈
（一）栈的概念及结构
栈：一种特殊的线性表，其只允许再固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端成为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做压栈（或者入栈、进栈），入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
栈既可以通过数组的方法实现，也可以以链表的方式实现。数组的具体的实现方法我们来看下面两幅图：
如图所示，在通过数组实现时，我们会定义一个top变量来表示堆顶，每插入一个元素，top的值都会发生改变。在删除操作时，由于后进先出原则，最后一个入栈的元素5也就是数组的最后一个元素应该最先出栈，因此我们只需要把top的位置往前挪动，即可实现出栈操作了。
知道了底层逻辑，我们就可以用代码来实现了。
（二）栈的接口实现
1.栈的初始化与销毁
我们首先将要存储的数据类型进行重命名。其次需要定义一个结构体，结构体内应包含：1个指数据存储数组的指针，1个表示堆顶的整形变量，由于需要动态开辟空间，所以还需要1个表示容量的整形变量。
typedef int DataType;
typedef struct Stack {
DataType* val;
int top;
int capacity;
}Stack;栈的初始化我们通过形参传址来对结构体内的各元素进行初始化。val需要开辟空间，其他参数置零。
//初始化栈
void StackInit(Stack* pmp)
{
pmp->val = (DataType*)malloc(sizeof(DataType) * 4);
if (!pmp->val)
{
perror("BuyStack::malloc");
return;
}
pmp->top = 0;
pmp->capacity = 4;
return;
}栈的销毁同样通过传址操作来实现，释放val的空间并置空，将其他参数置零。注意一下，结构体变量并不需要释放空间，因为它的空间不是通过动态开辟取得的。进行销毁操作前要对结构体指针进行断言，指针不能为空，必须有指向的空间。
//销毁栈
void DestoryStack(Stack* pmp)
{
assert(pmp);
free(pmp->val);
pmp->val = NULL;
pmp->capacity = pmp->top = 0;
return;
}2.入栈操作
如前文所述，入栈时只需要通过调整top的值即可控制数据的存储位置。当然了，入栈前需要对容量进行判断，容量不足则需要扩容，判断方法就是top值与capacity相等时则表示满栈。扩容之后capacity需要变成新的容量大小，存入一个数据需要对top的值++ 。
//入栈
void PushStack(Stack* pmp, DataType x)
{
if (pmp->top == pmp->capacity)
{
DataType* tmp = (DataType*)realloc(pmp->val, sizeof(DataType)*pmp->capacity*2);
if (!tmp)
{
perror("PushStack::realloc");
return;
}
pmp->val = tmp;
pmp->capacity *= 2;
}
pmp->val[pmp->top] = x;
pmp->top++;
return;
}
编译运行没有问题。
3.判断空栈与出栈
在进行出栈操作前，需要判断栈是否为空如果为空就不能继续出栈。我们bool返回值来表示，空栈则返回1，非空则返回0。对空栈有两种处理办法，一种是if语句的温柔检查，如果空栈就直接返回值停止后续操作；还有一种是assert的暴力检查，空栈就直接error报错，这种方法的好处是可以及时发现程序的问题，找出错误信息。所以我们用assert暴力检查方法：
//判断空栈
bool StackisEmpty(Stack* pmp)
{
assert(pmp);
if (!pmp->top)
return 1;
return 0;
}
//出栈
DataType PopStack(Stack* pmp)
{
assert(pmp);
assert(!StackisEmpty(pmp));
DataType ret = 0;
ret = pmp->val[pmp->top-1];
pmp->top--;
return ret;
}assert()内部的值如果为0就会报错，我们可以看到代码中，如果空栈，StackisEmpty会返回1，！1的值就是0，所以空战时assert()括号内是0，会报错，符合要求。
如图栈内原有5个数据，进行五次出栈操作后变成空栈，此后再出栈时报错了，符合要求。
至此，就已经完成了栈的实现，最后还有一个栈的打印，用于调试代码时使用，这里就不单独列出来了。
最后呈上完整代码：
（三）完整代码
//Stack.h
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int DataType;
typedef struct Stack {
DataType* val;
int top;
int capacity;
}Stack;
//初始化栈
void StackInit(Stack* pmp);
//销毁栈
void DestoryStack(Stack* pmp);
//入栈
void PushStack(Stack* pmp, DataType x);
//出栈
DataType PopStack(Stack* pmp);
//判断空栈
bool StackisEmpty(Stack* pmp);
//栈的打印
void PrintStack(Stack* pmp);//Stack.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
//初始化栈
void StackInit(Stack* pmp)
{
pmp->val = (DataType*)malloc(sizeof(DataType) * 4);
if (!pmp->val)
{
perror("BuyStack::malloc");
return;
}
pmp->top = 0;
pmp->capacity = 4;
return;
}
//销毁栈
void DestoryStack(Stack* pmp)
{
assert(pmp);
free(pmp->val);
pmp->val = NULL;
pmp->capacity = pmp->top = 0;
return;
}
//入栈
void PushStack(Stack* pmp, DataType x)
{
if (pmp->top == pmp->capacity)
{
DataType* tmp = (DataType*)realloc(pmp->val, sizeof(DataType)*pmp->capacity*2);
if (!tmp)
{
perror("PushStack::realloc");
return;
}
pmp->val = tmp;
pmp->capacity *= 2;
}
pmp->val[pmp->top] = x;
pmp->top++;
return;
}
//判断空栈
bool StackisEmpty(Stack* pmp)
{
assert(pmp);
if (!pmp->top)
return 1;
return 0;
}
//出栈
DataType PopStack(Stack* pmp)
{
assert(pmp);
assert(!StackisEmpty(pmp));
DataType ret = 0;
ret = pmp->val[pmp->top-1];
pmp->top--;
return ret;
}
//栈的打印
void PrintStack(Stack* pmp)
{
for (int i = 0; i < pmp->top; i++)
{
printf("%d ", pmp->val[i]);
}
printf("\n");
return;
}二、队列
（一）队列的概念及结构
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出：FIFO(First In First Out)的特点。
入队列：进行插入操作的一端成为队尾
出队列：进行删除操作的一端称为队头
通过上图可知，用数组实现时，用head、tail分别表示队头和队尾，head始终为0，tail在每插入一个数据时就往后移一位。由于先进先出原则，第一个出队列的应该是“1”，在数组中，我们通过挪动数据的方法将第一个数据进行覆盖，这样就实现了出队列，时间复杂度O(N)=n。
（二）队列的接口实现
1.队列的初始化与销毁
我们首先将要存储的数据类型进行重命名。其次需要定义一个结构体，结构体内应包含：1个指数据存储数组的指针，2个分别表示队头和队尾的整形变量，由于需要动态开辟空间，所以还需要1个表示容量的整形变量。
typedef int DataType;
typedef struct Queue {
DataType* val;
int head;
int tail;
int capacity;
}Queue;栈的初始化我们通过形参传址来对结构体内的各元素进行初始化。val需要开辟空间，其他参数置零。
//初始化队列
void QueueInit(Queue* pmp)
{
pmp->val = (DataType*)malloc(sizeof(DataType) * 4);
if (!pmp->val)
{
perror("QueueInit::malloc");
return;
}
pmp->head = pmp->tail = 0;
pmp->capacity = 4;
return;
}栈的销毁同样通过传址操作来实现，释放val的空间并置空，将其他参数置零。注意一下，结构体变量并不需要释放空间，因为它的空间不是通过动态开辟取得的。进行销毁操作前要对结构体指针进行断言，指针不能为空，必须有指向的空间。
//销毁队列
void QueueDestory(Queue* pmp)
{
assert(pmp);
free(pmp->val);
pmp->val = NULL;
pmp->head = pmp->tail = pmp->capacity = 0;
return;
}
2. 入队列操作
如前文所述，入队列时只需要通过调整tail的值即可控制数据的存储位置。当然了，入队列前需要对容量进行判断，容量不足则需要扩容，判断方法就是tail值与capacity相等时则表示满队列。扩容之后capacity需要变成新的容量大小，存入一个数据需要对tail的值++ 。
//入队
void QueuePush(Queue* pmp, DataType x)
{
if (pmp->tail == pmp->capacity)
{
Queue* tmp = (Queue*)realloc(pmp->val, sizeof(Queue) * pmp->capacity * 2);
if (!pmp)
{
perror("QueuePush::realloc");
return;
}
pmp->val = tmp;
pmp->capacity *= 2;
}
pmp->val[pmp->tail] = x;
pmp->tail++;
return;
}
编译运行没有问题。
3.判断空队列与出队列
在进行出队列操作前，需要判断队列是否为空如果为空就不能继续出队列。我们bool返回值来表示，空队列则返回1，非空则返回0。对空队列有两种处理办法，一种是if语句的温柔检查，如果空队列就直接返回值停止后续操作；还有一种是assert的暴力检查，空队列就直接报错，这种方法的好处是可以及时发现程序的问题，找出错误信息。所以我们用assert暴力检查方法：
//为空判断
bool QueueisEmpty(Queue* pmp)
{
assert(pmp);
if (pmp->tail == pmp->head)
return 1;
return 0;
}
//出队
DataType QueuePop(Queue* pmp)
{
assert(pmp);
assert(!QueueisEmpty(pmp));
for (int i = 1; i < pmp->tail; i++)
{
pmp->val[i - 1] = pmp->val[i];
}
pmp->tail--;
return;
}assert()内部的值如果为0就会报错，我们可以看到代码中，如果空栈，QueueisEmpty会返回1，！1的值就是0，所以空战时assert()括号内是0，会报错，符合要求。
如图队列内原有4个数据，进行四次出栈操作后变成空栈，此后再出栈时报错了，符合要求。
至此，就已经完成了栈的实现，最后还有一个栈的打印，用于调试代码时使用，这里就不单独列出来了。
最后呈上完整代码：
（三）完整代码
//Queue.h
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int DataType;
typedef struct Queue {
DataType* val;
int head;
int tail;
int capacity;
}Queue;
//初始化队列
void QueueInit(Queue* pmp);
//销毁队列
void QueueDestory(Queue* pmp);
//打印队列
void QueuePrint(Queue* pmp);
//入队
void QueuePush(Queue* pmp, DataType x);
//为空判断
bool QueueisEmpty(Queue* pmp);
//出队
DataType QueuePop(Queue* pmp);//Queue.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"
//初始化队列
void QueueInit(Queue* pmp)
{
pmp->val = (DataType*)malloc(sizeof(DataType) * 4);
if (!pmp->val)
{
perror("QueueInit::malloc");
return;
}
pmp->head = pmp->tail = 0;
pmp->capacity = 4;
return;
}
//销毁队列
void QueueDestory(Queue* pmp)
{
assert(pmp);
free(pmp->val);
pmp->val = NULL;
pmp->head = pmp->tail = pmp->capacity = 0;
return;
}
//打印队列
void QueuePrint(Queue* pmp)
{
assert(pmp);
for (int i = 0; i < pmp->tail; i++)
{
printf("%d ", pmp->val[i]);
}
printf("\n");
return;
}
//入队
void QueuePush(Queue* pmp, DataType x)
{
if (pmp->tail == pmp->capacity)
{
Queue* tmp = (Queue*)realloc(pmp->val, sizeof(Queue) * pmp->capacity * 2);
if (!pmp)
{
perror("QueuePush::realloc");
return;
}
pmp->val = tmp;
pmp->capacity *= 2;
}
pmp->val[pmp->tail] = x;
pmp->tail++;
return;
}
//为空判断
bool QueueisEmpty(Queue* pmp)
{
assert(pmp);
if (pmp->tail == pmp->head)
return 1;
return 0;
}
//出队
DataType QueuePop(Queue* pmp)
{
assert(pmp);
assert(!QueueisEmpty(pmp));
for (int i = 1; i < pmp->tail; i++)
{
pmp->val[i - 1] = pmp->val[i];
}
pmp->tail--;
return;
}
魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。
更多推荐
3
0- 0
已为社区贡献1条内容
所有评论(0)