前言

一、栈

1.概述 :

2.分类 :

前言

C 数据结构与算法入门——栈和队列内容分享。

注意 : ①代码中的注释也很重要；②不要眼高手低，自己动手跟着过一遍才能真正有收获；③可以点击文章侧边栏或者文章前面的目录进行跳转。良工不示人以朴，所有文章都会适时补充完善。感谢阅读！

一、栈

1.概述 :

"栈"是一种可以实现"先进后出"的存储结构。类似于向一个杯子里面装东西，先放进去的东西只能后倒出来。函数的调用，表达式的求值，内存分配，缓冲处理，迷宫问题等等都与栈有关。

2.分类 :

栈可分为静态栈和动态栈。

静态栈：内核为数组，空间是连续的。

动态栈：内核为链表，空间不连续。

无论是静态栈还是动态栈，都满足栈"先进后出"的特点。

本篇博客以动态栈为例，动态栈图示如下：

3.算法:

〇准备工作

使用typedef关键字，先定义Node类型的结构体（形成链表的条件），然后再定义一个Stack类型的结构体表示栈。在Stack类型的结构体定义两个成员pTop和pBottom，将来分别指向栈中的第一个元素和最后一个元素。如下所示：

typedefstructNode{
intdata;
structNode*pNext;
} NODE, *PNODE;
typedefstructStack{
PNODEpTop;
PNODEpBottom;
} STACK, *PSTACK;

注意，此处的"栈中第一个元素"指的是栈中真正意义上的第一个元素（相当于单链表中的头节点），该结点不存放有效数据。

①初始化

1° 仅仅在main方法中创建一个STACK类型的变量，并不算创建好一个栈，因为此时栈中的成员pTop和pBottom的值还是垃圾值。只有当pTop和pBottom指向同一个结点（头结点）时，一个栈才算被真正地创建出来。

2° 定义init_stack方法来完成栈的初始化，init_stack函数需要传入一个PSTACK类型的实参。init_stack方法的目的就是要让pTop和pBottom同时指向栈中的第一个元素。如下图所示 :

3° 先通过malloc函数为头结点分配内存空间；然后在令pTop和pBottom指向该空间；最后令其pNext指针域为空即可。

②压栈（进栈）:

1° 定义push_stack函数完成压栈的操作，push_stack函数需要传入一个PSTACK类型的实参和一个int类型的实参。（假设要存储的值为int类型）

2°将int类型的实参赋值给新结点的data成员。

3°令新结点指向pTop指向的结点（当前栈最顶部的结点），再令pTop的指针上移一位，使其指向新结点。效果如下图所示 :

③遍历 :

1° 在前面代码的基础上，定义traverse_stack函数来进行栈的遍历，只需要传入一个PSTACT类型的实参。

2° 定义一个临时变量pDemo（PNODE类型），令其指向栈中顶部的结点。

3° 利用while循环进行遍历，当pDemo指向的结点与pBottom指向的结点相同时停止遍历。

4° 最终达到的效果就是自上而下遍历栈中的元素（即先进后出）。

④判断栈是否为空 :

1° 在前面代码的基础上，定义is_empty函数来进行对栈是否为空的判断。

2°若判断栈中的pTop成员和pBottom成员指向相同，说明当前是空栈，否则不为空。

3° 判断栈是否为空的前提，是这个栈已经初始化，如果pTop和pBottom都是垃圾值，那么认为这个栈还没有创建出来。

⑤出栈 :

1° 在前面代码的基础上，定义pop_stack函数完成出栈的操作，需要传入一个PSTACK类型的实参和一个int * 类型的实参（假设出栈的是int类型元素）。其中，int * 类型的指针可以指向保存了出栈元素的值的变量。该函数的返回值类型为bool类型。

2° 出栈，即将栈中的元素拉出来扔掉，必须按照从上往下的顺序出栈，即先进栈的后出栈，后进栈的先出栈。

3° 先对要执行出栈操作的栈进行判断，如果该栈为空，直接false，不为空才执行出栈操作。

4° 如果出栈成功，返回true；否则返回false。

5°具体出栈的流程为：先定义临时PNODE类型变量指向栈顶部的元素；将pTop成员的指针下移一位，令其指向栈当前顶部元素的下一个元素；将要出栈的结点的数据域赋值给实参中int * 类型的变量；free掉临时变量指向的结点；令临时变量为空。

⑥清空栈 :

1° 在前面代码的基础上，定义clear_stack函数完成对栈清空的操作，需要传入要清空的栈的地址值，即PSTACK类型。

2° 注意，清空不是摧毁，清空后，栈依然存在，只不过栈中没有有效元素了。

3° 先利用is_empty函数进行判断，如果栈为空，不进行清空操作。

4° 在clear_stack函数中定义辅助变量p和q（均为PNODE类型），p指向栈顶部的元素。

5° 利用while 循环进行，当p指向的结点不为pBottom指向的结点时——先令q指向p下面的一个元素；再free掉p指向的空间；最后将q的指向传递给p，即令p指向了p的下一个元素；重复此过程，直到p指向栈的底部时，清空完成。

Δ代码演示

