前端跳槽面试总结之堆栈、队列、链表算法类

梦里梦外; 2023-02-17 14:28 60阅读 0赞

#### 一、堆栈 ####

1.  堆通常是一个可以被看做一棵树的数组对象，堆总是满足下列性质，如下所示：

*  堆中某个节点的值总是不大于或不小于其父节点的值；
 *  堆总是一棵完全二叉树。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。

1.  堆是在程序运行时，而不是在程序编译时，申请某个大小的内存空间。即动态分配内存，对其访问和对一般内存的访问没有区别。
2.  堆是应用程序在运行的时候请求操作系统分配给自己内存，一般是申请/给予的过程。
3.  堆是指程序运行时申请的动态内存，而栈只是指一种使用堆的方法(即先进后出)。
4.  栈`（stack）`又名堆栈，一个数据集合，可以理解为只能在一端进行插入或删除操作的列表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。
5.  栈就是一个桶，后放进去的先拿出来，它下面本来有的东西要等它出来之后才能出来（先进后出）。
6.  栈`(Stack)`是操作系统在建立某个进程时或者线程（在支持多线程的操作系统中是线程）为这个线程建立的存储区域，该区域具有`FIFO`的特性，在编译的时候可以指定需要的`Stack`的大小。
7.  栈的基本操作，如下所示：

*  进栈（压栈）：`push`
 *  出栈：`pop`
 *  取栈顶：`gettop`

1.  对于一个栈，我们需要实现添加、删除元素、获取栈顶元素、已经是否为空，栈的长度、清除元素等几个基本操作，下面是基本定义，代码如下所示：

1.  栈的基本操作，代码如下所示：

var stack = new Stack();
        console.log(stack.isEmpty());//true
        stack.push(5);
        stack.push(8);
        console.log(stack.peek());//8
        stack.push(11);
        console.log(stack.size());//3
        console.log(stack.isEmpty());
        stack.push(15);
        stack.pop();
        stack.pop();
        console.log(stack.size());//2
        console.log(stack.print());//5,8

1.  通过栈实现对正整数的二进制转换，代码如下所示：

#### 二、队列 ####

1.  队列`(Queue)`是一个数据集合，仅允许在列表的一端进行插入，另一端进行删除。
2.  进行插入的一端称为队尾`(rear)`，插入动作称为进队或入队。进行删除的一端称为队头`(front)`，删除动作称为出队。
3.  队列的性质：先进先出`(First-in, First-out)`。
4.  双向队列：队列的两端都允许进行进队和出队操作。
5.  队列是遵循`FIFO(First In First Out`,先进先出,也称为先来先服务)原则的一组有序的项。队列在尾部添加新元素,并从顶部移除元素。最新添加的元素必须排在队列的末尾。队列要实现的操作基本和栈一样，只不过栈是`FILO`(先进后出)，代码如下所示：

1.  队列的基本使用，代码如下所示：

var queue = new Queue();
        console.log(queue.isEmpty());//true
        queue.enqueue('huang');
        queue.enqueue('cheng');
        console.log(queue.print());//huang,cheng
        console.log(queue.size());//2
        console.log(queue.isEmpty());//false
        queue.enqueue('du');
        console.log(queue.dequeue());//huang
        console.log(queue.print());//cheng,du

1.  优先队列，元素的添加和移除是基于优先级的。实现一个优先队列,有两种选项:设置优先级,然后在正确的位置添加元素;或者用入列操 作添加元素,然后按照优先级移除它们。 我们在这里实现的优先队列称为最小优先队列,因为优先级的值较小的元素被放置在队列最 前面(`1`代表更高的优先级)。最大优先队列则与之相反,把优先级的值较大的元素放置在队列最 前面。
2.  优先队列的定义，使用组合继承的方式继承自`Queue`队列，代码如下所示：

1.  优先队列的基本使用，代码如下所示：

#### 三、链表 ####

1.  链表中每一个元素都是一个对象，每个对象称为一个节点，包含有数据域key和指向下一个节点的指针`next`。通过各个节点之间的相互连接，最终串联成一个链表。
2.  双链表中每个节点有两个指针：一个指向后面节点、一个指向前面节点。
3.  数组的大小是固定的,从数组的起点或中间插入 或移除项的成本很高,因为需要移动元素(尽管我们已经学过的`JavaScript`的`Array`类方法可以帮 我们做这些事,但背后的情况同样是这样)。链表存储有序的元素集合,但不同于数组,链表中的元素在内存中并不是连续放置的。每个 元素由一个存储元素本身的节点和一个指向下一个元素的引用(也称指针或链接)组成。
4.  相对于传统的数组,链表的一个好处在于,添加或移除元素的时候不需要移动其他元素。然 而,链表需要使用指针,因此实现链表时需要额外注意。数组的另一个细节是可以直接访问任何 位置的任何元素,而要想访问链表中间的一个元素,需要从起点(表头)开始迭代列表直到找到 所需的元素。
5.  链表的创建，用动态原型模式来创建一个链表，列表最后一个节点的下一个元素始终是`null`，代码如下所示：

