欢迎各位大佬光临本文章！！！

 

还请各位大佬提出宝贵的意见，如发现文章错误请联系冰冰，冰冰一定会虚心接受，及时改正。

本系列文章为冰冰学习编程的学习笔记，如果对您也有帮助，还请各位大佬、帅哥、美女点点支持，您的每一分关心都是我坚持的动力。

我的博客地址：bingbing~bang的博客_CSDN博客https://blog.csdn.net/bingbing_bang?type=blog

我的gitee：冰冰棒 (bingbingsupercool) - Gitee.comhttps://gitee.com/bingbingsurercool

系列文章推荐

冰冰学习笔记：一步一步带你实现《顺序表》

冰冰学习笔记：一步一步带你实现《单链表》

冰冰学习笔记：一步一步带你实现《双向带头循环链表》 

目录

系列文章推荐

前言

一、栈的实现

1.1结构创建与初始化函数

1.2入栈函数

1.3出栈函数

1.4获取栈顶元素

1.5判断栈是否为空

1.6计算栈空间与栈销毁

二、队列的实现

2.1队列结构创建与初始化函数

2.2入队列函数

2.3出队列函数

2.4获取队头、队尾数据

2.5队列元素个数计算

2.6队列判空与队列销毁

总结

前言

        栈和队列也是数据结构中的一种，二者都可以使用链表或者顺序表实现。对于栈来说，其最大的特点就是数据先入后出，每一个栈都有栈顶和栈底，数据总是放入栈顶，也总是从栈顶拿出。基于这些特点，实现栈最好的方式是使用顺序表，因为我们仅对顺序表进行尾插尾删就可实现栈。

        队列也是一种特殊的线性表。队列的特点是数据遵循先入先出的原则，每个队列都有对头和队尾，数据总是从对尾进入，从队头拿出。相比于栈，队列则更适合使用链表，因为队列在对头出数据更加方便，顺序表需要移动数据，效率太低。

        下面我们开始介绍栈与队列的具体实现方式。

一、栈的实现

        栈，归根结底只是一种特殊的线性表，前面的文章中我们具体介绍了线性表中顺序表的实现方式，因此栈的实现对于我们来说小菜一碟。栈通常的接口含有初始化，入栈，出栈，获取栈顶元素，判断栈是否为空，计算栈的元素个数，栈销毁。

1.1结构创建与初始化函数

        如前文所讲，栈的本质还是顺序表，因此栈的结构中应该包含三个元素：栈的存储数据类型、栈顶元素下标，存储空间大小。

        对于初始化函数，我们也可以一开始就为存储元素的空间开辟一部分，也可以在空间扩容时增加。这里采取的是后面统一扩容的方式，因此初始化函数只需要将top与capacity进行归零操作，然后将a赋值为空指针。

函数代码：

void StackInit(ST* ps){ assert(ps);ps->capacity = ps->top = 0;ps->a = NULL;}

1.2入栈函数

        入栈操作是将数据从栈顶放入，由于我们实现的方式是顺序表，因此我们可以将数组开头视为栈底，数组结尾视为栈顶。因此数据入栈即为将数据插入到数组尾部，也就是顺序表的尾插操作。

        这样一分析，我们的思路就清晰了。插入函数进来一定要先判断原有空间是否充足，能够存储数据，如果不能需要先开辟空间然后将数据存储进去。空间开辟完成后，将插入数据放入到顺序表尾部，也就是栈顶指向的位置，然后更新栈顶top指向的位置。

函数代码：

void StackPush(ST* ps, STDataType x){assert(ps);if ( ps->capacity == ps->top ){int newsize = ps->capacity==0?4:2*ps->capacity;STDataType* tmp = (STDataType*)realloc(ps->a,newsize*sizeof(STDataType));if ( tmp == NULL ){perror("StackPush::realloc");exit(-1);}ps->a = tmp;ps->capacity = newsize;}ps->a[ps->top] = x;ps->top++;}

