C语言编程数据结构栈与队列的示例分析(c语言,开发技术)

一、栈的表示和实现

1栈的概念和结构

栈：一种特殊的线性表（逻辑上数据是连着放的），其只允许在固定的一端进行插入和删除操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵循后进先出的原则。
压栈：栈的插入操作叫作进栈/压线/入线，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。

（图片来自比特就业课）

先入后出就类似与你装手枪弹夹，你先放入的子弹会在弹夹底部，最后放入的子弹是在弹夹顶部，你开手枪是先打出弹夹顶端的子弹。
我们这里先定义一个栈的类型：

typedefintSTDataType;//方便将来如果需要其他类型的数据，可以直接修改int的类型typedefstructStack{ STDataType*a;//栈底指针 inttop;//栈顶标号 intcapacity;//容量}ST;

本文介绍以顺序表（数组）实现栈，由此，所谓的入栈压栈也不过是顺序表的尾插尾删，如果读者想以链表实现也是可以的，方法不唯一。

2栈的初始化

关于栈的初始化：我们这里以容量大小4的栈为例，刚开始因为栈里没有数据我们用top=0标记，需要注意的是：传过来的栈底指针不能为空，开辟空间时万一没有开辟成功返回一个空指针也要丢弃。

#include<assert.h>#include<stdlib.h>//malloc函数头文件voidStackInit(ST*ps)//栈初始化{ assert(ps);//防止传过来的指针是空指针 ps->a=(STDataType)malloc(sizeof(STDataType)*4);//malloc开辟一块空间出来，由STDataType类型进行管理 //malloc，及后文出现的realloc、free函数详情见笔者动态内存管理文章 if(ps->a==NULL) { printf("reallocfail\n"); exit(-1);//终止程序 } ps->capacity=4; //这里以开辟4个数据容量大小的栈为例，你也可以写其他数字 //如果压栈的时候内存不够，可以在后面提到的压栈函数里面进行扩容 ps->top=0;//刚开始栈里没有值时，用top=0标记，后续每放入一个top++ //关于top详细用法请往下看1.3压栈部分}

3压栈(栈顶插入一个数据)

如上图，我们现在开辟了一块空间，a和top都在栈顶，我们往里面入一个数据1

1进入栈之后，1就是栈顶元素了，那如果我想继续入栈，就是要在top的位置放入一个数据让新放入的数据成为新的栈顶元素，然后以此类推，每次入一个元素，top++，top不是表示栈顶元素位置，而是栈顶元素下一个位置。

#include<assert.h>//assert函数头文件#include<stdlib.h>//realloc函数头文件voidStackPush(ST*ps,STDataTypex)//栈顶插入数据（入栈）{ assert(ps); if(ps->top==ps->capacity) { STDataType*tmp=realloc(ps->a,ps->capacity*2*sizeof(STDataType)); //realloc是在原先开辟的空间上继续往后开辟一块空间，详细见笔者动态内存文章 //扩容一般扩2倍 if(tmp==NULL)//扩容失败（比如内存已经不够你再开辟空间了）会返回空指针 { printf("reallocfail\n"); exit(-1);//终止程序 } else { ps->a=tmp; ps->capacity*=2; } } ps->a[ps->top]=x;//a是一个指针，a[x]==*(a+x) ps->top++;}

4出栈(栈顶删除一个数据)

出栈非常简单，我们以下图为例：

图中我们栈里已经存放了4个数据1、2、3、4，那我们现在要进行出栈操作,也就是删除4怎么办？直接top–即可

到这里肯定会有小伙伴有疑问，凭什么你top–一下就是出栈了，你4都没删除啊？解释如下：我们在1.3压栈部分就说过“top不是表示栈顶元素位置，而是栈顶元素下一个位置”，那现在我top在4这里，说明3才是真正的栈顶元素，4已经不在栈的管辖范围内了。

voidStackPop(ST*ps)//栈顶删除数据（出栈）{ assert(ps); assert(ps->top>0);//栈空了，调用Pop，直接中止程序报错 ps->top--;}

关于ps->top > 0，是这样的：假设你原先栈里没有有一个元素

你top–就是往下访问未知的领域了，这是非常严重的问题，所以我们这里用assert断言一下，防止栈里什么元素也没有让top标记到了未知领域。（再次强调一下：top不是表示栈顶元素位置，而是栈顶元素下一个位置）

5取栈顶元素

STDataTypeStackTop(ST*ps)//取栈顶数据{ assert(ps); assert(ps->top>0);//栈空了，调StackTop，直接中止程序报错 returnps->a[ps->top-1];//top是栈顶元素下一个位置,top-1是栈顶元素 //a[m]==*(a+m)}

这里的思路和1.4几乎一样，也要防止栈里什么也没有的情况，然后正常返回栈顶元素即可，因为top是栈顶元素下一个位置,top-1是栈顶元素，然后你正常写就行，这里的
a[ps->top - 1]你也可以写成*(a+(ps->top - 1)),这个写法读者可参加笔者以前的指针文章，这里不再赘述。

6取栈顶元素

intStackSize(ST*ps)//栈的数据个数{ assert(ps); returnps->top;}

这个就更简单了，直接返回top的值就可以了，为什么呢，我们看两张图即可
图一：

图二：

图一是压栈前，没有一个元素，top=0，图二是压栈后，top++，top=1。同样的以此类推，我们每加入1个元素，top++，每减去一个元素，top–。元素个数永远=top值，所以我们这里的函数直接返回top值即可。

