目录

一:栈

(1)什么是栈

(2)栈的两种实现方式

(3)栈的一些基本接口实现

【1】栈的结构体和初始化

【2】入栈

【3】销毁

【4】出栈

【5】判断栈是否为空

【6】取顶部数据

【7】取栈中有效数据的个数

【8】栈的全部代码

二:队列

(1)什么是队列

(2)队列的两种实现方式

(3)队列的一些基本接口实现

【1】队列的结构体和初始化

【2】入队列

【3】销毁队列

【4】判断队列是否为空

【5】出队列(删除数据)

【6】查找队列的头尾数据

【7】查找队列的结点个数

【8】队列的全部代码

三:小结


一:栈

(1)什么是栈

【1】栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。 进行数据插入和删除操作的一端 称为栈顶,另一端称为栈底 栈中的数据元素 遵守后进先出 LIFO Last In First Out )的原则。 【2】压栈:栈的插入操作叫做进栈 / 压栈 / 入栈, 入数据在栈顶 【3】出栈:栈的删除操作叫做出栈。 出数据也在栈顶 图解:

(2)栈的两种实现方式

链式栈:用链表的结构来实现栈。

顺序栈:数组的结构来实现栈。

优劣对比:

【1】单向链式结构的出栈入栈(删除插入)效率比较低,因为我们要先找到尾结点再行插入删除,可以通过双向链表或者将单向链表的头结点当作栈顶来处理。

【2】顺序栈只需要记录栈顶位置(同时也是有效元素个数)进行出栈入栈(尾插尾删)十分方便,而且不需要多余的空间存储地址

综上所述:在栈的实现中数组的结构实现更优一些因为数组在尾上插入数据的代价比较小。

(3)栈的一些基本接口实现

【1】栈的结构体和初始化

结构体:

注:改变结构体的变量只需要传入结构体指针。

初始化:

【2】入栈

基础思路:

①根据有效数据个数(top)和最大容量来判断是否扩容

存储数据

有效数据个数和最大容量进行更新

图解:

代码:

【3】销毁

思路:销毁很简单,因为空间是连续的,注意把栈顶位置(top)和最大容量置0就行。

代码:

【4】出栈

思路:

①栈顶其实是我们数组的尾,我们直接将top(有效数据个数)减一就行(数据失联)

②注意如果栈为空就不能在减了,不然会是top=-1,造成越界访问

代码:

【5】判断栈是否为空

思路:根据top判断,为0就是空栈,返回true,否则返回false。(注意包头文件stdbool.h)

代码:

【6】取顶部数据

思路:

①我们现在有有效数据个数,将它减一就得到顶部数据的下标,直接用下标访问,然后返回这个数据就行。

②栈为空不能用下标访问,不然会越界

代码:

【7】取栈中有效数据的个数

思路:很简单,直接返回top就行。

代码:

【8】栈的全部代码

stack.h(头文件)

#pragma once#include #include #include #include //重定义数据类型,方便更改typedef int STDataType;typedef struct stack {//存储数据STDataType* a;//栈顶(位置)int top;//容量int capacity;}ST;//初始化void StackInit(ST* ps);//销毁void StackDestroy(ST* ps);//入栈void StackPush(ST* ps, STDataType x);//出栈(销毁)void StackPop(ST* ps);//取栈顶的数据STDataType StackTop(ST* ps);//取栈中的有效数据个数int StackSize(ST* ps);//判断栈是否为空bool StackEmpty(ST* ps);

stack.c(接口实现)

