前言：前面已经详细地介绍了基本的顺序表和链表，这次要介绍的是数据结构中的栈与队列。从本质上来说，二者是特殊的线性表，是依赖于顺序表或链表来实现的，所以只要能够很好地掌握顺序表和链表，再了解清楚栈与队列的概念及基本结构，就可以很好地将二者实现出来。

注：由上言以及下文可以知道栈与队列的实现与顺序表，链表的实现大同小异（甚至更简单），一些内容不会详细说明，不清楚的可以再看看以下两篇文章：

（1）顺序表的实现

（2）单链表的实现

目录：

一：栈

1. 栈的概念

2. 栈的结构(图示)

3. 栈的重要接口函数

4. 栈实现相关代码总览

二：队列

1. 队列的概念

2. 队列的结构(图示)

3. 队列的重要接口函数

4. 队列实现相关代码总览

一：栈

1. 栈的概念

(1) 栈: 一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出的原则。 (2) 压栈：栈的插入操作叫做压栈/进栈/入栈，即入数据在栈顶。 (3) 出栈：栈的删除操作叫做出栈。即出数据也在栈顶。

2. 栈的结构(图示)

注：栈一定要遵守先进后出的原则。

3. 栈的重要接口函数

我们可以使用顺序表来实现栈，也可以用链表实现栈，但是链表实现栈有两种方式，一种是头插头删，一种是尾插尾删。而单链表进行尾插尾删时要进行的找尾操作较为复杂(要遍历链表)，所以我们选择顺序表(数组)来实现栈，其结构相对链表而言较为优势。

栈相关的七个重要接口函数：

void StackInit(ST* st);//初始化
void StackPush(ST* st, STDataType x);//入栈
void StackPop(ST* st);//出栈
STDataType StackTop(ST* st);//获取栈顶元素
int StackSize(ST* st);//获取栈中的有效元素个数
bool StackEmpty(ST* st);//判断栈是否为空
void StackDestroy(ST* st);//销毁栈

4. 栈实现相关代码总览

（1）TestStack.c

#define _CRT_SECURE_NO_WARNINGS
#include "Stack.h"void TestStack1()
{ST st;//定义一个栈StackInit(&st);//将栈初始化,要传递结构体指针才能在接口函数内对其进行改变StackPush(&st, 1);StackPush(&st, 2);StackPush(&st, 3);StackPush(&st, 4);//压栈printf("%d\n", StackSize(&st));//打印此时的栈内元素个数while (!StackEmpty(&st))//打印出栈内的所有数据{printf("%d ", StackTop(&st));StackPop(&st);}//一个小疑问：Pop执行后的终点是top=0,但是此时st->a[0]不是等于1吗,这样不是没有删干净吗？printf("\n%d\n", StackSize(&st));StackDestroy(&st);
}void TestStack2()
{ST st;//定义一个栈StackInit(&st);//将栈初始化,要传递结构体指针才能在接口函数内对其进行改变StackPush(&st, 1);StackPush(&st, 2);StackPush(&st, 3);StackPush(&st, 4);printf("%d\n", StackSize(&st));StackPop(&st);StackPop(&st);printf("%d\n", StackSize(&st));//Pop两次后栈内的元素个数while (!StackEmpty(&st)){printf("%d ", StackTop(&st));StackPop(&st);}printf("\n%d\n", StackSize(&st));StackDestroy(&st);
}int main()
{TestStack1();//TestStack2();return 0;
}

（2）Stack.h

#pragma once
#include 
#include 
#include 
#include typedef int STDataType;//定义一个动态增长的数组栈
typedef struct Stack
{STDataType* a;//指针a指向动态开辟的数组int top;//表示栈内的有效元素个数int capacity;//表示栈的空间容量
} ST;//相关接口函数的定义
void StackInit(ST* st);//初始化
void StackPush(ST* st, STDataType x);//入栈
void StackPop(ST* st);//出栈
STDataType StackTop(ST* st);//获取栈顶元素
int StackSize(ST* st);//获取栈中的有效元素个数
bool StackEmpty(ST* st);//判断栈是否为空
void StackDestroy(ST* st);//销毁栈

（3）Stack.c

#define _CRT_SECURE_NO_WARNINGS
#include "Stack.h"void StackInit(ST* st)
{assert(st);st->a = NULL;//top初始化为0时,top指向的是栈顶的下一个数据,因为压栈是先插入数据后top再加1st->top = st->capacity = 0;
}void StackPush(ST* st, STDataType x)//入栈,向栈内插入数据
{assert(st);if (st->top == st->capacity)//判断容量是否足够,不够就扩容{int newCapacity = st->capacity == 0 ? 4 : st->capacity * 2;STDataType* tmp = (STDataType*)realloc(st->a, sizeof(ST) * newCapacity);if (tmp == NULL){printf("realloc fail\n");exit(-1);}st->a = tmp;st->capacity = newCapacity;}st->a[st->top] = x;st->top++;//先插入数据,top再++,即top此时指向的是栈顶的下一个数据
}void StackPop(ST* st)//出栈
{assert(st);//assert(st->top > 0);assert(!StackEmpty(st));//栈不能为空st->top--;
}bool StackEmpty(ST* st)//判断栈是否为空
{assert(st);return st->top == 0;
}STDataType StackTop(ST* st)//获取栈顶元素
{assert(st);return st->a[st->top - 1];//top下标指向的是栈顶的后一个数据
}int StackSize(ST* st)//获取栈内有效数据的个数
{assert(st);return st->top;
}void StackDestroy(ST* st)//销毁栈
{assert(st);while (!StackEmpty(st)){StackPop(st);}st->a = NULL;st->top = st->capacity = 0;
}

二：队列

1. 队列的概念

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

