本文转载自微信公众号《太斗闲若如》，作者AhuntSun。转载本文请联系仙若如大师公众号。一、前言1.1．什么是数据结构？数据结构是数据在计算机中存储和组织的方式。例如：图书馆管理，如何整理书籍，使藏书多，取用方便？主要考虑两个问题：操作一：如何插入新书？操作2：如何找到指定的书？《常用数据结构：》《数组》（Aarray）《栈》（Stack）《链表》（LinkedList）《图》（Graph）《哈希表》（Hash）《队列》（Queue）《树》（Tree）)《堆》(Heap)《注》：数据结构和算法与语言无关。常见的编程语言“直接或间接”地使用了上述常见的数据结构。1.2.什么是算法？算法定义了一个有限的指令集，每条指令的描述不依赖于语言；接收一些输入（在某些情况下不需要输入）；生成输入；必须在有限的步骤后终止；algorithm通俗理解：解决问题的方法/步骤逻辑。数据结构的实现离不开算法。2.栈结构（Stack）2.1．简介数组是线性结构，可以在数组的“任意位置”插入和删除元素。而“栈和队列”是比较常见的“受限线性结构”。如下图所示：image-20200226131817102栈的特点是“先进后出，后进先出”（LIFO：lastinfirstout）。《程序中的栈结构：》《函数调用栈》：A(B(C(D())))：即函数A调用B，B调用C，C调用D；在A执行的过程中，A被压入栈中，然后B执行时，B也被压入栈中，函数C和D在执行时也被压入栈中。所以当前栈的顺序是：A->B->C->D（栈顶）；函数D执行后，会出栈和释放，出栈顺序为D->C->B->A；《递归》：为什么没有停止条件的递归会导致栈溢出？比如函数A是一个递归函数，一直在调用自己（因为函数还没有执行完，所以不会把函数pop出栈），一直把同一个函数A压入栈中，最后导致《栈溢出》（StackOverfloat）3.练习题：问题：有6个元素6,5,4,3,2,1按顺序入栈，下列哪一项不是合法的入栈顺序A:543612(√)B:453216(√)C:346521(×)D:234156(√)顺序叠加不是指全部叠加一次，但要一进一出。入栈顺序为6->5->4->3->2->1。分析：A答案：65入栈，5出栈，4进出栈，3进出栈出栈，6出栈，21入入，1出栈，2出栈（整体入栈顺序符合654321）；B答案：654入栈，4出栈，5出栈，3进出栈，2进出栈，1进出栈，6出栈（整体堆叠顺序符合654321）；C答案：入栈6543，出栈3个，出栈4个，然后出栈5个，而不是6个，所以是错误的；D答案：65432入栈，2出栈，3出栈，4出栈，1进出栈，5出栈，6出栈。符合堆放顺序；《常用栈操作：》push(element)：向栈顶添加一个新元素；pop()：取出栈顶元素，同时返回取出的元素；peek()：返回栈顶元素，不对栈做任何改变（该方法不移除栈顶元素，只是返回）；isEmpty()：如果栈中没有元素则返回true，否则返回false；size()：返回栈中元素的个数。这个方法类似于数组的length属性；toString()：以字符串的形式返回栈结构的内容。2.2.封装栈类《代码实现：》//封装栈类functionStack(){//栈中的属性this.items=[]//栈相关操作//1.push()：将元素压入栈中的方法//1（不推荐）：给对象添加方法，其他对象不能复用//this.push=()=>{//}//方法2（推荐）：给Stack类添加方法，可以多objectReuseStack.prototype.push=function(element){//使用数组item的push方法实现Stack类的pop方法this.items.push(element)}//2.pop():取从栈中取出元素Stack.prototype.pop=()=>{//使用数组item的pop方法实现Stack类的pop方法returnthis.items.pop()}//3.peek():查看栈顶元素Stack.prototype.peek=()=>{returnthis.items[this.items.length-1]}//4.isEmpty()：判断栈是否为空Stack.prototype.isEmpty=()=>{//两个小时的课啊，不是this.length（不是Stack对象的长度，stack类没有length属性），但是Stack类中定义的数组项有length属性returnthis.items.length==0}//5.size():获取栈Stack.prototype中的元素个数。size=()=>{returnthis.items.length}//6.toString():将栈中的数据以字符串的形式输出Stack.prototype.toString=()=>{//想要的输出形式:20101287letresultString=''for(letiofthis.items){resultString+=i+''}returnresultString}}"测试代码："//堆栈使用lets=newStack()s.push(20)s.push(10)s.push(100)s.push(77)console.log(s)//65console.log(s.pop());//68console.log(s.pop());//69console.log(s.peek());//71console.log(s.isEmpty());//72console.log(s.size());//74console.log(s.toString());//75"测试结果："image-20200305205??050816"栈结构的简单应用："利用栈结构的特性封装十进制转二进制的功能：//简单应用：//封装函数：十进制转二进制（十转二的最后一个运算取反，余数符合栈的先进后出）letdec2bin=decNumber=>{/1。定义一个stack对象，剩下的保存varstack=newStack()//2。循环操作while(decNumber>0){//2.1。获取余数入栈stack.push(decNumber%2)//2.2。得到被整除的结果作为下一个运算Number(floor:向下舍入)decNumber=Math.floor(decNumber/2)}//3。从栈中取出0和1letbinaryString='';leta=stack.items.lengthwhile(stack.items.length!=0){binaryString+=stack.pop();}returnbinaryString;}//测试代码console.log(dec2bin(10));//103console.log(dec2bin(100));//104console.log(dec2bin(1000));//105"测试结果："image-20200305205??547226