#define _CRT_SECURE_NO_WARNINGS 1#include "stack.h"//初始化void StackInit(ST* ps){//断言,不能传空指针进来assert(ps );//一开始指向NULLps->a = NULL;//把栈顶和容量都置为空ps->top = ps->capacity = 0;}//销毁void StackDestroy(ST* ps){//断言,不能传空指针进来assert(ps );//栈顶和容量置为空ps->top = ps->capacity = 0;//释放空间free(ps->a);ps->a = NULL;}//入栈void StackPush(ST* ps, STDataType x){//断言,不能传空指针进来assert(ps);//先判断是否扩容if (ps->top == ps->capacity){int newcapacity = ps->capacity == 0 " />capacity = newcapacity;ps->a = tmp;}//存储数据ps->a[ps->top] = x;ps->top++;}//出栈(删除)void StackPop(ST* ps){//断言,不能传空指针进来assert(ps);//如果栈为空,不能出栈assert(!StackEmpty(ps));ps->top--;}//取顶部数据STDataType StackTop(ST* ps){//断言,不能传空指针进来assert(ps);//如果栈为空,不能进行访问assert(!StackEmpty(ps));//返回栈顶数据return ps->a[ps->top-1];}//取栈中的有效数据个数int StackSize(ST* ps){//断言,不能传空指针进来assert(ps);//直接返回topreturn ps->top;}//判断栈是否为空bool StackEmpty(ST* ps){//断言,不能传空指针进来assert(ps);//依据top来判断/*if (ps->top == 0)return true;return false;*///更简洁的写法,一个判断语句的值要么为true,要么falsereturn ps->top == 0;}

text.c(测试,写接口最好写一测一)

#define _CRT_SECURE_NO_WARNINGS 1#include "stack.h"void text1(){ST s1;StackInit(&s1);StackPush(&s1, 89);StackPush(&s1, 109);while (!StackEmpty(&s1)){printf("%d ", StackTop(&s1));//出栈StackPop(&s1);}//测试结束,及时释放空间StackDestroy(&s1);}void text2(){ST s;StackInit(&s);StackPush(&s, 5);StackPush(&s, 48);StackPush(&s, 88);StackPush(&s, 85);int a = StackSize(&s);printf("%d\n", a);StackPop(&s);StackPop(&s);StackPop(&s);StackPop(&s);bool t=StackEmpty(&s);if (t)printf("为空\n");elseprintf("不为空\n");//测试结束,及时释放空间StackDestroy(&s);}int main(){//text2();text1();return 0;}

二:队列

(1)什么是队列

【1】队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出 FIFO(First In First Out)的特性。

【2】入队列:进行插入操作的一端称为队尾

【3】出队列:进行删除操作的一端称为队头

图解:

(2)队列的两种实现方式

【1】和栈类似,队列也可以用数组和链表的结构实现。 【2】数组实现的队列每一次入队都要将数据前移一位,而链表实现的队列入队不需要大量的移动数据,效率更高。

(3)队列的一些基本接口实现

【1】队列的结构体和初始化

结构体:与原先我们实现的链表小有不同,我们要取到队列的最后一个结点的数据或者进行入队,都需要得到尾结点的地址,所以我们可以另外声明一个结构体,其中一个变量为我们熟悉的头指针,一个为记录尾结点地址的尾指针。(也可以不声明这个结构体,但要定义两个结构体指针,一个头和一个尾,函数传参要同时传入这两个指针)

图解:

初始化:

【2】入队列

思路:

申请新结点并存储数据(注意新结点指针域指空)。

扩容加链接加尾结点更新

③一定要对空队列进行单独处理,不然会对空指针解引用。

代码:

【3】销毁队列

思路:

①和单链表类似,从头结点开始,一个个往后删除

②注意记录下一个结点位置再释放

③要把头和尾都进行置空(避免野指针)。

图解:

代码:

【4】判断队列是否为空

思路:根据头指针是否为空来进行判断

代码:

【5】出队列(删除数据)

思路:

保存原头结点的下一个结点再释放,然后更新头指针

②注意队列为空的时候不能进行删除,不然会对空指针解引用。

③有一个比较隐性的bug,那就是进行了多次删除一直到把队列删空,头指针置空了但是尾指针没有置空,存在野指针的问题。

隐性bug图解:

代码:

【6】查找队列的头尾数据

思路:

①很简单,直接返回头结点和尾结点的数据

注意队列为空时不能查找,不然会对空指针解引用。

代码:

【7】查找队列的结点个数

一样有两种实现方法:

定义一个计数变量并遍历整个链表直至空。

②在队列结构体中多声明一个size变量来记录,初始化为0,每次出入队列都进行更新

本文采用第一种

代码:

【8】队列的全部代码

Queue.h