2. 队列的结构(图示)

 注：队列一定要遵守先进先出的原则。

3. 队列的重要接口函数的实现

与栈相同，队列既可以通过顺序表来实现，也可以通过链表实现。但与栈实现起来不同的是，对于队列而言，链表的结构更适合它，因为队列主要涉及到的是头部尾部的插入与删除，而顺序表(数组)实现起来的效率会更低一些。

这里需要特别说明的是：选用的是单链表，并且我们需要给这个单链表定义好头节点 (head)和尾节点(tail)，将它们作为队列的基本框架，以形成一个较好头插尾删的单链表。

图示：

代码说明：

队列相关接口函数：

void QueueInit(Queue* pq);//初始化队列
void QueuePush(Queue* pq, QDataType x);//入队列
void QueuePop(Queue* pq);//出队列
bool QueueEmpty(Queue* pq);//判断队列是否为空
int QueueSize(Queue* pq);//返回队列中有效数个数
QDataType QueueFront(Queue* pq);//获取队头数据
QDataType QueueBack(Queue* pq);//获取队尾数据
void QueuePrint(Queue* pq);//打印队列(同时会清空队列的元素)
void QueueDestroy(Queue* pq);//销毁队列中动态开辟节点的链表

4. 队列实现相关代码总览

(1) TestQueue.c

#define _CRT_SECURE_NO_WARNINGS
#include "Queue.h"void TestQueue1()
{Queue q;QueueInit(&q);QueuePush(&q, 1);QueuePush(&q, 2);QueuePush(&q, 3);QueuePush(&q, 4);printf("%d\n", QueueSize(&q));//打印此时队列内的元素个数QueuePop(&q);QueuePop(&q);printf("%d\n", QueueSize(&q));//打印此时队列内的元素个数QueuePrint(&q);//QueuePrint函数调用的同时会清空队列printf("\n%d\n", QueueSize(&q));QueueDestroy(&q);
}void TestQueue2()
{Queue q;QueueInit(&q);QueuePush(&q, 5);QueuePush(&q, 6);QueuePush(&q, 7);QueuePush(&q, 8);//打印此时队列元素个数,队头数据,对尾数据printf("%d %d %d\n", QueueSize(&q), QueueFront(&q), QueueBack(&q));QueuePrint(&q);//QueuePrint函数调用的同时会清空队列printf("\n%d\n", QueueSize(&q));QueueDestroy(&q);
}int main()//各个接口函数功能的测试
{TestQueue1();//TestQueue2();return 0;
}

(2) Queue.h

#pragma once
#include 
#include 
#include 
#include typedef int QDataType;//用单链表实现队列(定义队列中的链表结构)
typedef struct QueueListNode
{struct QueueListNode* next;//指针域QDataType data;//数据域
} QLNode;//为了更好地实现单链表的头删(出队列)与尾插(入队列),在队列的链表结构中在定义一个头节点与尾节点,可以表示队列的结构
typedef struct Queue
{QLNode* head;QLNode* tail;
} Queue;//队列相关接口函数的定义
void QueueInit(Queue* pq);//初始化队列
void QueuePush(Queue* pq, QDataType x);//入队列
void QueuePop(Queue* pq);//出队列
bool QueueEmpty(Queue* pq);//判断队列是否为空
int QueueSize(Queue* pq);//返回队列中有效数个数
QDataType QueueFront(Queue* pq);//获取队头数据
QDataType QueueBack(Queue* pq);//获取队尾数据
void QueuePrint(Queue* pq);//打印队列(同时会清空队列的元素)
void QueueDestroy(Queue* pq);//销毁队列中动态开辟节点的链表

(3) Queue.c

#define _CRT_SECURE_NO_WARNINGS
#include "Queue.h"void QueueInit(Queue* pq)//队列初始化
{assert(pq);pq->head = NULL;pq->tail = NULL;
}void QueuePrint(Queue* pq)//打印整个队列的元素(同时会清空队列的元素)
{assert(pq);while (!QueueEmpty(pq)){printf("%d ", QueueFront(pq));QueuePop(pq);//只有清理了对头元素,才可以继续向后读取数据}
}void QueuePush(Queue* pq, QDataType x)//入队列(单链表的尾插)
{QLNode* newnode = (QLNode*)malloc(sizeof(QLNode));//开辟新节点if (newnode == NULL){printf("malloc fail\n");exit(-1);}newnode->next = NULL;newnode->data = x;//节点入列的两种情况if (pq->head == NULL)//1.原队列为空{pq->head = pq->tail = newnode;newnode->next = NULL;}else//原队列不为空{pq->tail->next = newnode;pq->tail = newnode;pq->tail->next = NULL;}
}void QueuePop(Queue* pq)//出队列,单链表的头删
{assert(pq);assert(!QueueEmpty(pq));//删除时队列不能为空QLNode* next = pq->head->next;free(pq->head);pq->head = next;
}bool QueueEmpty(Queue* pq)//判断队列是否为空
{assert(pq);return pq->head == NULL;
}int QueueSize(Queue* pq)//返回队列中有效数个数
{assert(pq);QLNode* cur = pq->head;int num = 0;while (cur)//遍历队列中的单链表{num++;cur = cur->next;}return num;
}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;
}void QueueDestroy(Queue* pq)//销毁队列中动态开辟节点的链表
{assert(pq);while (pq->head){QLNode* next = pq->head->next;free(pq->head);pq->head = next;}
}

总结：

栈与队列的实现最重要的是结构以及对链表，顺序表的理解程度，这里再强调一次：数据结构的学习中结构的理解十分重要，所以我们可以多画画相关的图，再结合图理解这样一定可以事半功倍。栈与队列的介绍就到这里结束，谢谢大家的阅读，再见。