• 栈和队列的那些“恩怨情仇”，被我抓个正着

    🌈欢迎来到数据结构专栏~栈和队列

    • (꒪ꇴ꒪(꒪ꇴ꒪ )🐣,我是Scort
    • 🌍博客主页：张小姐的猫~江湖背景🌍
    • 快上车🚘，握好方向盘跟我有一起打天下嘞！
    • 送给你们一句罗翔老师的话🤔：
    • 🔥🔥
    • 🙏作者水平很有限，如果发现错误，可在评论区指正，感谢🙏
    • 🎉🎉欢迎持续关注！🎉🎉
      请添加图片描述

    请添加图片描述

    栈和队列的实现🔍

    请添加图片描述

    🌸栈

    🌼栈的概念及结构

    栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

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

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

    在这里插入图片描述

    🌸一.栈的的实现

    🛫准备工作

    为了简明扼要的分清楚栈和队列的作用，各部分代码分在以下三个不同的项中👇🏻

    • Queue.h ---------➡️函数功能的说明
    • Queue.c ---------➡️函数功能的实现
    • test.c ---------➡️调用函数功能

    我们用数组还是链表去实现栈呢？

    答案是都可以，但是用数组是更好的

    • 插入数据，基本上只有尾插尾删，而顺序表的尾插尾删效率很高
    • 唯一的缺点：扩容

    那么问题又来了：数组是定义静态的还是动态的呢？

    答案肯定是：动态 静态的还要定义数组的大小什么的，麻烦！

    //静态
#define N 10
typedef int STDataType;
typedef struct Stack
{
	STDataType a[N];
	int top;
}ST;
//动态
typedef int STDataType;
typedef struct Stack
{
	STDataType *a;
	int top;//栈顶
	int capacity;//容量
}ST;

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    🌼1.栈的初始化

    ➡️思路实现： 把栈的栈顶、容量等全部置为0，栈的指针置NULL

    这个简单，就不多说了上代码

    💫代码实现：

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    ❗特别注意：这里我们设置的top为0，所以top是栈顶元素的下一个

    在这里插入图片描述

    🌼2.入栈

    ➡️思路实现： 从栈尾插入一个元素，要注意判断空间是否足够

    ❗注意事项：

    1. 注意空间大小的问题：空间不够就扩容

    ✨动图解析：

    请添加图片描述

    💫代码实现：

    // 入栈 
void StackPush(ST* ps, STDataType data)
{
	assert(ps);
	if (ps->top == ps->capacity) 
	{
		//满了就扩容
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newCapacity;
	}
	ps->a[ps->top] = data;
	ps->top++;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20

    🌼3.出栈

    ➡️思路实现： 即删除栈顶元素，把top - -

    ✨动图解析：

    请添加图片描述

    💫代码实现：

    void StackPop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));//防止堆顶为空
	ps->top--;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    🌼4.获取栈顶元素

    ➡️思路实现： top是栈顶，那么top-1就是栈顶元素

    ❗注意事项：

    • 要注意判断栈是否为空
    • ps是指向栈结构的指针，结构里有数组a和栈顶的下标top，top不是已有栈顶元素的下标，而是待入栈的一个位置，所以栈顶的下标是top-1，数组名加下标获取数组元素

    💫代码实现：

    STDataType StackTop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));//防止栈顶为空
	 
	return ps->a[ps->top-1];
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    🌼5.判断栈是否为空

    ➡️思路实现： 判断top等不等于0，等于0就是就空，不等则相反

    ❗注意事项：

    1. 除了常规的if else判断，还有一种较为简单的方法，看下面

    💫代码实现：

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

    • 1
    • 2
    • 3
    • 4
    • 5

    🌼6.获取栈中元素个数

    ❗注意事项：

    1. top就是size，再数组里top是最后元素的下一个，也是元素的个数，从数组下标的角度看

    💫代码实现：

    int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;//top就是size个数，看下标
}

    • 1
    • 2
    • 3
    • 4
    • 5

    🌼7.销毁栈

    没啥说的直接上代码

    💫代码实现：

    // 销毁栈 
