开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 《数据结构》（五）线性表之栈和队列的实现及万字详解 -> 正文阅读

[数据结构与算法]《数据结构》（五）线性表之栈和队列的实现及万字详解

今天的重点是栈和队列，以及接口实现和详细解释。字数很多，很详细，大家收藏起来，慢慢回味😉😉😉

栈和队列的介绍

栈和队列是两种重要的线性结构，从数据结构角度来看，栈和队列也是线性表，其特殊性在于栈和队列的基本操作是线性表操作的子集，这一篇我们将介绍栈和队列的定义，表示方法和实现。

栈

栈的定义

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。栈的插入操作被称为压栈/进栈/入栈，栈的删除操作被称为出栈。进行数据插入和删除操作的一端称为栈顶（top），另一端称为栈底。栈中元素按 a1，a2， …, an. 的次序进栈，出栈的第一个元素应为栈顶元素，也就是后进先出，就像汉诺塔一样（两石柱）。这里的top都是指向栈顶元素的下一位，一会大家就知道了。😝😝😝看图理解一下就上高速了。

在这里插入图片描述

栈的实现

栈的结构选择

🎤由之前的博客中介绍的有顺序表和链表，到底如何选择结构也是一个问题，我们理解栈的定义后讨论一下两种不同结构：
1.链表：双链表的话也是一个不错的选择，但是单链表的话尾插和尾删就是O(N)；
2.顺序表：由栈的定义可以清晰了解，栈只涉及尾插和尾删，用数组的话也是一个不错的选择。
综上所述：栈的实现，结构是多样的，各有千秋，喜欢那个就用那个吧，这篇我们就是用顺序表的形式（后面就会体会到数组的好处）。

栈的基本接口

🎤栈的基本操作除了在栈顶进行插人或删除外，还有栈的初始化、判空及取栈顶元素等

//栈需要的接口
// 初始化栈
void StackInit(ST* ps);
// 销毁栈
void StackDestory(ST* ps);
//入栈
void StackPush(ST* ps,STDataType x);
//出栈
void StackPop(ST* ps);
//取栈顶的数据
STDataType StackTop(ST* ps);
//栈的数据个数
int StackSize(ST* ps);
//检测栈是否为空
bool StackEmpty(ST* ps);

栈结构（顺序结构）的定义

🎤一般来说结构定义的时候，设置空栈时不应该限定栈的最大容量，我们先为栈设置一个基础容量，在后面实际应用的时候，如果空间不够用，我们可以增容，这就是我们这里用到的支持动态增长的栈。

typedef int STDataType;
typedef struct Stack
{
	STDataType* a;//是一个指针指向这个数组
	int top;//栈顶
	int capacity;//容量
}ST;

🎤这里的top指的是栈顶，capacity指的是数组当前可以使用的最大容量；这个a是一个结构体指针，指向的是数组。

栈的初始化

🎤初始化这里，也是很容易理解的，重点是这里的top，大家都知道数组中下标是从0开始的，top一般指在栈顶的下一位，如果top给0，指向的就是栈顶的下一位，如果给-1，那么指向的就是栈顶。

void StackInit(ST* ps)
{
	assert(ps);
	ps -> a = (STDataType*)malloc(sizeof(STDataType) * 4);
	if (ps->a == NULL)//判空，如果我们malloc的空间是空的话，就直接报错
	{
		printf("malloc fail\n");
		exit(-1);
	}
	ps->capacity = 4;//是我们初始给数组的最大容量
	ps->top = 0;
}

栈的销毁

🎤我们用的是数组结构，直接free掉数组，然后让a指向空，在将top和capacity赋为0就ok了。

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

入栈

🎤入栈，就像是顺序表的尾插一样，首先判断数组是不是满了，如果满了我们就进行二倍的扩容，否则我们将待插入数据放到数组中top指向的位置，再让top++，让它指向待插入元素的下一位。

void StackPush(ST* ps, STDataType x)
{
	assert(ps);

	//满了怎么办？---增容
	if (ps->top == ps->capacity)
	{
		STDataType* tmp = (STDataType*)realloc(ps->a, ps->capacity * 2 * sizeof(STDataType));
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		else
		{
			ps->a = tmp;
			ps->capacity *= 2;//乘等2才会变成它的二倍
		}
	}
	
	ps->a[ps->top] = x;
	ps->top++;
}

出栈

🎤 出栈时要注意是栈顶出，还要考虑栈中是否为空，如果为空，肯定不能出栈。数据从栈顶出，让top前一位置为0肯定是不行的，我们让top–，直接覆盖即可。

void StackPop(ST* ps)
{
	assert(ps);
	//栈空了，调用pop，直接中止程序并报错
	assert(ps->top > 0);

	ps->top--;
}

取栈顶元素

