重庆分公司,新征程启航
为企业提供网站建设、域名注册、服务器等服务
目录
成都创新互联专注于勐海网站建设服务及定制,我们拥有丰富的企业做网站经验。 热诚为您提供勐海营销型网站建设,勐海网站制作、勐海网页设计、勐海网站官网定制、成都微信小程序服务,打造勐海网络公司原创品牌,更为您提供勐海网站排名全网营销落地服务。前言
一、栈
1.1 栈的概念和结构
1.2 栈的实现
1.2.1 栈的创建及其初始化
1.2.2 入栈/出栈
1.2.3 获取栈顶元素
1.2.4 检查栈是否为空
1.2.5 销毁栈
二、队列
2.1 队列的概念及结构
2.2 队列的实现
2.2.1 队列结构的创建及初始化
2.2.2 插入删除数据
2.2.3 读取头尾数据
2.2.4 判断是否为空
2.2.5 判断存储数据的数量
2.2.6 销毁队列
总结
本篇文章主要带领大家深入了解栈和队列以及相关实现。
栈:栈是一种特殊的线性表,其只允许在一端进行插入和删除的操作,而进行插入删除操作的一端叫栈顶,另一端叫栈底。所以栈中的数据也遵从后进先出原则。
1.2 栈的实现压栈:从栈顶压入数据的操作叫做压栈,也称为进栈或者出栈
出栈:从栈顶删除数据的操作叫做出栈
栈的实现一般使用数组或者是链表,相对而言,使用数组的优势更大,因为数组尾插尾删的效率高,相当契合栈的要求,而链表尾删需要遍历链表效率相比数组就低了许多。
1.2.1 栈的创建及其初始化接下来我们就用数组实现动态栈
栈的创建:栈的结构体成员有三个,分别代表数组,栈顶,栈容
// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{
STDataType* _a;
int _top; // 栈顶
int _capacity; // 容量
}Stack;
栈的初始化:我们先开辟4个空间的数组,然后给栈顶,容量赋值
// 初始化栈
void StackInit(Stack* ps)
{
assert(ps);
STDataType* ptr = (STDataType*)malloc(4 * sizeof(STDataType));
if (ptr == NULL)//检查开辟是否成功
{
perror("malloc");
exit(-1);
}
ps->_a = ptr;
ps->_top = 0;
ps->_capacity = 4;
}
1.2.2 入栈/出栈入栈:入栈需要先检查容量,如果容量满了,就用realloc进行扩容,然后在插入数据即可
// 入栈
void StackPush(Stack* ps, STDataType data)
{
assert(ps);
if (ps->_top == ps->_capacity)
{
STDataType* ptr =realloc(ps->_a,ps->_capacity*2*sizeof(STDataType));
if (ptr == NULL)//检查开辟是否成功
{
perror("malloc");
exit(-1);
}
ps->_a = ptr;
ps->_capacity = ps->_capacity * 2;
}
ps->_a[ps->_top] = data;
ps->_top++;
}
出栈:出栈就很简单了,只需检查栈里是否有数据,无数据则无法删除,然栈顶--即可。
// 出栈
void StackPop(Stack* ps)
{
assert(ps);
assert(StackEmpty(ps));
ps->_top--;
}
1.2.3 获取栈顶元素这个需要注意的是,top指向的是栈顶元素的下一个位置,所以想要获取栈顶元素,需要的下标是top-1
// 获取栈顶元素
STDataType StackTop(Stack* ps)
{
assert(ps);
assert(StackEmpty(ps));
return ps->_a[ps->_top - 1];
}
1.2.4 检查栈是否为空只需返回top即可,如果top为0则为空
// 检测栈是否为空,如果为空返回非零结果,如果不为空返回0
bool StackEmpty(Stack* ps)
{
assert(ps);
return ps->_top;
}
1.2.5 销毁栈释放数组即可
// 销毁栈
void StackDestroy(Stack* ps)
{
assert(ps);
free(ps->_a);
ps->_a = NULL;
ps->_capacity = 0;
ps->_top = 0;
}
二、队列
2.1 队列的概念及结构2.2 队列的实现队列:只允许在一端进行插入,在另一端进行删除的特殊线性表,插入的一端叫队尾,删除的一端叫队头,遵从先进先出原则。
队列一般可以用数组或者链表实现,使用链表的结构更优一些,因为队列需要用到尾插头删,链表的头删和尾插都比数组要优秀。
2.2.1 队列结构的创建及初始化下面就用链表实现队列
结构的创建:首先是创建链表的节点空间,然后在创建两个指针分别指向链表头和尾,再创建一个size记录队列的有效数据
typedef int QDataType;
typedef struct QueueNode
{
QDataType data;
struct QueueNode* next;
}QNode;
typedef struct Queue
{
QNode* head;
QNode* tail;
int size;
}Queue;
初始化:头尾指针置空,size置为0
//初始化
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = pq->tail = NULL;
pq->size = 0;
}
2.2.2 插入删除数据插入数据:先给要插入的数据开辟一个新节点,然后只需要考虑一些第一次插入的特殊情况,其他按照链表的尾插即可
//插入数据
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QNode* newcode = (QNode*)malloc(sizeof(QNode));
if (newcode == NULL)
{
perror("malloc");
exit(-1);
}
if (pq->head == NULL)
{
newcode->data = x;
newcode->next = NULL;
pq->head = pq->tail = newcode;
pq->size++;
}
else
{
newcode->data = x;
newcode->next = NULL;
pq->tail->next = newcode;
pq->tail = pq->tail->next;
pq->size++;
}
}
删除数据:需要检查是否为空,为空则无法删除,和链表头删类似
//删除数据
void QueuePop(Queue* pq)
{
assert(pq);
assert(QueueEmpty(pq));
QNode* cur = pq->head->next;
free(pq->head);
pq->head = cur;
pq->size--;
}
2.2.3 读取头尾数据读取头数据:直接读取head指向的数据即可
//读取头个数据
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(QueueEmpty(pq));
return pq->head->data;
}
读取尾数据:读取tail指向的数据即可
//读取最后一个数据
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(QueueEmpty(pq));
return pq->tail->data;
}
2.2.4 判断是否为空head和tail为空则为空
//判断是否为空
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->head && pq->tail;
}
2.2.5 判断存储数据的数量返回size即可
//判断数据的数量
int QueueSize(Queue* pq)
{
assert(pq);
assert(QueueEmpty(pq));
return pq->size;
}
2.2.6 销毁队列一个空间一个空间释放即可
//释放空间
void QueueDestroy(Queue* pq)
{
assert(pq);
while (pq->head)//一个节点一个节点释放
{
QNode* cur = pq->head->next;
free(pq->head);
pq->head = cur;
}
pq->head = NULL;
pq->tail = NULL;
pq->size = 0;
}
以上就是今天要讲的内容,希望铁子们可以有所收货。
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