朋友们、伙计们，我们又见面了，本期来给大家解读一下栈和队列方面的相关知识点，如果看完之后对你有一定的启发，那么请留下你的三连，祝大家心想事成！

C 语言专栏：C语言：从入门到精通

数据结构专栏：数据结构

个人主页： stackY、

前言：

1.栈

1.1栈的概念及结构

1.2栈的实现

1.2.1栈的创建

1.2.2栈的初始化

1.2.3入栈

1.2.4检测栈是否为空

1.2.5出栈

1.2.6获取栈顶元素

1.2.7获取栈中有效元素的个数

1.2.8销毁栈

1.2.9访问栈

1.3栈的完整代码

2.队列

2.1队列的概念及结构

2.2队列的实现

2.2.1队列的创建

2.2.2队列的初始化

2.2.3队尾入队列

2.2.4检测队列是否为空

2.2.5队头出队列

2.2.6获取队头数据

2.2.7获取队尾数据

2.2.8获取队列有效元素个数

2.2.9销毁队列

2.2.10访问队列

2.3队列完整代码

前言：

在之前的顺序表中我们提到过线性表：线性表（linear list）是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串...

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

顺序表的实现我们使用的是数组，链表的实现我们使用的是链式结构，那么关于栈和队列又该怎么样实现呢？话不多说，直接开始：

1.栈

1.1栈的概念及结构

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。

进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。

栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。

出栈：栈的删除操作叫做出栈。出数据也在栈顶。

1.2栈的实现

我们以STL为模板来实现栈，因此栈的功能也就分为：初始化、销毁、入栈、出栈、获取栈顶元素、获取栈中有效元素个数、检测栈是否为空。

栈的实现还是和之前的数据结构的实现一样分模块来写，当然也是可以在一个源文件中完成的，当然小编还是推荐大家分模块来写，先创建两个源文件：Test.c和Stack.c，再创建一个头文件：Stack.h，这里的文件命名不做要求，表示的有意义就行。同样的我们在Test.c中实现基本逻辑，在Stack.c中实现栈的细节，在Stack.h中进行函数声明和头文件包含等，话不多说，我们直接开始：

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为我们的入栈和出栈都是在尾部进行操作，如果使用链表的话，在进行入栈的时候还得找尾，在出栈的时候还得找尾的前一个，代价有点大，所以选择数组，因为数组在尾上插入数据的代价比较小。

1.2.1栈的创建

栈的创建有两种方式：

1.静态栈

头文件：Stack.h
//静态栈
typedef int STDataType;
#define N 10
typedef struct Stack
{
	STDataType _a[N];
	int _top; // 栈顶
}Stack;
2.动态栈

头文件：Stack.h
//动态栈
typedef int STDataType;

typedef struct Stack
{
	STDataType* a;
	int top;        //栈顶
	int capacity;  //栈的容量
}Stack;
由于静态栈不常用也不实用，所以在这里我们就来使用动态栈：

1.2.2栈的初始化

在创建栈的时候栈中有一个指针，栈顶，和栈的容量，因此我们要将这些数据初始化一下，先将指针置为NULL，再将容量置为0，这里的栈顶初始化就有两种说法了：

1.如果将top置为0的话，那么在插入数据的时候是先插入然后top++，在插入完之后top始终指向的是最后一个数据的下一个位置。

2.如果将top置为-1，那么就要先top++然后再插入数据，再插入完之后top指向的是最后一个数据的位置。

两种方式都可行，但是将top置为0在后面的操作中会比较方便。

头文件：Stack.h
//对栈的初始化
void StackInit(Stack* pst);
源文件：Stack.c
//对栈的初始化
void StackInit(Stack* pst)
{
	assert(pst);
	pst->a = NULL;
	//top为-1时，插入一个数据之后top指向的是刚刚插入数据的位置
	//pst->top = -1     
	//top为0时，插入一个数据之后top指向的是刚刚插入数据后面的位置
	pst->top = 0;
	pst->capacity = 0;
}
注意：这里传参为什么不用二级指针，因为我们改变的是结构体成员，使用结构体指针就完全OK。

1.2.3入栈

入栈也叫做插入数据，先要检测容量，如果top等于容量，那么就需要扩容，然后将数据插入到top的位置，然后top++：

头文件：Stack.h

//入栈
void StackPush(Stack* pst, STDataType x);