7判断栈是否为空

intStackEmpty(ST*ps)//判断栈是不是空{ assert(ps); returnps->top==0;}

由1.6知，我们的top值是和栈里元素个数一样的，所以我们直接return ps->top == 0；即可，如果ps->top == 0这个表达式成立表达式值为1，反之为0。

二、队列的表示和实现

1队列的概念及结构

队列：只允许在一端插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出的性质
入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为队头

（图片来自比特就业课）

类似你走人工通道那样，你排在前面的，你先出去

2队列的实现

由于队列的队头出，队尾入，非常类似单链表的头删和尾插，我们这里介绍以单链表实现队列，如下图，现有3个节点的单链表：

比如现在，我要队头出一个，也就是把单链表节点第一个节点删掉（头删）

或者队尾入一个，也就是单链表的尾插

代码如下（示例）：

typedefintQDataType;typedefstructQueueNode{ structQueueNode*next; QDataTypedata;}QNode;//这里和单链表定义一样，有需要的可以看一下笔者之前的单链表文章typedefstructQueue//定义一个结构体存储头节点地址和尾节点地址，方便后面头删和尾插{ QNode*head; QNode*tail;}Queue;

3队列初始化

代码如下（示例）：

voidQueueInit(Queue*pq)队列初始化,pq是一个结构体指针{ assert(pq);//判断pq是否是空指针 pq->head=NULL; pq->tail=NULL;}

4入队（队尾插入一个数据）

voidQueuePush(Queue*pq,QDataTypex)//入队（队尾入）{ assert(pq); QNode*newnode=(QNode*)malloc(sizeof(QNode));//开辟出一块空间给newnode if(newnode==NULL)//有可能剩余内存不够开辟空间，malloc开辟失败会返回空指针 { printf("开辟空间失败\n"); exit(-1);//退出程序 } newnode->data=x; newnode->next=NULL; if(pq->tail==NULL)//原先队列里没有任何数据，头和尾指针都指向NULL { pq->head=pq->tail=newnode; } else { pq->tail->next=newnode; pq->tail=newnode; }}

关于下面if这段代码解释如下：

if(pq->tail==NULL) { pq->head=pq->tail=newnode; } else { pq->tail->next=newnode; pq->tail=newnode; }

原先队列里没有任何数据，头和尾指针都指向NULL

当你往队列里面放了一个数据，头和尾指针是指向新的数据（头和尾指针仍指向一个）

如果你想再加1个节点，你首先得把两节点连上，也就是pq->tail->next = newnode;（没接上之前tail还指向第一个节点），接上之后tail指针指向第二节点

5出队（队头删除一个数据）

voidQueuePop(Queue*pq)//出队（队头出）{ assert(pq); assert(pq->head);//要出队，队里也要有数据可以出 //原队列只有1个数据 if(pq->head->next==NULL) { free(pq->head); pq->head=pq->tail=NULL; } //原队列有多个数据 else { QNode*next=pq->head->next; free(pq->head); pq->head=next; }}

关于出队，这里要分2种情况讨论：

1.原队列只有1个数据

只有一个数据的时候，头和尾指针都指向1节点，他们的next是空指针，所以我们以这个条件为判断。又因为要出队（队头删除一个数据），因为只有一个节点，也就是把这个节点给删掉，我们用free函数释放掉head指向的空间。释放完，那块空间已经还给内存了，这时你的头和尾指针就不能指向那块空间了，我们用空指针赋值。
2.原队列有多个数据

我们现在要出队（队头删除一个数据），也就是把1节点删掉，我们先创建一个变量next找到2节点位置，然后free掉1节点的空间

1节点空间free掉之后，把next（指向2节点）赋给head，让头指针指向2节点。

6取队头数据

QDataTypeQueueFront(Queue*pq)//取队头数据{ assert(pq); assert(pq->head); returnpq->head->data;}

7取队尾数据

QDataTypeQueueBack(Queue*pq)//取队尾数据{ assert(pq); assert(pq->head); returnpq->tail->data;}

8计算队列中数据个数

intQueueSize(Queue*pq)//队内数据个数{ assert(pq); intsize=0; QNode*cur=pq->head; while(cur)//cur!=NULL进行循环,NULL是遍历完tail之后出现的 { size++; cur=cur->next; } returnsize;}

9判断队列是否为空

boolQueueEmpty(Queue*pq){ assert(pq); returnpq->head==NULL;}

这一般是作为一个辅助函数来使用，bool 就是用来判断真假的数据类型，如果表达式：pq->head == NULL成立返回true,反之返回false

10销毁队列

voidQueueDestory(Queue*pq)//队列销毁{ assert(pq); QNode*cur=pq->head; while(cur)//cur!=NULL进行循环,NULL是遍历完tail之后出现的 { QNode*next=cur->next; free(cur);//free是释放指向的空间，指针还是在的 cur=next; } pq->head=pq->tail=NULL;}

如上图，我们创建一个变量cur并用head指针赋值。然后找到第二个节点，用cur->next标记,标记完我们释放掉cur（释放的第一个节点空间,指针还是在的），释放完，cur开始遍历第二个节点，也就是我们先前用next标记的空间。。。剩下的以此类推。cur!=NULL进行循环,NULL是遍历完tail之后出现的，当循环不进行说明已经遍历完了尾指针指向的节点，头和尾节点已经不需要了，我们用空指针赋值。