# include <stdio.h># include <malloc.h># include <stdlib.h># include <stdbool.h>typedefstructNode{
intdata;
structNode*pNext;
} NODE, *PNODE;
typedefstructStack{
PNODEpTop;
PNODEpBottom;
} STACK, *PSTACK;
//函数声明voidinit_stack(PSTACK);            //初始化栈，创建一个空栈voidpush_stack(PSTACK, int);       //压栈（进栈）voidtraverse_stack(PSTACK);        //完成栈的遍历boolis_empty(PSTACK);              //判断栈是否为空boolpop_stack(PSTACK, int* );     //出栈voidclear_stack(PSTACK);           //清空栈intmain(void)
{
STACKstack;
intval;
init_stack(&stack);
push_stack(&stack, 141);
push_stack(&stack, 11);
push_stack(&stack, 233);
push_stack(&stack, 4);
push_stack(&stack, 5);
push_stack(&stack, 6);
printf("===============遍历栈如下：===============\n");
traverse_stack(&stack);
printf("\n--------------------------------------------------------\n");
printf("当前栈为空吗？");
if (is_empty(&stack))
printf("Yes!");
elseprintf("No!");
printf("\n--------------------------------------------------------\n");
boolb1=pop_stack(&stack, &val);
if (b1)
printf("出栈成功，且出栈元素的值 = %d\n", val);
elseprintf("出栈失败！");
printf("\n--------------------------------------------------------\n");
clear_stack(&stack);
printf("清空栈后，当前栈为空吗？");
if (is_empty(&stack))
printf("Yes!");
elseprintf("No!");
return0;
}
voidinit_stack(PSTACKpStack)
{
pStack->pTop= (PNODE) malloc(sizeof(NODE));
if (NULL==pStack->pTop)
    {
printf("初始化栈时，动态分配内存失败!\n");
exit(-1);
    }
else    {
pStack->pBottom=pStack->pTop;
pStack->pTop->pNext=NULL;
    }
return;
}
voidpush_stack(PSTACKpStack, intval)
{
PNODEpNew= (PNODE) malloc(sizeof(NODE));
if (NULL==pNew)
    {
printf("压栈时，动态分配内存失败！\n");
exit(-1);
    }
pNew->data=val;               //注意 : 栈的指向是从上往下指的。pNew->pNext=pStack->pTop;     //必须让新结点指向栈最上面的一个结点。pStack->pTop=pNew;            //同时让pTop指针后移。return;
}
voidtraverse_stack(PSTACKpStack)
{
PNODEpDemo=pStack->pTop;
while (pDemo!=pStack->pBottom)
    {
printf("%d\t", pDemo->data);
pDemo=pDemo->pNext;
    }
printf("\n");
return;
}
boolis_empty(PSTACKpStack)
{
if (pStack->pTop==pStack->pBottom)
returntrue;
elsereturnfalse;
}
boolpop_stack(PSTACKpStack, int*val)
{
if (is_empty(pStack)) 
    {
returnfalse;
    }
else    {
PNODEpDemo=pStack->pTop;
pStack->pTop=pDemo->pNext;
*val=pDemo->data;
free(pDemo);
pDemo=NULL;
returntrue;
    }
}
voidclear_stack(PSTACKpStack)
{
if (is_empty(pStack))
return;
PNODEq,p=pStack->pTop;
while (p!=pStack->pBottom)
    {
q=p->pNext;
free(p);
p=q;
    }
pStack->pTop=pStack->pBottom;
return;
}

运行结果 :

二、队列

1.概述 :

一种可以实现"先进先出"的存储结构。比如一个杯子底下漏了，你从上面往进倒水，它只能从下面出去，而且先进入杯子内的水一定会先从杯子底下漏出去。只要满足这种条件的存储结构，就可以称为队列。所有和时间有关的操作都与队列有关。

向队列中添加元素称为"入队"，将队列中的元素拿出称为"出队"。（满足"先进先出，后进后出"，类似于排队。）

2.分类 :

链式队列 : 底层用链表实现的队列。

链式队列效果图如下 :

静态队列 ：底层用数组实现的队列。数组的长度决定了队列可使用空间的大小。

静态队列效果图如下 :

静态队列通常都必须是循环队列，即保存数组下标的front和rear是可以循环的。

循环队列的特点，如下效果图所示 :

3.循环队列相关算法 :

①构成循环队列的条件

1° 需要两个参数，分别是front和rear。其中——

当队列初始化时，front和rear的值均为0。

当队列不为空时，front代表的是队列中的第一个元素，rear代表的是队列中最后一个有效元素的下一个元素。

当队列为空时，front和rear的值相等，但不一定为0。

②"入队"

1°将要入队的值存入rear当前代表的位置（即当前队列的最后一个元素的下一个位置）。

2°改变rear 的值，具体操作为——rear = （rear+ 1) % 数组的长度。（取余）

③"出队"

1°改变front 的值，具体操作为——front = （front + 1) % 数组的长度。（取余）

④判断队列是否为空

1° 根据front参数和rear参数的值来判断当前队列是否为空。

2°当front的值和rear的值相等时，当前队列一定为空。