void StackDestroy(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    请添加图片描述

    🌸队列

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

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

    请添加图片描述

    🌸二.队列的实现

    🛫准备工作

    同理，为了简明扼要的分清楚队列的作用，各部分代码分在以下三个不同的项中：Queue.h
    Queue.c test.c

    这里部分比较帅的读者会问：我们还是用数组去实现队列？

    答案：链表，队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，出队列只能覆盖数据，效率会比较低。

    这里我们要使用带头双向链表吗？

    答案：小题大做了，带头双向循环链表的优势是在任意位置上插入删除，我们队列只在队尾插入、队头删除，所以可以定义head、tail两个指针

    // 链式结构：表示队列
typedef int QDataType;
typedef struct SListNode
{
	QDataType data;
	struct SListNode* next;
}QNode;
// 队列的结构
typedef struct Queue
{
	QNode* head;
	QNode* tail;
}Queue;

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13

    🌼1.初始化队列

    ➡️思路实现：把head、tail指针置为空

    💫代码实现：

    // 初始化队列
void QueueInit(Queue* q)
{
	assert(q);
	q->head = q->tail = NULL;//不带哨兵位，哨兵位意义不大
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    🌼2.队尾入队列

    ➡️思路实现： 从队尾插入数据，要注意极端情况

    ❗注意事项： （两种情况）

    1. 当队列为空时，一个数据都没有，这时候的head和tail都是指向NULL;
    2. 队列不为空的时候，入队列一个一个 的插入

    ✨动图解析：

    在这里插入图片描述

    情况2：
    请添加图片描述

    💫代码实现：

    // 队尾入队列
void QueuePush(Queue* q, QDataType data)
{
	assert(q);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		printf("malloc failed\n");
		exit(-1);
	}
	newnode->data = data;
	newnode->next = NULL;

	if (q->tail == NULL)
	{
		q->head = q->tail = newnode;
	}
	else
	{
		q->tail->next = newnode;
		q->tail = newnode;
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23

    🌼3.队头出队列

    ➡️思路实现： 从队头出数据，相当于头删，也有极端情况

    ❗注意事项：

    • 保存head的下一个next，释放head，然后next赋值给head
    • 极端情况：当只剩下一个节点了，如下图的tail就变成野指针了

    ✨动图解析：

    请添加图片描述
    极端情况：请添加图片描述

    💫代码实现：

    // 队头出队列
void QueuePop(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(&q));

	//1.一个节点
	//2.多个节点
	if (q->head->next == NULL)
	{
		free(q->head);
		q->head = q->tail = NULL;//避免野指针
	}
	else
	{
		QNode* next = q->head->next;
		free(q->head);
		q->head = next;
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20

    🌼4.获取队列头部元素

    这个很简单，先判空，然后直接取就行
    💫代码实现：

    QDataType QueueFront(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(&q));

	return q->head->data;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    🌼5.获取队列队尾元素

    同理，取队尾数据
    💫代码实现：

    QDataType QueueFront(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(&q));

	return q->tail->data;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    🌼6.检测队列是否为空

    ❗注意事项： 按理来说，head和tail为空，都是一起为空的，所以任选一个
    💫代码实现：

    // 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
int QueueEmpty(Queue* q)
{
	assert(q);
	return q->head == NULL;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    🌼7.获取队列中有效元素个数

    ❗注意事项：

    • 高效的方法：可以在队列里定义一个Size，插入数据的时候++，删除数据的时候--
    • 不在乎效率的方法：现场计数，遍历一遍链表，算出元素个数

    💫代码实现：

    // 获取队列中有效元素个数
int QueueSize(Queue* q)
{
	assert(q);
	QNode* cur = q->head;
	int Size = 0;
	while (cur)
	{
		Size++;
		cur = cur->next;
	}
	return Size;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13

    🌼8.销毁队列

    ❗注意事项：

    • 同样也是遍历链表，先定义一个next，为cur的下一个，防止找不到下一个，遍历完把head、tail都置空

    💫代码实现：

    void QueueDestroy(Queue* q)
{
	assert(q);
	QNode* cur = q->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	q->head = q->tail = NULL;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    请添加图片描述

    🌸三.栈和队列的区别

    void TestQueue()
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);
	QueuePush(&q, 5);

	while (!QueueEmpty(&q))
	{
		printf("%d ", QueueFront(&q));
		QueuePop(&q);
	}
	printf("\n");
}

void TestQueue2()
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	printf("%d ", QueueFront(&q));
	QueuePop(&q);
	printf("%d ", QueueFront(&q));
	QueuePop(&q);
	QueuePush(&q, 3);
	QueuePush(&q, 4);
	QueuePush(&q, 5);

	while (!QueueEmpty(&q))
	{
		printf("%d ", QueueFront(&q));
		QueuePop(&q);
	}
	printf("\n");
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39

    在这里插入图片描述

    可以知道，在队列里，无论我们以什么方法去出队列，输出的结果都不会变。简单来说：只要入的顺序是12345，不管咋样出，运行结果永远是12345，这才符合先进先出

    🌼队列的应用

    1. 排队，保持决定的公平性
    2. 广度优先遍历

    举个例子：
    栈是死胡同，队列是活胡同
    队列就好像是医院的排队：先到的先拿号，先看病。
    栈 就好比一排车开进了死胡同，那是不是只能后来进的车先出去

    请添加图片描述

    📢写在最后

    • 能看到这里的都是棒棒哒🙌！
    • 如果认真看完以上部分，肯定有所收获。
    • 接下来我还会继续写关于📚《栈和队列oj》等…
    • 💯如有错误可以尽管指出💯
    • 🥇想学吗？我教你啊🥇
    • 🎉🎉觉得博主写的还不错的可以一键三连撒🎉🎉

    在这里插入图片描述

  • 相关阅读:
    【Github开源项目体验】- ZFile 基于 Java 的在线网盘
    nextjs上手
    mysql 常见锁的类型
    linux音频-IIS音频接口
    前端使用 Konva 实现可视化设计器（3）- 单选、多选、选择框
    Python入门基础
    MFC 用Imm类库实现输入法修改输入模式
    MSVCR80.DLL 丢失修复方法：完美解决你的问题！
    数据结构之八大排序及代码
    微软将JavaScript API引入 Excel
  • 原文地址：https://blog.csdn.net/qq_42996461/article/details/125460670