摘要：下面来看一下，有哪些数据结构属于线性表吧栈特性先进后出只有唯一的一个出入口介绍栈又名堆栈，它是一种运算受限的线性表。
原文是在我自己博客中，小伙伴也可以点阅读原文进行跳转查看，线性表还有好听的背景音乐噢背景音乐已取消~ 2333333
什么是线性表？就是一种连续或间断存储的数组，这里的连续和间断是针对物理内存空间中线性表元素之间是否连续，其中连续数组对应内置数组的实现方式，间断数组对应的是指针的实现方式，这种方式也称为链表实现。
也就是说，线性表有两种实现方式，一种是内置数组实现，另一种是链表实现。
下面来看一下，有哪些数据结构属于线性表吧！
先进后出
只有唯一的一个出入口
介绍栈（stack）又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。
通过上面的话语表达，相信不难理解栈的概念。下面我们上图感受一下栈和入栈出栈情况：
上图中我们可以看到入栈、出栈的实际情况。只有一个入口（缺口），在这个缺口处，进行入栈和出栈操作。在现实生活中更形象的比喻就是垒砖。
砖一次一次往上叠加，取的时候也是从最上部取，一直取到底部的最后一块。
php也可以实现简单的栈，由于php中没有提供很好的操作指针的方式，所以只能通过数组的方式实现。使用连个函数就可以，它们分别是 array_push和array_pop
array_push 将一个或多个单元压入数组的末尾（入栈）;
array_pop 弹出数组最后一个单元（出栈）
简单代码示例：
$arr = []; array_push($arr, 1); // $arr[] = 1; print_r($arr); sleep(1); array_push($arr, 2); // $arr[] = 2; print_r($arr); sleep(1); array_push($arr, 3); // $arr[] = 3; print_r($arr); sleep(1); $val = array_pop($arr); echo $val . " "; print_r($arr); sleep(1); $val = array_pop($arr); echo $val . " "; print_r($arr);
把这段代码放在cli下跑，就能看到效果了，看一下运行gif图：
从命令行的执行结果来看，我们先依次入栈1、2、3三个值，后来取出的时候，也是按照栈的先进后出，后进先出的特性出栈的。
队列（queue） 特性先进先出
两个缺口，一入口，一个出口
介绍队列（queue）是一种采用先进先出(FIFO)策略的抽象数据结构，它的想法来自于生活中排队的策略。在生活中比较形象的比喻就是排队了。php实现
同样的，php中也可以以数组的形式实现队列，两个函数array_push和array_shift
array_push 将一个或多个单元压入数组的末尾（入队）;
array_shift 将数组开头的单元移出数组（出队）
可以发现array_push和上面的栈入栈是同一个函数，其实两个函数的作用一样。用在这里就表示为入队了。
简单代码示例：
header("Content-type:text/html;charset=utf-8");
$arr = [];
echo "入队-1 array_push($arr, 1)" . "
";
array_push($arr, 1); // $arr[] = 1;
print_r($arr);
sleep(1);
echo "入队-2 array_push($arr, 2)" . "
";
array_push($arr, 2); // $arr[] = 2;
print_r($arr);
sleep(1);
echo "入队-3 array_push($arr, 2)" . "
";
array_push($arr, 3); // $arr[] = 3;
print_r($arr);
sleep(1);
echo "出队-3 array_shift($arr)" . "
";
$val = array_shift($arr);
echo $val . "
";
print_r($arr);
sleep(1);
echo "出队-2 array_shift($arr)" . "
";
$val = array_shift($arr);
echo $val . "
";
print_r($arr);
图示：
从命令行的执行结果我们可以看到，我们依次入队 1、2、3三个值，出队的时候先出1，再出2.符合我们队列的特性，先进先出，后进后出。
单链表 特性由每一个节点组成
每个节点中包含下一个节点的指针(*next)
介绍单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据
链表有两个比较重要的部分组成:
指针 指向下一个节点的地址，（即内存位置的直接地址）
节点 链表中的组成部分，对于单链表，一个节点里面包含节点数据和下一个节点的指针
图中我们可以看到，单向链表由一个头指针、头节点、n个元素节点和尾节点组成。
其中头指针代表，我们根据这个指针可以找到对应的链表
头节点，用来存储链表的一些信息，比如链表长度，头节点指针指向第一个元素节点
每个节点中又包括，节点数据（data）和指针（*next指向下一个元素节点）、
一直到尾节点为null
同单链表类似由一个一个的节点组成
与单向链表不同的是，每个节点中包含了除数据(data)之外的上一个节点的指针(*prev)和下一个节点的指针(*next)
介绍双向链表又叫做双链表；跟单向链表不同的是，他的每个节点都有两个指针，一个指向前面的一个节点，一个指向后面的节点。通过这两个指针我们可以很方便的通过某一个节点，访问到相（前）邻（后）的两个节点。
我们来看一下，双向链表的图示：
图中我们可以看到，除了头节点和尾节点之外，每个中间节点与节点之间都是首尾相连，每个节点保存了上一个节点的指针和下一个节点的指针，这就是与单链表的不同之处。
注：我们也可以构造双向循环链表；尾节点的下一个指针*next指向头节点，而头节点的*prev指向尾节点；这样就构成了一个双向循环链表；下图所示，我们只需把双向链表简单改造一下即可：
总结以上，就是本篇文章介绍的内容了。
数据结构很多，也很高深，其中的算法知识，也让人回味无穷。
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/28717.html
摘要：数据结构实现链表简单介绍链表是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针。图解如下查找通过遍历链表，使用标记是否找到了正在寻找的项。一旦为，就是对包含要删除的项的节点的引用。 Python数据结构实现—链表 1. 简单介绍 链表(Linked list)是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数...
摘要：小概哈希容器也可以理解为是一种映射容器，采用哈希算法映射算法，散列算法，将不定长的数据压缩成定长的数据，这串定长值我们称为哈希值，并将不同的哈希值分组存起来，每一个分组我们认为是一个槽我们将不同的数据格式通过哈希算法，将其映射到不同的槽内， 小概 哈希容器也可以理解为是一种映射容器，采用哈希算法（映射算法，散列算法），将不定长的数据压缩成定长的数据，这串定长值我们称为 哈希值，并将不同...
摘要：在本书中你将学习比较不同算法的优缺点该使用合并排序算法还是快速排序算法或者该使用数组还是链表。这样的算法包括快速排序一种速度较快的排序算法。 在读《算法图解》这本书，这本书有两个优点： 手绘风格的图，看着很让人入戏； 算法采用Python语言描述，能更好的表达算法思想。 关于算法的学习有两点心得： 算法思想最重要，理解了思想，算法是很容易写出来的，所以尽量不要把过多精力放在细节上...
摘要：为检查长度为的列表，二分查找需要执行次操作。最后需要指出的一点是高水平的读者可研究一下二叉树关于二叉树，戳这里数据结构与算法二叉树算法常见练习在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。 常见数据结构 简单数据结构（必须理解和掌握） 有序数据结构：栈、队列、链表。有序数据结构省空间（储存空间小） 无序数据结构：集合、字典、散列表，无序...
摘要：为检查长度为的列表，二分查找需要执行次操作。最后需要指出的一点是高水平的读者可研究一下二叉树关于二叉树，戳这里数据结构与算法二叉树算法常见练习在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。 常见数据结构 简单数据结构（必须理解和掌握） 有序数据结构：栈、队列、链表。有序数据结构省空间（储存空间小） 无序数据结构：集合、字典、散列表，无序...
阅读 510·2023-04-26 00:33
阅读 3537·2021-11-24 09:39
阅读 2896·2021-09-22 15:34
阅读 2315·2019-08-23 18:07
阅读 2911·2019-08-23 18:04
阅读 3693·2019-08-23 16:06
阅读 2893·2019-08-23 15:27
阅读 1613·2019-08-23 14:32