源文件：Stack.c

//入栈
void StackPush(Stack* pst, STDataType x)
{
	assert(pst);
	//检测容量
	if (pst->top == pst->capacity)
	{
		int NewCapacity = pst->capacity == 0 ? 4 : 2 * pst->capacity;
		//当pst->a为NULL时执行的功能是和malloc一样
		STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * NewCapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		pst->a = tmp;
		pst->capacity = NewCapacity;
	}
	//入栈
	pst->a[pst->top] = x;
	pst->top++;
}

1.2.4检测栈是否为空

检测栈是否为空：就是检测栈顶是否为0，如果栈顶top为0，则为空，栈为空返回true，不为空返回false：

头文件：Stack.h
//检测栈是否为空
bool StackEmpty(Stack* pst);
源文件：Stack.c
//检测栈是否为空
bool StackEmpty(Stack* pst)
{
	assert(pst);
	/*if (pst->top == 0)
	{
		return true;
	}
	else
	{
		return false;
	}*/
	return pst->top == 0;
}

1.2.5出栈

出栈就比较简单了，直接将top--，但是这里还存在一个问题，如果栈为空，那么就不能再出栈，因此我们需要对栈进行判空：

头文件：Stack.h
//出栈
void StackPop(Stack* pst);
源文件：Stack.c
//出栈
void StackPop(Stack* pst)
{
	assert(pst);
	//判断栈是否为空
	assert(!StackEmpty(pst));
	//出栈
	pst->top--;
}

1.2.6获取栈顶元素

获取栈顶元素就是将数组中下标为top-1的元素返回，并且在返回前先要判断栈中是否有无数据：

头文件：Stack.h
//获取栈顶元素
STDataType StackTop(Stack* pst);
源文件：Stack.c
//获取栈顶元素
STDataType StackTop(Stack* pst)
{
	assert(pst);
	assert(!StackEmpty(pst));
	//top指向的是栈顶的下一个位置的元素
	return pst->a[pst->top-1];
}

1.2.7获取栈中有效元素的个数

栈中有效元素的个数就是top，只需要将top直接返回即可：

头文件：Stack.h
//获取栈中的有效元素的个数
int StackSize(Stack* pst);
源文件：Stack.c
//获取栈中的有效元素的个数
int StackSize(Stack* pst)
{
	assert(pst);

	return pst->top;
}

1.2.8销毁栈

由于我们创建的是动态的栈，因此在程序结束之后我们需要将动态开辟的空间释放掉，然后将top和capacity都置为0：
头文件：Stack.h
//销毁栈
void StackDestroy(Stack* pst);
源文件：Stack.c
//销毁栈
void StackDestroy(Stack* pst)
{
	assert(pst);

	//释放
	free(pst->a);
	pst->a = NULL;
	//重置为0
	pst->top = pst->capacity = 0;
}

1.2.9访问栈

上面的这些接口都比较简单，那么在实现上面的接口之后怎么访问栈呢？我们可以通过循环来进行访问，循环的判断条件就是栈不为空，然后打印栈顶的元素，然后再删除栈顶的元素，依次类推，就可以访问栈中的全部元素了：

源文件：Test.c
#include "Stack.h"

void TestStack()
{
	Stack st;
	//初始化
	StackInit(&st);

	//入栈
	StackPush(&st, 1);
	StackPush(&st, 2);
	StackPush(&st, 3);
	StackPush(&st, 4);

	//获取栈中的有效元素的个数
	printf("Size:%d\n", StackSize(&st));

	//访问栈的元素
	while (!StackEmpty(&st))
	{
		//打印栈顶的数据
		printf("%d ", StackTop(&st));
		//出栈
		StackPop(&st);
	}

	//销毁栈
	StackDestroy(&st);
}

int main()
{
	TestStack();
	return 0;
}

1.3栈的完整代码

头文件：Stack.h

#pragma once

//   栈的实现

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

//动态栈
typedef int STDataType;

typedef struct Stack
{
	STDataType* a;
	int top;        //栈顶
	int capacity;  //栈的容量
}Stack;


//对栈的初始化
void StackInit(Stack* pst);

//入栈
void StackPush(Stack* pst, STDataType x);

//出栈
void StackPop(Stack* pst);

//获取栈顶元素
STDataType StackTop(Stack* pst);