1.3出栈函数

        由于栈必须满足栈空间的数据从栈顶取出，因此，出栈函数就意味着删除栈顶的元素，及顺序表中数组尾部的元素，也就是尾删。

        实际操作中我们并不需要真正的将内存空间释放，我们只需要将top向后移动即可，这样顺序表访问不到元栈顶的数据，即为删除。注意：此处调用了判空函数，因为只有当栈中含有元素的时候才能正确执行删除数据功能，栈为空，数据无法删除，应直接报错。

函数代码：

void StackPop(ST* ps){assert(ps);assert(!StackEmpty(ps));ps->top--;}

1.4获取栈顶元素

        获取栈顶元素函数与出栈函数不同。出栈函数是将栈空间中栈顶的元素弹出，也就是删除销毁，获取栈顶函数是将栈顶空间保存的数据取出，并不会改变栈空间的数据存储。因此我们只需要将顺序表中top所指向的上一个空间的位置存储的数据返回即可。

函数代码：

STDataType StackTop(ST* ps){assert(ps);assert(!StackEmpty(ps));return ps->a[ps->top-1];}

1.5判断栈是否为空

        我们在判断栈是否为空的函数时使用了布尔类型，如果栈为空则返回true，不是空则返回false。使用布尔类型，我们得先包含头文件，这样C语言才能识别布尔类型。

        我们可以使用top来确定栈空间是否为空，若栈为空，则top必定为0。使用if语句进行判断可以，但是不够简洁，我们完全可以直接返回top==0，如果满足即为真，不满足即为假。

函数代码：

bool StackEmpty(ST* ps){assert(ps);return ps->top == 0;}

1.6计算栈空间与栈销毁

        计算栈空间元素个数的函数比较简单，由于栈是顺序表结构实现的，因此栈顶下标top的大小即为栈空间的元素个数，直接返回即可。

        栈销毁函数就是将开辟的空间进行释放，与顺序表的释放函数一致。

函数代码：

//栈销毁void StackDestroy(ST* ps){assert(ps);free(ps->a);ps->a = NULL;ps->capacity = ps->top = 0;}//计算栈空间元素个数STDataType StackSize(ST* ps){assert(ps);return ps->top;}

二、队列的实现

        队列的性质和栈恰恰相反，队列采用先进先出的原则，插入数据的一端称为队尾，拿出数据的一端称为队头，队列的代码实现中通常包含队列初始化、入队、出队、获取队头元素、获取队尾元素、队列判空、队列元素个数获取、队列销毁。

2.1队列结构创建与初始化函数

        队列的搭建可以采用顺序表或者链表，由于队列需要使用尾增与头删，所以顺序表实现并不划算，原因在于顺序表进行头删的时候，元素需要移动，增加了时间复杂度。在这里我们采用的是链表的结构。

        如图所示，队列的结点中还是和单链表一致，含有存储元素data，以及指向下一个结点的指针next。但是队列结构中含有两个指针，分别为头指针head、尾指针tail，以及一个保存队列元素个数的size变量。head指针指向队列的头，尾指针记录队列的尾，这样数据插入的时候就不用遍历链表找尾部，直接连接在记录尾部的指针tail中。单链表中我们并没有采用此种方式，原因在于队列的性质规定，队列只能从尾部进行数据插入，为了方便可以采用这种情况。但是，单链表中数据插入的方式不仅尾插一种，任意位置的插入还需要遍历寻找指针，此种方式虽能解决尾插，但是意义不大，其他算法还是O(N)。

        队列的初始化函数与单链表相似，初始化时不需要开辟头结点（开辟也可以），只需要将head指针与tail指针指向NULL，size的大小变为0。

函数代码：

//队列初始化void QueueInit(Queue* pq){assert(pq);pq->head = pq->tail = NULL;pq->size = 0;}

2.2入队列函数

        入队列函数本质就是单链表的尾插函数，因为我们队列结构体中包含了记录尾指针的tail指针，因此我们不需要遍历寻找尾指针，直接将新开辟的结点newnode连接到尾指针tail后面即可。队列结构中含有记录元素个数的数据size，因此插入结点后应该将size进行自增。

       注意，由于我们并没有开辟头结点，所以我们需要判断是否为第一次的数据插入，如果是第一次插入数据，tail和head为空，无法将数据直接连接在tail后方，因此需要将数据直接连接在head后面。 