🎤上面介绍过，我们top指向的是栈顶元素的下一位，取栈顶元素的时候，取它的前一位，就是栈顶元素。

STDataType StackTop(ST* ps)
{
	assert(ps);
	
	//栈空了，调用top，直接中止程序并报错
	assert(ps->top > 0);

	return ps->a[ps->top - 1];
}

栈中数据的个数

🎤因为使用的是数组，而且还有top，我们肯定不会去遍历，top所在数组的下标就是栈的长度，我们直接return top即可。

int StackSize(ST* ps)
{
	assert(ps);

	return ps->top;//top所在数组的下标就是栈的长度
}

判空

🎤这个也简单，但是需要理解，如果为空返回非零结果，如果不为空返回0 。

bool StackEmpty(ST* ps)
{
	assert(ps);
	
	return ps->top == 0;//如果为空返回非零结果，如果不为空返回0
}

队列

队列的定义

和栈相反，队列是一种先进先出的线性表，它只允许在队的一端进行插入，在队的另一端进行删除。这就像我们日常派对做核酸一样，最早排队的做的先出结果。在队列中允许插入的一端叫做队尾，允许删除的一端则称为队头。😲😲😲

在这里插入图片描述

队列的实现

队列结构的选择

🎤队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。我们本篇就使用的是链表的结构。

队列的基本接口

🎤对于队列来说，能实现的接口几乎是和栈是一样的，但是需要注意的是入队是在队列后面入，出队是在队列头部出。

//初始化
void QueueInit(Queue* pq);
//销毁
void QueueDestory(Queue* pq);
//入队---队尾入
void QueuePush(Queue* pq, QDataType x);
//出队---队头出
void QueuePop(Queue* pq);

//取队头数据
QDataType QueueFront(Queue* pq);
//取队尾数据
QDataType QueueBack(Queue* pq);
//数据个数
int QueueSize(Queue* pq);
//判空
bool QueueEmpty(Queue* pq);

队列结构（链式结构）的定义

🎤既然用的是单链表的结构，那么就要有一个数据域（data）和指针域（next）（指针域在以往博客，单链表中有详细说明）；而且还要有两个指针，一个指向队头（head），一个指向队尾（tail）。

typedef int QDataType;

typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;

}QNode;

typedef struct Queue
{
	QNode* head;//队头
	QNode* tail;//队尾
}Queue;

队列的初始化

🎤先让头指针和尾指针都指向空。

void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;
}

队列的销毁

🎤因为队列是单链表的形式，所以就只能用遍历释放的方式，用两个指针分别是cur和next，用cur来释放，让next来指向cur的下一个结点，然后将next赋给cur，当cur指向空的时候截止，最后将头指针和尾指针置空

void QueueDestory(Queue* pq)
{
	assert(pq);

	QNode* cur = pq->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
}

入队（队尾入）

🎤入队，就像是单链表的尾插，有一个问题需要注意，要注意队列是否为空
1.申请新结点newnode，并判断是否malloc失败；
2.把新结点的数据域赋值为x，让其指针域指向NULL；
3.判断队列是否为空，如果为空，将头指针和尾指针指向newnode，否则让tail的next指向newnode，并让tail走到newnode上成为新的尾。

void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);

	QNode* newnode = (QNode*)malloc(sizeof(QNode));//新结点的创建
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		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;//链接之后让tail成为新的尾
	}
}

出队（队头出）

🎤==出队类似于单链表的头删，需要注意的是，队列的不能为空，需要判断链表只剩一个结点还是多个结点。==当队列只剩下一个结点时，要防止tail成为野指针，很简单，释放队列中第一个结点后，让head向后走一个，大家看一下就懂了。

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->tail);//既然是出队列，那么就要判断队列是不为空的，空了还出个毛线

	if (pq->head->next == NULL)//当队列中只剩下一个结点的时候，防止tail成为野指针
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else//多个结点
	{
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
}

取队头元素

🎤取元素就更简单了，返回头指针指向结点的数据域的值就行了。

QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->head);//先判断一下队头数据是不是空，如果为空就不能调用

	return pq->head->data;//很简单，直接返回队头的数据即可
}

取队尾数据

🎤和取队头数据差不多

QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->head);//同上

	return pq->tail->data;//直接返回队尾的数据即可
}

队列中数据个数

🎤队列中数据个数，没有别的方法只能遍历链表了，定义一个指针cur用来从队列头走到空截止，每走一位，size++

int QueueSize(Queue* pq)
{
	//这次就需要用遍历链表，也是非常简单的
	assert(pq);

	int size = 0;
	QNode* cur = pq->head;
	while (cur)
	{
		++size;
		cur = cur->next;
	}
	return size;
}

判空

🎤 如果为空返回非零结果，如果非空返回0

bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL;//如果等于空就是真，不等于空就是假
}