//获取栈中的有效元素的个数
int StackSize(Stack* pst);

//检测栈是否为空
bool StackEmpty(Stack* pst);

//销毁栈
void StackDestroy(Stack* pst);

源文件：Stack.c

#define _CRT_SECURE_NO_WARNINGS 1

#include "Stack.h"

//对栈的初始化
void StackInit(Stack* pst)
{
	assert(pst);
	pst->a = NULL;
	//top为-1时，插入一个数据之后top指向的是刚刚插入数据的位置
	//pst->top = -1     
	//top为0时，插入一个数据之后top指向的是刚刚插入数据后面的位置
	pst->top = 0;
	pst->capacity = 0;
}

//入栈
void StackPush(Stack* pst, STDataType x)
{
	assert(pst);
	//检测容量
	if (pst->top == pst->capacity)
	{
		int NewCapacity = pst->capacity == 0 ? 4 : 2 * pst->capacity;
		//当pst->a为NULL时执行的功能是和malloc一样
		STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * NewCapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		pst->a = tmp;
		pst->capacity = NewCapacity;
	}
	//入栈
	pst->a[pst->top] = x;
	pst->top++;
}

//出栈
void StackPop(Stack* pst)
{
	assert(pst);
	//判断栈是否为空
	assert(!StackEmpty(pst));
	//出栈
	pst->top--;
}

//获取栈顶元素
STDataType StackTop(Stack* pst)
{
	assert(pst);
	assert(!StackEmpty(pst));
	//top指向的是栈顶的下一个位置的元素
	return pst->a[pst->top-1];
}

//获取栈中的有效元素的个数
int StackSize(Stack* pst)
{
	assert(pst);

	return pst->top;
}

//检测栈是否为空
bool StackEmpty(Stack* pst)
{
	assert(pst);
	/*if (pst->top == 0)
	{
		return true;
	}
	else
	{
		return false;
	}*/
	return pst->top == 0;
}

//销毁栈
void StackDestroy(Stack* pst)
{
	assert(pst);

	//释放
	free(pst->a);
	pst->a = NULL;
	//重置为0
	pst->top = pst->capacity = 0;
}

源文件：Test.c

#define _CRT_SECURE_NO_WARNINGS 1

#include "Stack.h"

void TestStack()
{
	Stack st;
	//初始化
	StackInit(&st);

	//入栈
	StackPush(&st, 1);
	StackPush(&st, 2);
	StackPush(&st, 3);
	StackPush(&st, 4);

	//获取栈中的有效元素的个数
	printf("Size:%d\n", StackSize(&st));

	//访问栈的元素
	while (!StackEmpty(&st))
	{
		//打印栈顶的数据
		printf("%d ", StackTop(&st));
		//出栈
		StackPop(&st);
	}

	//销毁栈
	StackDestroy(&st);
}


int main()
{
	TestStack();
	return 0;
}

2.队列

2.1队列的概念及结构

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

入队列：进行插入操作的一端称为队尾

出队列：进行删除操作的一端称为队头

2.2队列的实现

我们以STL为模板来实现队列，因此队列的功能也就分为：初始化、销毁、入列、出列、获取队头元素、获取队尾元素，获取队列中有效元素个数、检测队列是否为空。

队列的实现还是和之前的数据结构的实现一样分模块来写，当然也是可以在一个源文件中完成的，当然小编还是推荐大家分模块来写，先创建两个源文件：Test.c和Queue.c，再创建一个头文件：Queue.h，这里的文件命名不做要求，表示的有意义就行。同样的我们在Test.c中实现基本逻辑，在Queue.c中实现队列的细节，在Queue.h中进行函数声明和头文件包含等，话不多说，我们直接开始：

队列也可以使用数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，每一次出一个数据都要将后面的数据挪动，代价大，效率低，使用链表可以直接今天头删，和尾插。

2.2.1队列的创建

队列的实现使用链表比较合适，因此我们需要先创建一个单链表表示链式结构，由于单链表尾插每次都需要找尾，效率比较低，所以我们可以再创建一个队列结构，这个队列结构中包含这个队列的头、尾、有效元素个数：

头文件：Queue.h
//链式结构：表示队列
typedef int QDataType;
typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;
}QNode;