函数代码：

void QueuePush(Queue* pq, QueueDataType x){assert(pq);QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));if ( newnode == NULL ){perror("QueuePush::malloc");exit(-1);}newnode->Data = x;newnode->next = NULL;//第一次插入if (pq->tail == NULL ){pq->head = pq->tail = newnode;}//其他情况else{pq->tail->next = newnode;pq->tail = newnode;}pq->size++;//元素个数自增}

2.3出队列函数

        队列的性质决定了实现队列的链表结构只能采用头删。我们需要将head所指向的结点进行释放，然后将head向后移动成为新的队头，size减少。但是删除之前我们要对队列内容进行检查，检查队列空间是否为空，只有不为空的情况下才能进行删除。

        但是我们要注意只有一个链表结点的情况，此时head和tail均指向该节点，如果直接释放掉head，并将head向后移动，会造成tail指针变为野指针的问题。因此我们需要在释放后，tail指针和head指针一起向后移动。

函数代码：

//队头删除数据void QueuePop(Queue* pq){assert(pq);assert(!QueueEmpty(pq));//只有一个结点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;}pq->size--;//元素个数减少}

2.4获取队头、队尾数据

        队列的数据获取函数是将队头或队尾的数据进行拿出，不改变队列的空间数据结构。获取队头数据直接返回head指针所指向的结点的data，队尾数据则为tail指针指向的结点的data。

        注意：获取数据函数与删除函数一样，都需要判空，空队列没有数据可以获取，调用函数会获取失败。

代码函数：

//队头数据拿出QueueDataType QueueFront(Queue* pq){assert(pq);assert(!QueueEmpty(pq));return pq->head->Data;}//队尾数据拿出QueueDataType QueueBack(Queue* pq){assert(pq);assert(!QueueEmpty(pq));return pq->tail->Data;}

2.5队列元素个数计算

        队列元素个数的计算可以采用遍历队列来获取，但是此种方式的时间复杂度为O(N)，当然也可以定义一个全局变量来进行记录，但是此种状况容易代码混乱。本文采用的方式是在创建队列结构时在结构内部定义了一个size来记录数据个数，不会引起代码混乱。size在插入结点或者删除结点的时候随之变化，因此元素个数可直接返回size。

函数代码：

int QueueSize(Queue* pq){assert(pq);return pq->size;}

2.6队列判空与队列销毁

        判空函数的实现并不复杂，当队列为空时，对应的链表中head指针和tail指针都将指向NULL，我们只需要返回判断即可。

        队列销毁函数就是将队列创建的结点一一释放，其做法与单链表释放一样，采用循环遍历释放即可。

函数代码：

//队列判空bool QueueEmpty(Queue* pq){assert(pq);return pq->head == NULL;}//销毁队列void QueueDestroy(Queue* pq){assert(pq);QueueNode* cur = pq->head;while ( cur){QueueNode* next = cur->next;free(cur);cur = next;}pq->head = pq->tail = NULL;}

总结

        只要了解了顺序表和单链表的结构与功能的实现，栈和队列的实现相对简单。本文采用顺序表实现栈，链表实现队列，但是不代表只能这么实现，仁者见仁智者见智，每种实现方式都有存在的意义。C语言标准并没有明确规定，栈与队列必须使用顺序表还是链表实现，两种实现方式均可，但是顺序表具备尾插尾删的优势，因此栈的实现多半采用该结构。链表更适合头删操作，因此队列多采用该种结构进行实现。顺序表与单链表的具体实现方式可以观看本人的系列文章，已放入推荐文章中。本文所讲解的具体代码已放入仓库中，可自行下载参考。

栈实现代码链接：栈的顺序表结构实现 · 67cbfd9 · 冰冰棒/数据结构仓库 - Gitee.com

队列实现代码链接：队列的实现与队列练习题 · 4ff55d4 · 冰冰棒/数据结构仓库 - Gitee.com