C语言超详细讲解栈与队列实现实例

Olathe ·

更新时间:2024-06-01

· 479 次阅读

1.思考-1

2.栈基本操作的实现

2.1 初始化栈

2.2 入栈

2.3 出栈

2.4 获取栈顶数据

2.5 获取栈中有效元素个数

2.6 判断栈是否为空

2.7 销毁栈

3.测试

3.1 测试

3.2 测试结果

4.思考-2

5.队列的基本操作实现

5.1 初始化队列

5.2 队尾入队列

5.3 队头出队列

5.4 队列中有效元素的个数

5.5 判断队列是否为空

5.6 获取队头数据

5.7 获取队尾的数据

5.8 销毁队列

6.测试

6.1 测试

6.2 测试结果

1.思考-1

为什么栈用数组来模拟比用链表来模拟更优一些？

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低，时间复杂度为O(n)。

2.栈基本操作的实现 2.1 初始化栈


void StackInit(stack*ps)
{
assert(ps);
ps->_a = (StackDate*)malloc(sizeof(StackDate) * 4);
ps->_top = 0;
ps->_capacity = 4;
}

2.2 入栈


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++;
}

2.3 出栈


void StackPop(stack*ps)
{
assert(ps);
assert(!StackIsEmpty(ps));
--ps->_top;
}

注意：出栈并不是真正意义上的删除数据，而是将_top向后挪动了一个位置。

2.4 获取栈顶数据


StackDate StackTop(stack*ps)
{
assert(ps);
assert(!StackIsEmpty(ps));
return ps->_a[ps->_top - 1];
}

2.5 获取栈中有效元素个数


int StackSize(stack*ps)
{
assert(ps);
return ps->_top;
}

2.6 判断栈是否为空


bool StackIsEmpty(stack*ps)
{
assert(ps);
return ps->_top == 0;
}

2.7 销毁栈


void StackDestory(stack*ps)
{
assert(ps);
free(ps->_a);
ps->_a = NULL;
ps->_top = ps->_capacity = 0;
}

3.测试 3.1 测试


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);
}

3.2 测试结果

4.思考-2

为什么队列用链表模拟比数组模拟更加合适？

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价小。

5.队列的基本操作实现 5.1 初始化队列


void QueueInit(Queue*pq)
{
assert(pq);
pq->_head = pq->_tail = NULL;
}

5.2 队尾入队列


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;
}
}

5.3 队头出队列


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;
}
}

代码分析：

5.4 队列中有效元素的个数


int QueueSize(Queue*pq)
{
assert(pq);
int count = 0;
QueueNode*cur = pq->_head;
while (cur)
{
++count;
cur = cur->next;
}
return count;
}

5.5 判断队列是否为空


bool QueueIsEmpty(Queue*pq)
{
assert(pq);
return pq->_head == NULL;
}

5.6 获取队头数据


QueueDate QueueFront(Queue*pq)
{
assert(pq);
assert(!QueueIsEmpty(pq));
return pq->_head->val;
}

5.7 获取队尾的数据


QueueDate QueueBack(Queue*pq)
{
assert(pq);
assert(!QueueIsEmpty(pq));
return pq->_tail->val;
}

5.8 销毁队列


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;
}
}
}

注意：和队头出队列一样分析。

6.测试 6.1 测试


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");
}

6.2 测试结果