目录1.思考-12.栈基本操作的实现2.1 初始化栈2.2 入栈2.3 出栈2.4 获取栈顶数据2.5 获取栈中有效元素个数2.6 判断栈是否为空2.7 销毁栈3.测试3.1 测试3
队列也可以数组和链表的结构实现,使用链表的结构实现更优一些,因为如果使用数组的结构,出队列在数组头上出数据,效率会比较低,时间复杂度为O(n)。
void StackInit(stack*ps)
{
assert(ps);
ps->_a = (StackDate*)malloc(sizeof(StackDate) * 4);
ps->_top = 0;
ps->_capacity = 4;
}
void StackPush(stack*ps, StackDate x)
{
assert(ps);
if (ps->_top == ps->_capacity)
{
stack*tmp = (StackDate*)realloc(ps, sizeof(StackDate)*(ps->_capacity) * 2);
if (NULL == tmp)
{
printf("realloc failed\n");
exit(-1);
}
ps = tmp;
ps->_capacity *= 2;
}
ps->_a[ps->_top] = x;
ps->_top++;
}
void StackPop(stack*ps)
{
assert(ps);
assert(!StackIsEmpty(ps));
--ps->_top;
}
注意: 出栈并不是真正意义上的删除数据,而是将_top向后挪动了一个位置。
StackDate StackTop(stack*ps)
{
assert(ps);
assert(!StackIsEmpty(ps));
return ps->_a[ps->_top - 1];
}
int StackSize(stack*ps)
{
assert(ps);
return ps->_top;
}
bool StackIsEmpty(stack*ps)
{
assert(ps);
return ps->_top == 0;
}
void StackDestory(stack*ps)
{
assert(ps);
free(ps->_a);
ps->_a = NULL;
ps->_top = ps->_capacity = 0;
}
void test()
{
//插入数据
stack st;
StackInit(&st);
StackPush(&st,1);
StackPush(&st,2);
StackPush(&st,3);
StackPush(&st,4);
while (!StackIsEmpty(&st))
{
printf("%d ", StackTop(&st));
StackPop(&st);
}
printf("\n");
//获取栈顶数据
StackPush(&st, 1);
StackPush(&st, 2);
printf("%d ", StackTop(&st));
printf("\n");
//栈中有效数据个数
printf("%d ", StackSize(&st));
//销毁栈
StackDestory(&st);
}
为什么队列用链表模拟比数组模拟更加合适?
栈的实现一般可以使用数组或者链表实现,相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价小。
void QueueInit(Queue*pq)
{
assert(pq);
pq->_head = pq->_tail = NULL;
}
void QueuePush(Queue*pq, QueueDate x)
{
assert(pq);
Queuenode*newnode = (QueueNode*)malloc(sizeof(QueueNode));
if (NULL == newnode)
{
printf("malloc failed\n");
exit(-1);
}
newnode->next = NULL;
newnode->val = x;
if (NULL == pq->_tail)
{
pq->_head = pq->_tail = newnode;
}
else
{
pq->_tail->next = newnode;
pq->_tail = newnode;
}
}
void QueuePop(Queue*pq)
{
assert(pq);
assert(!QueueIsEmpty(pq));
if (NULL == pq->_head->next)
{
free(pq->_head);
pq->_head = pq->_tail = NULL;
}
else
{
QueueNode*next = pq->_head->next;
free(pq->_head);
pq->_head = next;
}
}
代码分析:
int QueueSize(Queue*pq)
{
assert(pq);
int count = 0;
QueueNode*cur = pq->_head;
while (cur)
{
++count;
cur = cur->next;
}
return count;
}
bool QueueIsEmpty(Queue*pq)
{
assert(pq);
return pq->_head == NULL;
}
QueueDate QueueFront(Queue*pq)
{
assert(pq);
assert(!QueueIsEmpty(pq));
return pq->_head->val;
}
QueueDate QueueBack(Queue*pq)
{
assert(pq);
assert(!QueueIsEmpty(pq));
return pq->_tail->val;
}
void QueueDestory(Queue*pq)
{
assert(pq);
while (pq->_head)
{
if (pq->_head == pq->_tail)
{
free(pq->_head);
pq->_head = pq->_tail = NULL;
}
else
{
QueueNode*next = pq->_head->next;
free(pq->_head);
pq->_head = next;
}
}
}
注意: 和队头出队列一样分析。
void test1()
{
//插入数据
Queue q;
QueueInit(&q);
QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
QueuePush(&q, 4);
//有效数据的个数
printf("%d ", QueueSize(&q));
printf("\n");
//获取队头数据
printf("%d",QueueFront(&q));
printf("\n");
//获取队尾数据
printf("%d",QueueBack(&q));
printf("\n");
//出队
QueuePop(&q);
while (!QueueIsEmpty(&q))
{
printf("%d ", QueueFront(&q));
QueuePop(&q);
}
printf("\n");
//销毁
QueueDestory(&q);
printf("\n");
}
今天数据结构栈与队列的相关知识点就分享到这里了,感谢你的浏览,如果对你有帮助的话,可以给个关注,顺便来个赞。
到此这篇关于C语言超详细讲解栈与队列实现实例的文章就介绍到这了,更多相关C语言 栈与队列内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网!
--结束END--
本文标题: C语言超详细讲解栈与队列实现实例
本文链接: https://www.lsjlt.com/news/144314.html(转载时请注明来源链接)
有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
下载Word文档到电脑,方便收藏和打印~
2024-03-01
2024-03-01
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
回答
回答
回答
回答
回答
回答
回答
回答
回答
回答
0