//队列的结构
typedef struct Queue
{
	//头指针
	QNode* phead;
	//尾指针
	QNode* ptail;
	//队列中有效元素个数
	int size;
}Queue;

2.2.2队列的初始化

初始化队列比较简单，将队列中的头、尾指针置为NULL，再将有效元素个数置为0：

头文件：Queue.h
//初始化队列
void QueueInit(Queue* pq);
源文件：Queue.c
//初始化队列
void QueueInit(Queue* pq)
{
	assert(pq);

	pq->phead = NULL;
	pq->ptail= NULL;
	pq->size = 0;
}

2.2.3队尾入队列

从队尾插入队列就相当于尾插，先创建一个新结点，表示要插入的结点，这时就要区分第一次插入和后面几次插入，第一次插入时要注意空指针的问题，队列为空的条件是头指针和尾指针都为空，后面的插入直接链接到尾，然后更新尾，然后将有效元素个数加一：

头文件：Queue.h
//队尾入队列
void QueuePush(Queue* pq, QDataType x);
源文件：Queue.c
//队尾入队列
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	
	//创建新的结点
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	newnode->next = NULL;
	newnode->data = x;

	//第一次尾插
	if (pq->ptail == NULL)
	{
		assert(pq->phead == NULL);

		pq->phead = pq->ptail = newnode;
	}
	else
	{
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}
	//有效元素++
	pq->size++;
}

2.2.4检测队列是否为空

在出队列时先要进行对队列的检查，检测队列是否为空，若为空就不能再进行删除，实现这个接口有两种方式：

1.头指针和尾指针都指向空。

2.队列中有效元素个数为空。

根据个人习惯来进行使用

头文件：Queue.h
//检测队列是否为空
bool QueueEmpty(Queue* pq);
源文件：Queue.c
//检测队列是否为空
bool QueueEmpty(Queue* pq)
{
	assert(pq);

	//1.判断头、尾指针
	/*
	return pq->phead == NULL
		&& pq->ptail == NULL;
	*/

	//2.判断有效元素个数
	return pq->size == 0;
}

2.2.5队头出队列

队头出队列就表示头删，因此先要判断队列中是否有数据，然后进行头删，头删的话需要保存头的后一个结点，然后将头结点释放，再将新的头指向保存的结点，然后再将有效元素个数减一，这样子就完成了头删，但是如果我们仔细画图的话就会发现，这样删除的话并不完美，当只有一个结点的时候，进行头删的话这里的尾指针就变成了野指针，所以还是得区分两种情况，只有一个结点和有多个结点，如果只有一个结点，那么直接进行释放，然后将头尾结点都置为NULL，有多个结点的话可以直接释放：

头文件：Queue.h
//对头出队列
void QueuePop(Queue* pq);
源文件：Queue.c
//队头出队列
void QueuePop(Queue* pq)
{
	assert(pq);
	//判空
	assert(!QueueEmpty(pq));

	//一个结点
	if (pq->phead->next == NULL)
	{
		//直接释放
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	//多个结点
	else
	{
		//记录头的下一个
		QNode* Next = pq->phead->next;
		//释放
		free(pq->phead);
		//更新头结点
		pq->phead = Next;
	}
	
	pq->size--;
}

2.2.6获取队头数据

队头数据就是头指针的结点中的data，如果队列是空队列则不能获取，所以先得判断一下：

头文件：Queue.h
//获取队头的元素
QDataType QueueFront(Queue* pq);
源文件：Queue.c
//获取队头的元素
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	//先判空
	assert(!QueueEmpty(pq));

	return pq->phead->data;
}

2.2.7获取队尾数据

队尾数据就是尾指针的结点中的data，如果队列是空队列则不能获取，所以先得判断一下：

头文件：Queue.h
//获取队尾的元素
QDataType QueueBack(Queue* pq);
源文件：Queue.c
//获取队尾的元素
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	//先判空
	assert(!QueueEmpty(pq));

	return pq->ptail->data;
}

2.2.8获取队列有效元素个数

有效元素个数就是size，可直接进行返回：

头文件：Queue.h
//获取队列有效元素的个数
int QueueSize(Queue* pq);
源文件：Queue.c
//获取队列有效元素的个数
int QueueSize(Queue* pq)
{
	assert(pq);

	return pq->size;
}

2.2.9销毁队列

