数据结构——栈和队列

目录

1.栈（stack）

1.1 模拟实现

1.1.1 定义栈

 1.1.2 初始化栈

1.1.3 销毁栈

​编辑 

1.1.4 入栈----栈顶

​编辑 

1.1.5 判栈空

1.1.6 出栈——栈顶

​编辑 

1.1.7 取栈顶数据

​编辑 

1.1.8 取栈的有效数据个数

 ​编辑

2.队列（queue）

2.1 模拟实现

2.1.1 定义队列

2.1.2 初始化队列

​编辑 

2.1.3 销毁队列

2.1.4 插入数据

​编辑

 2.1.5 判断队列是否为空

2.1.6 出队列

 2.1.7 取队头数据

2.1.8 取队尾数据

​编辑 

2.1.9 有效元素个数

​编辑 

 

---

1.栈（stack）

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

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

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

1.1 模拟实现

对于栈来说，咱们选择数组作为他的底层实现逻辑，原因如下：

1.栈只需要对一端进行输入输出，也就是说只需要确保输入输出那一端的实现的时间复杂度最小即可，咱们又知道数组与链表对于一端的输入输出，时间复杂度都是O（1），但是呢，比如：由于数组空间是连续的，所以说，数组直接top--,top++,即可。

2.而你的链表还需要考虑申请新结点，释放的时候别忘了将已释放的结点置为空（性能损耗）。

3.并且，数组实现可以确保cpu缓存命中率高，起码比链表要高。链表还可能出现缓存污染等问题。

所以，结合以上观点，用数组去实栈确实很方便。

1.1.1 定义栈

 1.1.2 初始化栈

1.1.3 销毁栈

 

1.1.4 入栈----栈顶

 

别忘了将栈顶的位置更新一下。

1.1.5 判栈空

1.1.6 出栈——栈顶

 

同样，直接top--即可，也算是更新了栈顶的元素位置。 

1.1.7 取栈顶数据

 

1.1.8 取栈的有效数据个数

 

 栈的实现也是非常的简单，接下来看队列。

2.队列（queue）

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

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

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

所以说队列是个两头操作的。

2.1 模拟实现

那么队列的实现咱们是用链表还是数组呢？咱们先来分析一下：

1.如果说使用数组：队列是两头操作的，对于插入那一头来说好办，时间复杂度是O（1），但是对于出队列的那一头呢？就是不太友好了，因为你得删除数据后，挪动数据，挪动数据的时间复杂度是O（n），不是我们想要的。

2.单链表：跟数组一样的，对于删除操作，时间复杂度是O（1），但是对于插入操作，得找到链表的尾部，又因为这是个单向链表，所以说又得循环遍历，找出链表的尾部，再进行插入，那这个时间复杂度是不是就是O（n）了，也不是咱们想要的。

3.哎，那么这个时候，就有人想到了，咱们用两头带指针的链表不就可以了吗？聪明，就是这样的，这样的话，对于两头的操作时间复杂度都是O（1），就是咱们想要的。

4.那么底层使用链表实现的，链表是由一个一个的结点构成的，这下子脑中就有清晰的思路了吧。

2.1.1 定义队列

2.1.2 初始化队列

 

2.1.3 销毁队列

看这个销毁代码熟悉不，没错，这个就是咱们单链表也用的销毁代码，循环销毁。

2.1.4 插入数据

• 若队列为空（phead == NULL），新节点同时作为队头和队尾。

• 否则，将新节点链接到队尾，并更新 ptail。

 2.1.5 判断队列是否为空

2.1.6 出队列

• 检查队列是否为空（size == 0 或 phead == NULL），避免空指针访问。

  • 若出队后队列为空，需将 ptail 置为 NULL，防止野指针。

  • 更新size。

 2.1.7 取队头数据

2.1.8 取队尾数据

 

2.1.9 有效元素个数

 

这个实现是不是也跟咱们的链表有异曲同工之妙。

OK，本篇完..................

本篇为C++的stack与queue打基础。