系列文章目录
第一章 顺序表、链表
第二章 栈和队列
第三章 二叉树
第四章 八大排序
文章目录
前言
学习栈和队列之前，首先我们要知道，如果说顺序表和链表只是一种数据在内存中不同的存储结构，那么栈和队列就是对内存空间的不同的管理结构。所以栈和队列都可以用顺序表或者链表实现，不同的存储结构并不影响栈和队列对内存空间的管理，只是在代码实现上会有所不同。下面让我们一起来看看吧。
一、栈
什么是栈呢？大家都知道，我们的内存空间大致有不同的几个区域，分别是栈区、堆区及静态区。栈区中一般存储的是我们程序中的局部变量、函数栈帧等，堆区一般存储的是动态开辟的空间，而静态区一般存储的是static修饰的静态变量。那这里的栈和我们要学习的栈有什么关联吗？其实是没有关联的，如果说什么相关的话，那么也就是名字一样而已。
1.1 栈的概念和结构
什么是栈？
栈：是一种特殊的线性表，只允许在固定的一端进行插入和删除数据。插入和删除数据的一端叫做栈顶，另一端叫做栈底。 栈有一个原则，叫做后进先出LIFO(Last In First Out)。栈就像我们坐电梯，最先进去的最后出来。
后进先出原则是学习栈非常重要的内容。理解了这个你才能更好的学习栈。
栈的两个基本操作：
- 压栈：栈的插入操作叫做压栈/入栈/进栈。在栈顶入数据
- 出栈：栈的删除操作叫做出栈。在栈顶出数据
栈的结构：
栈的底层逻辑存储结构可以用两种方式，顺序表和链表。无论用那种方式都可以，只是在实现上会有区别。当然，不同的存储结构也有不同的好处，而栈的底层存储结构一般建议用数组(也就是顺序表)实现。因为相对于链表，数组更能适应栈的结构——数组的尾插代价更小。
1.2 栈的实现
我们用数组来实现栈。数组的首部我们当做栈底，尾部当做栈顶。
这里就体现出了数组实现的好处，数组对尾部的访问可以直接访问，而链表则不可以直接访问。当然也不是说链表就不好，如果用链表实现，我们可以将链表的头当做栈顶，尾当做栈底，在链表的头部插入/删除数据，代价也比较低。只是数组的结构更符合栈的特性，所以我们建议用数组来实现栈。
栈的实现
// 下面是定长的静态栈的结构，实际中一般不实用，所以我们主要实现下面的支持动态增长的栈
typedef int STDataType;
#define N 10
typedef struct Stack
{
STDataType a[N];
int top; // 栈顶
}Stack;
//动态的栈
typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top; //用top表示栈顶
int capacity;
}Stack;
//初始化栈
void StackInit(Stack* ps);
//销毁栈
void StackDestory(Stack* ps);
//入栈
void StackPush(Stack* ps,STDataType x);
//出栈
void StackPop(Stack* ps);
//显示栈顶数据
STDataType StackTop(Stack* ps);
//获取栈中元素个数
int StackSize(Stack* ps);
//检查栈是否为空
bool StackEmpty(Stack* ps);
1.2.1 初始化栈
栈的初始化没什么好说的，和顺序表的初始化基本没什么区别。
void StackInit(Stack* ps)
{
assert(ps);
ps->capacity = 4;
ps->a = (STDataType*)malloc(sizeof(STDataType) * ps->capacity);
if (ps->a == NULL)
{
perror("StackInit fail");
exit(-1);
}
ps->top = 0;
}
1.2.2 销毁栈
栈的销毁和初始化这两个接口都没什么好说的，代码也很简单。
void StackDestory(Stack* ps)
{
free(ps->a);
ps->a = NULL;
ps->capacity = 0;
ps->top = 0;
}
1.2.3 入栈
入栈接口的实现要符合栈的特性：只在栈顶入数据。用数组实现就很简单，数组尾部当做栈顶，头部当做栈底。然后插入数据（入栈）即可。
注意也要判断栈是否满了。
void StackPush(Stack* ps, STDataType x)
{
assert(ps);
//满了进行扩容
if (ps->top == ps->capacity)
{
STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * ps->capacity * 2);
if (tmp == NULL)
{
perror("Expansion fail");
exit(-1);
}
ps->a = tmp;
ps->capacity *= 2;
}
//栈顶入数据
ps->a[ps->top] = x;
ps->top++;
}
1.2.4 出栈
出栈的逻辑就不用说了，直接让top自减就可以。
void StackPop(Stack* ps)
{
assert(ps);
ps->top--;
}
但是这里就有一个问题，直接出栈后我们就拿不到栈顶的数据了，所以在出栈前我们要将栈顶的元素存起来，这就是下一个接口。
1.2.5 获取栈顶元素
直接返回栈顶元素就可以。
STDataType StackTop(Stack* ps)
{
assert(ps);
return ps->a[ps->top - 1];
}
1.2.6 获取栈中的元素个数
top就是栈中的元素个数。
int StackSize(Stack* ps)
{
assert(ps);
return ps->top;
}
1.2.7 检查栈是否为空
top为0栈就为空。
bool StackEmpty(Stack* ps)
{
assert(ps);
return ps->top == 0;
}
以上就是栈的实现，我们可以发现，栈的结构其实是很简单的，实现也非常简单。队列其实也差不多，下面我们来看看队列吧。
二、队列
2.1 队列的概念和结构
什么是队列？
队列就像我们现实中排队一样，假如我们要去银行办理业务，就需要排队，先排队的先处理业务，后排队的后处理业务。而队列也是如此。
队列：只允许在一端进行插入数据，在另一端进行删除数据的特殊线性表。队列的原则是先进先出FIFO（First In First Out）。进行插入操作的一端叫做队头，进行删除操作的一端叫做队尾
队列的结构：
队列的底层逻辑存储结构也一样，顺序表或者链表都可以。但由于队列的特性，一般建议用链表实现队列。因为队列需要在队头出数据，而顺序表在头部出代价较大，要挪动整个数组，因此建议用链表。
那么用链表实现队列的话，结构就稍微复杂一点，因为会有许多细节需要注意，下面我们来看看队列的实现吧。
2.2 队列的实现
typedef int QDataType;
typedef struct QueueNode
{
struct QueueNode* next;
QDataType data;
}QNode;
typedef struct Queue
{
QNode* head;
QNode* tail;
int size; //给一个size表示队列的大小，在一些接口的实现上会简单许多，不是必须要有
}Queue;
//初始化队列
void QueueInit(Queue* pq);
//销毁队列
void QueueDestroy(Queue* pq);
//入队列
void QueuePush(Queue* pq, QDataType x);
//出队列
void QueuePop(Queue* pq);
//显示队列头元素
QDataType QueueFront(Queue* pq);
//显示队列尾元素
QDataType QueueBack(Queue* pq);
//检测队列是否为空
bool QueueEmpty(Queue* pq);
int QueueSize(Queue* pq);
这就是队列我们要实现的所有接口。关于这个size的具体作用在接口的实现上会讲到。
2.2.1 初始化队列
初始化队列很简单，将head和tail指针置为空即可，size初始为0。
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = pq->tail = NULL;
pq->size = 0;
}
有了初始化，一般来说我们会再写销毁，那么队列这里我们将销毁放到后面在写，因为队列的销毁会有一些要注意的点在我们写完了其他接口，对队列的结构有了更深的理解后，才会有更好的认识。
2.2.2 入队列
入队列是我们要第一个学习的接口，要写好入队列这个接口，首先要我们对队列的结构有一定的理解。
我们的队列是用链表写的，当队列中没有数据时，队列为空，链表也为空，而我们插入第一个数据时，就需要注意，链表一个结点存储我们的数据，让队列的头和尾指向这个结点。
之后的插入数据，就是让我们的链表链接起来，用tail指向最后一个结点。
这就是我们的入队列。其实入队列的逻辑很简单，我们理解这一块最主要的就是要将队列和链表分离开来，链表是我们的存储结构，而队列是我们用来管理链表的。无论你是用什么方式进行存储，我们的管理方式都不变，用数组存储是这样，链表也同样如此。
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
//申请结点存储数据
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc fail");
exit(-1);
}
newnode->next = NULL;
newnode->data = x;
//判断是不是第一个数据
if (pq->tail == NULL)
{
//让head和tail都指向第一个结点
pq->tail = pq->head = newnode;
}
else
{
//让结点链接起来
pq->tail->next = newnode;
//让tail指向队尾
pq->tail = newnode;
}
pq->size++; //用来统计队列中的元素个数
}
2.2.3 出队列
队尾入数据，队头出数据，出队列就是类似于链表的头删。这里要注意当队列只剩一个数据的时候，也就是链表只有一个结点，需要另外的处理。
void QueuePop(Queue* pq)
{
assert(pq);
//这里出队列的时候要注意判空，队列为空不能删除
assert(!QueueEmpty(pq));
//我们用size来统计队列中的元素个数，当size==1，就只有一个元素。
if (pq->size == 1)
{
free(pq->head);
pq->head = pq->tail = NULL;
}
else
{
//链表头删的逻辑，head指向队头（也就是链表的头部）。
QNode* cur = pq->head;
pq->head = pq->head->next;
free(cur);
}
pq->size--;
}
2.2.4 检测链表是否为空
这里就体现了我们额外定义一个size变量的好处，当size为0时，队列就为空。
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->size == 0;
}
2.2.5 显示队列头元素
head就指向我们的队头结点。
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->head->data;
}
2.2.6 显示队列尾元素
tail就指向我们的队尾结点
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->tail->data;
}
2.2.7 获取队列中的元素个数
size就是队列中的元素个数
int QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}
2.2.8 销毁队列
现在我们再来看看队列的销毁，其实队列的销毁就像链表的销毁一样，只是这里我们有了队头和队尾两个指针管理。队列销毁的是链表中的结点
void QueueDestroy(Queue* pq)
{
assert(pq);
QNode* cur = pq->head;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = cur->next;
}
pq->head = pq->tail = NULL;
}
以上就是队列的实现，队列的结构相比栈更复杂是因为我们用了链表来实现，但本质上无论用顺序表还是链表实现都是一样的，只要我们将管理结构和存储结构分离开来，就很好理解。
总结
关于栈和队列的概念和结构以及实现部分我们就学习到这里，要想对栈和队列有更深的认识，还需要我们来做一些相关的题目，这里我给大家推荐几道相关的题，大家可以下来自己做一做。
以上就是我们所有的内容，希望对大家有所帮助，谢谢！