⑤判断队列是否已满

1° 假设数组的长度为10，如果向队列中添加10个元素，即若把某个队列填满，最终会导致front和rear表示的是同一个元素，这与前面判断队列是否为空的条件相矛盾。

解决办法——可以另定义一个变量来保存当前队列中元素的个数，当front和rear的值相等时，增加一个判断，若当前队列中元素的个数不为0，则已满，否则为空。

2°更好的方法——"凡事当留馀地，得意不宜再往"。将数组中的一个位置空下，即少存一个元素。当队列中元素的个数 = 数组长度 - 1时，就认为当前队列已满。并且，随着数组长度越来越长，这一个内存空间的浪费可以忽略不计。

if 语句的判断条件 : (((rear + 1) % 数组的长度) == front).

Δ代码演示 :

# include <stdio.h># include <stdbool.h># include <stdlib.h># include <malloc.h>typedefstructQueue{
int*pBase;            //用于存储元素的数组intfront;              //保存队列中第一个元素的下标intrear;               //用于保存队列中最后一个元素的下一个元素的下标} QUEUE, *PQUEUE;
//函数声明voidinit_queue(PQUEUE);        //初始化队列boolen_queue(PQUEUE, int);     //入队voidtraverse_queue(PQUEUE);    //遍历队列boolis_full(PQUEUE);           //判断当前队列是否已满boolis_empty(PQUEUE);          //判断当前队列是否为空boolout_queue(PQUEUE, int* ); //出队intmain(void)
{
QUEUEqueue;
intval;
printf("当前队列为空吗？");
init_queue(&queue);
if (is_empty(&queue))
printf("Yes!\n");
elseprintf("No!\n");
printf("-------------------------------------\n");
en_queue(&queue, 141);
en_queue(&queue, 11);
en_queue(&queue, 211);
en_queue(&queue, 985);
en_queue(&queue, 5);
printf("===========遍历队列如下:===========\n");
traverse_queue(&queue);
printf("-------------------------------------\n");
printf("当前队列是否已满？");
if (is_full(&queue)) 
printf("Yes!");
elseprintf("No!");
printf("\n-------------------------------------\n");
if (out_queue(&queue, &val))
printf("出队成功！出队的元素 = %d\n", val);
elseprintf("出队失败！\n");
printf("-------------------------------------\n");
printf("===========遍历队列如下:===========\n");
traverse_queue(&queue);
return0;
}
voidinit_queue(PQUEUEpQueue)
{
pQueue->pBase= (int* ) malloc(sizeof(int) *6);
pQueue->front=0;
pQueue->rear=0;
return;
}
boolen_queue(PQUEUEpQueue, intval)
{
if (is_full(pQueue))
returnfalse;
pQueue->pBase[pQueue->rear] =val;
pQueue->rear= (pQueue->rear+1) %6;
returntrue;
}
voidtraverse_queue(PQUEUEpQueue)
{
inti=pQueue->front;
while (i!=pQueue->rear)
    {
printf("%d\t", pQueue->pBase[i]);
i= (i+1) %6;
    }
printf("\n");
return;
}
boolis_full(PQUEUEpQueue)
{
if (((pQueue->rear+1) %6) ==pQueue->front)
returntrue;
elsereturnfalse;
}
boolis_empty(PQUEUEpQueue)
{
if (pQueue->front==pQueue->rear)
returntrue;
elsereturnfalse;
}
boolout_queue(PQUEUEpQueue, int*pVal)
{
if (is_empty(pQueue))
returnfalse;
*pVal=pQueue->pBase[pQueue->front];
pQueue->front= (pQueue->front+1) %6;
returntrue;
}

运行结果：

三、完结撒❀

🆗，以上就是关于栈和队列的全部内容了。up之后可能也会出一些算法题的讲解，不过目前在写java的博文，有时间后或许会考虑。今天就先到这里， 感谢阅读！

System.out.println("END---------------------------------------------------------------");

C 线性结构的两种应用——栈和队列详解

前言

一、栈

1.概述 :

2.分类 :

3.算法:

〇准备工作

①初始化

②压栈（进栈）:

③遍历 :

④判断栈是否为空 :

⑤出栈 :

⑥清空栈 :

Δ代码演示

二、队列

1.概述 :

2.分类 :

3.循环队列相关算法 :

①构成循环队列的条件

②"入队"

③"出队"

④判断队列是否为空

⑤判断队列是否已满

Δ代码演示 :

三、完结撒❀

热门文章

最新文章

相关课程

相关电子书

C 线性结构的两种应用——栈和队列 详解

前言

一、栈

1.概述 :

2.分类 :

3.算法:

〇准备工作

①初始化

②压栈（进栈）:

③遍历 :

④判断栈是否为空 :

⑤出栈 :

⑥清空栈 :

Δ代码演示

二、队列

1.概述 :

2.分类 :

3.循环队列相关算法 :

①构成循环队列的条件

②"入队"

③"出队"

④判断队列是否为空

⑤判断队列是否已满

Δ代码演示 :

三、完结撒❀

热门文章

最新文章

相关课程

相关电子书

C 线性结构的两种应用——栈和队列详解