#pragma once#include #include #include #include //重定义,方便更改存储类型typedef int QDataType;//结点的结构体typedef struct QueueNode{struct QueueNode* next;QDataType data;}QNode;//队列的结构体(头用来开辟链接,尾用来查找)typedef struct Queue{//头QNode* head;//尾QNode* tail;}Queue;//队列的初始化void QueueInit(Queue* pq);//入队列(队列只能从后入)void QueuePush(Queue* pq, QDataType x);//队列的销毁void QueueDestroy(Queue* pq);//出队列(删除)void QueuePop(Queue* pq);//判断队列是否为空bool QueueEmpty(Queue* pq);//查找队列的头数据QDataType QueueFront(Queue* pq);//查找队列的尾数据QDataType QueueBack(Queue* pq);//查找队列的结点个数int QueueSize(Queue* pq);

Queue.c(接口实现)

#define _CRT_SECURE_NO_WARNINGS 1#include "Queue.h"//初始化void QueueInit(Queue* pq){//断言,不能传空的结构体指针assert(pq);//初始化,把头和尾都指向空pq->head = pq->tail = NULL;}//入队列void QueuePush(Queue* pq,QDataType x){//断言,不能传空的结构体指针assert(pq);//申请新结点QNode* newnode = (QNode*)malloc(sizeof(QNode));newnode->data = x;newnode->next = NULL;//如果队列为空,单独处理if (pq->head == NULL){pq->head = pq->tail = newnode;}else{//原尾指向新结点(链接)pq->tail->next = newnode;//更新尾pq->tail = newnode;}}//队列销毁void QueueDestroy(Queue* pq){//断言,不能传空的结构体指针assert(pq);//先保存下一个,再释放QNode* cur = pq->head;while (cur){//记录QNode* next = cur->next;//释放free(cur);//迭代cur = next;}//头尾都置空pq->head = pq->tail = NULL;}//出队列(删除)void QueuePop(Queue* pq){//断言,不能传空的结构体指针assert(pq);//断言,队列为空不能删除assert(!QueueEmpty(pq));//保存原头的下一个结点位置QNode* newhead = pq->head->next;//释放free(pq->head);//迭代pq->head = newhead;//如果删除结束了,要把tail指向空(避免野指针)if (pq->head == NULL)pq->tail = NULL;}//判断队列是否为空bool QueueEmpty(Queue* pq){//断言,不能传空的结构体指针assert(pq);/*if (pq->head == NULL)return true;elsereturn false;*///依据判断语句的指直接返回return pq->head == NULL;}//查找队列的头数据QDataType QueueFront(Queue* pq){//断言,不能传空的结构体指针assert(pq);//断言,队列为空不能查找assert(!QueueEmpty(pq));return pq->head->data;}//查找队列的尾数据QDataType QueueBack(Queue* pq){//断言,不能传空的结构体指针assert(pq);//断言,队列为空不能查找assert(!QueueEmpty(pq));return pq->tail->data;}//查找队列的结点个数int QueueSize(Queue* pq){//断言,不能传空的结构体指针assert(pq);//计数int size = 0;//遍历链表QNode* cur = pq->head;while (cur){size++;cur = cur->next;}return size;}

text.c(测试)

#define _CRT_SECURE_NO_WARNINGS 1#include "Queue.h"//测试void text1(){Queue Q;QueueInit(&Q);QueuePush(&Q, 80);QueuePush(&Q, 60);QueuePush(&Q, 40);QueuePush(&Q, 70);QueuePop(&Q);QueuePop(&Q);QueuePop(&Q);QueuePop(&Q);bool a = QueueEmpty(&Q);//QueueDestroy(&Q);}void text2(){Queue Q2;QueueInit(&Q2);queuepush(&Q2, 80);queuepush(&Q2, 60);queuepush(&Q2, 100);queuepush(&Q2, 67);printf("%d ", queuefront(&Q2));printf("%d ", queueback(&Q2));int size=QueueSize(&Q2);}int main(){//text1();text2();return 0;}

三:小结

相较于链表,栈和队列的实现更加简单,但有关栈和队列的面试题还是比较难的,下一次我们就会在这一次的基础上完成一些比较经典的OJ题目