数据结构 栈和队列上

一.学习了这么久的顺序表和链表，现在来掰扯掰扯顺序表和链表的优点和缺点把。

顺序表的优点：1.尾插尾删的效率高

                         2.可以通过下标随机访问

                         3.cpu告诉缓存命中率更高

顺序表缺点:1.头部或者中部插入删除效率低

         2.扩容过程会造成时间和空间的消耗

链表的优点：1.任意位置插入删除效率高

                     2. 可以按需开辟释放空间

链表的缺点：1.不支持随机访问

                      2.频繁调用malloc会造成空间的一定损耗

在实际运用中，有关空间的损耗顺序表和链表相差不大，最重要的是根据插入数据的位置挑选合适的线性表来实现功能。

关于顺序表第三个优点的详解：

 核心关注点在cpu！

寄存器就是CPU内部用来存放数据的一些小型存储区域，用来暂时存放参与运算的数据和运算结果。一般四个字节或者是八个字节。在cpu周围大约由几十个寄存器。那么寄存器可以相当于皇帝身边的暗卫。

CPU是中央处理器（Central Processing Unit）的缩写。中央处理器是一块超大规模的集成电路，是一台计算机的运算核心和控制核心。它的功能主要是解释计算机指令以及处理计算机软件中的数据。类似于古代皇帝，是处理国家高级军务事理的。

三级缓存可以理解为cpu皇帝身边的锦衣卫，是向皇帝传输情报的机构。

主存可以理解为是中央的官员，磁盘相当于底层官员。

而远程二级存储在现实生活例子有网盘存储一些文件照片视频等，可以理解为一些村长乡绅之类的人物。

以上比喻要有不妥处，请谅解。作此比喻目的在于要理解这些具有存储数据功能的硬件的地位。

内存和主存并不是一样。内存包括主存(内存条,基于DRAM)与高速缓存(Cache,基于SRAM)两部分。

主存储器（Main memory），简称主存。是计算机硬件的一个重要部件，其作用是存放指令和数据，并能由中央处理器（CPU）直接随机存取。

内存是计算机中重要的部件之一，它是与CPU进行沟通的桥梁。计算机中所有程序的运行都是在内存中进行的，因此内存的性能对计算机的影响非常大

像类似顺序表、链表存放的数据在主存中。

程序员编写的程序根据编译链接成可执行程序，加载到内存中去，操作系统加载程序执行，并将数据指令传送到cpu缓存中去等待处理。

cpu执行指令，不会直接访问内存，由两种方式：

1.先看数据是否在三级缓存，在（命中）。直接访问

2.不在（不命中）。先将数据存储在缓存，在访问。

数据在由主存向三级缓存中存储数据，是存在局部性原理的。即要访问4个字节，可能实际会访问十六甚至更多的字节数。

二.栈

1.概念

2.实现增删查改的功能

 3.栈的相关习题讲解

有效括号

题目要求：

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
示例：

题解：左括号入栈，遇到右括号，将栈顶元素出栈匹配

 三.队列

1.概念：

 

2.实现：

 

 

3.应用：