由于链式结构的每一个结点都是动态开辟的，因此在程序结束之后我们需要将这些结点一一释放掉，这里要注意，即便是空队列也要进行释放，空队列只表示结点中没有数据，但不能表示没有结点，所以空队列也是要进行释放，销毁队列也有两种方式，大家根据习惯来进行使用：

1.保存当前结点，然后释放。

2.保存下一个结点，然后释放当前结点。

头文件：Queue.h
//销毁队列
void QueueDestroy(Queue* pq);
源文件：Queue.c
//销毁队列
void QueueDestroy(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->phead;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}

2.2.10访问队列

当我们完成上述接口时，可以来测试一下，顺便对队列进行访问，访问的时候依旧是队列不为空我们就可以访问，每一次访问的是队头的元素，然后将队头的元素出列，再访问下一个元素，依次类推：

源文件：Test.c
void TestQueue()
{
	Queue q;
	
	//初始化
	QueueInit(&q);

	//入列
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);

	//有效元素个数
	printf("Size:%d\n", QueueSize(&q));

	//访问队头元素
	printf("Front:%d\n", QueueFront(&q));

	//访问队尾元素
	printf("Back:%d\n", QueueBack(&q));

	//访问队列
	while (!QueueEmpty(&q))
	{
		printf("%d ", QueueFront(&q));
		QueuePop(&q);
	}

	//销毁
	QueueDestroy(&q);
}


int main()
{
	TestQueue();
	return 0;
}

2.3队列完整代码

头文件：Queue.h

#pragma once

//       队列

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

//链式结构：表示队列
typedef int QDataType;
typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;
}QNode;

//队列的结构
typedef struct Queue
{
	//头指针
	QNode* phead;
	//尾指针
	QNode* ptail;
	//队列中有效元素个数
	int size;
}Queue;


//初始化队列
void QueueInit(Queue* pq);

//销毁队列
void QueueDestroy(Queue* pq);

//队尾入队列
void QueuePush(Queue* pq, QDataType x);

//检测队列是否为空
bool QueueEmpty(Queue* pq);

//对头出队列
void QueuePop(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->phead = NULL;
	pq->ptail= NULL;
	pq->size = 0;
}

//销毁队列
void QueueDestroy(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->phead;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}

//队尾入队列
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	
	//创建新的结点
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	newnode->next = NULL;
	newnode->data = x;

	//第一次尾插
	if (pq->ptail == NULL)
	{
		assert(pq->phead == NULL);

		pq->phead = pq->ptail = newnode;
	}
	else
	{
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}
	//有效元素++
	pq->size++;
}

//检测队列是否为空
bool QueueEmpty(Queue* pq)
{
	assert(pq);

	//1.判断头、尾指针
	/*
	return pq->phead == NULL
		&& pq->ptail == NULL;
	*/

	//2.判断有效元素个数
	return pq->size == 0;
}

//队头出队列
void QueuePop(Queue* pq)
{
	assert(pq);
	//判空
	assert(!QueueEmpty(pq));

	//一个结点
	if (pq->phead->next == NULL)
	{
		//直接释放
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	//多个结点
	else
	{
		//记录头的下一个
		QNode* Next = pq->phead->next;
		//释放
		free(pq->phead);
		//更新头结点
		pq->phead = Next;
	}
	
	pq->size--;
}

//获取队头的元素
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	//先判空
	assert(!QueueEmpty(pq));

	return pq->phead->data;
}

//获取队尾的元素
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	//先判空
	assert(!QueueEmpty(pq));

	return pq->ptail->data;
}

//获取队列有效元素的个数
int QueueSize(Queue* pq)
{
	assert(pq);

	return pq->size;
}

源文件：Test.c

#define _CRT_SECURE_NO_WARNINGS 1

#include "Queue.h"

void TestQueue()
{
	Queue q;
	
	//初始化
	QueueInit(&q);

	//入列
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);

	//有效元素个数
	printf("Size:%d\n", QueueSize(&q));

	//访问队头元素
	printf("Front:%d\n", QueueFront(&q));

	//访问队尾元素
	printf("Back:%d\n", QueueBack(&q));

	//访问队列
	while (!QueueEmpty(&q))
	{
		printf("%d ", QueueFront(&q));
		QueuePop(&q);
	}

	//销毁
	QueueDestroy(&q);
}


int main()
{
	TestQueue();
	return 0;
}