代码参考

到这里，我相信大家对湛河队列已经拿捏了🎉🎉🎉，有错误大家可以指出哦，有疑问也可以问我，大家共同进步，后续会持续更新《数据结构》的相关内容，大家喜欢的话可以关注一下，😚😚😚
下面是项目代码，大家参考一下。

栈

Stack.c

#include"Stack.h"

void StackInit(ST* ps)
{
	assert(ps);
	ps -> a = (STDataType*)malloc(sizeof(STDataType) * 4);
	if (ps->a == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	ps->capacity = 4;
	ps->top = 0;
}

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

void StackPush(ST* ps, STDataType x)
{
	assert(ps);

	//满了怎么办？---增容
	if (ps->top == ps->capacity)
	{
		STDataType* tmp = (STDataType*)realloc(ps->a, ps->capacity * 2 * sizeof(STDataType));
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		else
		{
			ps->a = tmp;
			ps->capacity *= 2;//乘等2才会变成它的二倍
		}
	}
	
	ps->a[ps->top] = x;
	ps->top++;
}

void StackPop(ST* ps)
{
	assert(ps);
	//栈空了，调用pop，直接中止程序并报错
	assert(ps->top > 0);

	ps->top--;
}

STDataType StackTop(ST* ps)
{
	assert(ps);
	//栈空了，调用top，直接中止程序并报错
	assert(ps->top > 0);

	return ps->a[ps->top - 1];
}

int StackSize(ST* ps)
{
	assert(ps);

	return ps->top;//top所在数组的下标就是栈的长度
}

bool StackEmpty(ST* ps)
{
	assert(ps);
	
	return ps->top == 0;//如果为空返回非零结果，如果不为空返回0
}

Stack.h

typedef struct Stack
{
	STDataType* a;//是一个指针指向这个数组
	int top;//栈顶
	int capacity;//容量
}ST;

//栈需要的接口
// 初始化栈
void StackInit(ST* ps);
// 销毁栈
void StackDestory(ST* ps);
//入栈
void StackPush(ST* ps,STDataType x);
//出栈
void StackPop(ST* ps);
//取栈顶的数据
STDataType StackTop(ST* ps);
//栈的数据个数
int StackSize(ST* ps);
//检测栈是否为空，如果为空返回非零结果，如果非空返回0 
bool StackEmpty(ST* ps);//用布尔来判断真假更好用，但是注意引用头文件

队列

Queue.h

#pragma once

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

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 QueueDestory(Queue* pq);
//入队---队尾入
void QueuePush(Queue* pq, QDataType x);
//出队---队头出
void QueuePop(Queue* pq);

//取队头数据
QDataType QueueFront(Queue* pq);
//取队尾数据
QDataType QueueBack(Queue* pq);
//数据个数
int QueueSize(Queue* pq);
//判空
bool QueueEmpty(Queue* pq);

Queue.c

#include"Queue.h"

void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;
}

void QueueDestory(Queue* pq)
{
	assert(pq);

	QNode* cur = pq->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
}

//入队---队尾入
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);

	QNode* newnode = (QNode*)malloc(sizeof(QNode));//新结点的创建
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		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;//链接之后让tail成为新的尾
	}
}
//出队---队头出
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->tail);//既然是出队列，那么就要判断队列是不为空的，空了还出个毛线

	if (pq->head->next == NULL)//当队列中只剩下一个结点的时候，防止tail成为野指针
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else//多个结点
	{
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
}

//取队头数据
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->head);//先判断一下队头数据是不是空，如果为空就不能调用

	return pq->head->data;//很简单，直接返回队头的数据即可
}
//取队尾数据
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->head);//同上

	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;
}
//判空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL;//如果等于空就是真，不等于空就是假
}

Test.c

#include"Stack.h"
#include"Queue.h"
void TestStack()
{
	ST st;
	StackInit(&st);

	StackPush(&st, 1);
	StackPush(&st, 2);
	StackPush(&st, 3);
	StackPush(&st, 4);
	StackPush(&st, 5);

	printf("%d ", StackTop(&st));
	StackPop(&st);

	printf("%d ", StackTop(&st));
	StackPop(&st);

	printf("%d ", StackTop(&st));
	StackPop(&st);

	printf("%d ", StackTop(&st));
	StackPop(&st);

	printf("%d ", StackTop(&st));
	printf("\n");

	StackDestory(&st);
}

void TestQueue()
{
	Queue q;
	QueueInit(&q);

	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);
	while (!QueueEmpty(&q))
	{
		printf("%d ", QueueFront(&q));
		QueuePop(&q);
	}
	printf("\n");

	QueueDestory(&q);

}
int main()
{
	printf("栈：Last In First Out\n");
	TestStack();

	printf("队列：First In First Out\n");
	TestQueue();
	return 0;
}