线性结构_栈结构

       1. 栈(Stack)    一种受限的线性结构

            1. 特点：

                1. 只有一个口

                2. 先进后出，后进先出

                3. 元素按照进栈顺序从栈底排到栈顶

             2. 函数调用栈：

                　　假如函数A调用函数B，函数B调用函数C

                　　则在执行的过程中，先将A压入栈，由于A没有执行完，所以不会弹出栈，

                    　　然后A中调用了B函数，B函数也被压入栈，由于B没有执行完，所以不会弹出栈

                        　　然后A中调用了C函数，C函数也被压入栈，并且在栈顶，

                            　　随后C执行结束，C函数被弹出栈，

                                　　紧接着B函数执行结束，B函数被弹出栈

                                    　　紧接,A函数执行结束，A函数弹出栈

                递归压栈(容易栈溢出)

 　　2. 栈相关的面试题

                1. 有六个元素6 5 4 3 2 1 顺序进栈，则下列不合法的出栈顺序为: ( )

                    A: 5 4 3 6 1 2              B: 4 5 3 2 1 6

                    C: 3 4 6 5 2 1              D: 2 3 4 1 5 6

                    答案为C, 注意身审题，栈中大数在下，小数在上，并且并不是说一次性全部进栈

        3. 栈结构的实现

                1. 栈结构的实现有两种方式(即存储数据的方法)

                    基于数组

                    基于链表

                2. 栈常见的操作方法

                    1. push()       添加一个新的元素到栈顶

                    2. pop()        从栈顶移除一个元素，并且将该元素返回

                    3. peek()       返回栈顶元素，此时栈没有被修改

                    4. isEmpty()    栈是都为空，为空返回true, 不为空返回false

                    5. size()       返回栈的长度，即栈中元素的个数

                    6. toString()   将栈结构中的内容以字符形式返回        

 　　4. 栈结构的函数封装

 1     // 1. 封装栈类
 2     function Stack(){
 3         // 栈的属性
 4         // 1. 初始化存储栈的数组
 5         this.items = [];
 6 
 7         // 2. 栈的简介
 8         /*************************************************/
 9         // 栈的相关操作方法
10         // 1. 将元素压入栈
11         Stack.prototype.enStack = function(element){
12             this.items.push(element);
13         }
14 
15         // 2. 从栈中取出元素
16         Stack.prototype.deStack = function(){
17             return this.items.pop();
18         }
19 
20         // 3. 查看栈顶元素
21         Stack.prototype.peek = function(){
22             return this.items[this.items.length - 1];
23         }
24 
25         // 4. 查看栈是否为空
26         Stack.prototype.isEmpty = function(){
27             return this.items.length == 0;
28         }
29 
30         // 5. 查看栈的元素个数
31         Stack.prototype.size = function(){
32             return this.items.length;
33         }
34 
35         // 6. 将栈中的内容以字符的形式返回
36         Stack.prototype.toString = function(){
37             // [1, 6, 4, 8, 9, 4] => "1 6 4 8 9 4"
38             var res = ""
39             for(var i = 0; i < this.items.lenght; i++){
40                 res += this.items[i] + " ";
41             }
42             return res;
43         }
44     }

View Code