1.  链表的基本使用，代码如下所示：

var linkedList = new LinkedList();
        console.log(linkedList.isEmpty());//true;
        linkedList.append('huang');
        linkedList.append('du')
        linkedList.insert(1,'cheng');
        console.log(linkedList.toString());//huangchengdu
        console.log(linkedList.indexOf('du'));//2
        console.log(linkedList.size());//3
        console.log(linkedList.removeAt(2));//du
        console.log(linkedList.toString());//huangcheng

1.  双向链表和普通链表的区别在于,在链表中, 一个节点只有链向下一个节点的链接,而在双向链表中,链接是双向的:一个链向下一个元素, 另一个链向前一个元素。
2.  双向链表和链表的区别就是有一个`tail`属性，所以必须重写`insert、append、removeAt`方法。每个节点对应的`Node`也多了一个`prev`属性，代码如下所示：

//寄生组合式继承实现
       function inheritPrototype(subType, superType) { 
           function object(o) { 
               function F() { }
               F.prototype = o;
               return new F();
           }
           var prototype = object(superType.prototype);
           prototype.constructor = subType;
           subType.prototype = prototype;
       }
       function DoublyLinkedList() { 
           function Node(element) { 
               this.element = element;
               this.next = null;
               this.prev = null;
           }
           this.tail = null;
           LinkedList.call(this);
           //与LinkedList不同的方法自己实现。
           this.insert = function(position, element) { 
               if (position > -1 && position <= this.length) { 
                   var node = new Node(element);
                   var current = this.head;
                   var previous;
                   var index = 0;
                   if (position === 0) { 
                       if (!this.head) { 
                           this.head = node;
                           this.tail = node;
                       } else { 
                           node.next = current;
                           current.prev = node;
                           this.head = node;
                       }
                   } else if (position == this.length) { 
                       current = this.tail;
                       current.next = node;
                       node.prev = current;
                       this.tail = node;
                   } else { 
                       while (index++ < position) { 
                           previous = current;
                           current = current.next;
                       }
                       previous.next = node;
                       node.next = current;
                       current.prev = node;
                       node.prev = previous;
                   }
                   this.length++;
                   return true;
               } else { 
                   return false;
               }
           };
           this.append = function(element) { 
               var node = new Node(element);
               var current;
               if (this.head === null) { 
                   this.head = node;
                   this.tail = node;
               } else { 
                   current = this.head;
                   while (current.next !== null) { 
                       current = current.next;
                   }
                   current.next = node;
                   node.prev = current;
                   this.tail = node;
               }
               this.length++;
           };
           this.removeAt = function(position) { 
               if (position > -1 && position < this.length) { 
                   var current = this.head;
                   var previous;
                   var index = 0;
                   if (position === 0) { 
                       this.head = current.next;
                       if (this.length === 1) { 
                           this.tail = null;
                       } else { 
                           this.head.prev = null;
                       }
                   } else if (position === (this.length - 1)) { 
                       current = this.tail;
                       this.tail = current.prev;
                       this.tail.next = null;
                   } else { 
                       while (index++ < position) { 
                           previous = current;
                           current = current.next;
                       }
                       previous.next = current.next;
                       current.next.prev = previous;
                   }
                   this.length--;
                   return current.element;
               } else { 
                   return false;
               }
           };
       }
       inheritPrototype(DoublyLinkedList, LinkedList);

1.  双向链表的基本使用，代码如下所示：

var doublyList = new DoublyLinkedList();
        console.log(doublyList.isEmpty()); //true;
        doublyList.append('huang');
        doublyList.append('du')
        doublyList.insert(1, 'cheng');
        console.log(doublyList.toString()); //huangchengdu
        console.log(doublyList.indexOf('du')); //2
        console.log(doublyList.size()); //3
        console.log(doublyList.removeAt(2)); //du
        console.log(doublyList.toString()); //huangcheng

1.  循环链表可以像链表一样只有单向引用,也可以像双向链表一样有双向引用。循环链表和链 表之间唯一的区别在于,最后一个元素指向下一个元素的指针`(tail.next)`不是引用`null`, 而是指向第一个元素`(head)`。双向循环链表有指向`head`元素的`tail.next`,和指向`tail`元素的`head.prev`。