前端编程应该了解的数据结构——栈、队列

数据结构

数据结构并没有官方的定义，在民间有各种定义；

1、数据结构是数据对象，以及存在于该对象的实例和组成实例的数据元素之间的各种联系；

2、数据结构是计算机中存储、组织数据的方式，通常情况下，精心选择的数据结构可以带来最有效的算法；

3、数据结构是抽象数据类型的物理实现

数据结构的实现离不开算法，算法Algorithm，单词意思为解决问题的方法和步骤

算法的定义：

1、一个有限指令集，每条指令的描述不依赖于语言

2、接受一些输入（有时不需要输入）

3、产生输出

4、一定有限步骤后终止

常用的数据结构

八种：栈、队列、链表、集合、字典、树、图、哈希表

每一种都有其对应的应用场景, 不同的数据结构的不同操作性能是不同的:

• 有的查询性能很快,有的插入速度很快,有的是插入头和尾速度很快

• 有的做范围查找很快,有的允许元素重复,有的不允许重复等等

• 在开发中如何选择,要根据具体的需求来选

在学习数据结构后，可根据业务需求选择响应的数据结构，数据结构是每一个程序员都应该学习的课程， 数据结构和语言无关, 基本常见的编程语言都有直接或者间接的使用上述常见的数据结构。

今天讲解栈和队列

栈

栈的基本特性：

1、与数组相似，但它是一种受限制的线性结构

2、看作存取数据的一个容器，只能在容器的一端操作数据

3、LIFO(last in first out ),表示先进后出，意思就是第一个进去的元素，只能在最后一个出来

4、向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素

5、从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

简单画出简图：

 在前端中简单实现对栈的操作：

用es6新增的class类封装栈的常用操作：

push()向栈顶添加一个元素；

pop()移除栈顶元素，并返回这个值；

peek()返回栈顶元素；

isEmpty()返回布尔值，栈内无任何元素返回true，否则返回false;

clear()清除栈内的所有元素

size()返回栈内元素的个数

代码实例：

 class Stack{
            constructor(){
                this.item=[]
            }
            //入栈
            push(i){
                this.item.push(i)
            }
            //出栈 删除最后一个元素并返回
            pop(){
                return this.item.pop()
            }
            //peek 返回最后一个元素
            peek(){
                return this.item[this.item.length-1]
            }
            //isEmpty是否为空
            isEmpty(){
                return this.item.length==0
            }
            // clear清空栈
            clear(){
                this.item=[]
            }
            //栈内元素的个数
            size(){
                return this.item.length
            }
        }

实际应用：利用栈实现十进制转换为二进制

class Stack{
            constructor(){
                this.item=[]
            }
            //入栈
            push(i){
                this.item.push(i)
            }
            //出栈 删除最后一个元素并返回
            pop(){
                return this.item.pop()
            }
            //peek 返回最后一个元素
            peek(){
                return this.item[this.item.length-1]
            }
            //isEmpty是否为空
            isEmpty(){
                return this.item.length==0
            }
            // clear清空栈
            clear(){
                this.item=[]
            }
            //栈内元素的个数
            size(){
                return this.item.length
            }
        }
 
       function bin(el){
        var stack=new Stack()
        // console.log(stack);
 
        //余数
      while(el>0){
        let yushu=el%2
        stack.push(yushu)
       el=Math.floor(el/2)
      }
      console.log(stack.item.length);
      var str=""
      while(stack.isEmpty()==false){
        str=str+stack.item.pop()
      }
        return str
       }
      console.log(bin(8)); //打印结果1000

队列

队列也是受限制的线性表，它的基本特性：

FIFO先进先出，意思就是先进入队列的元素先出去；

在队列前端删除元素，在后端插入元素。

画出简图：

在生活中很多例子都像队列，例如食堂排队打饭，先来排队的人，优先打到饭离开。

队列的常见操作：

enqueue()向队列尾部添加一个新的元素；

delqueue()移除队列中队首的那个元素；

front()返回队列队首的那个元素；

isEmpty()返回布尔值，如果队列不含任何元素返回true,反之false;

size()返回队列包含元素的个数。

代码实现：

 //封装一个队列
        class Queue{
            constructor(){
                this.item=[]
            }
            //入队
            enqueue(el){
                this.item.push(el)
            }
            //出队
            delqueue(){
                return  this.item.shift()
            }
            // 返回首元素
            front(){
                return this.item[0]
            }
            //判空
            isEmpty(){
                return this.item.length==0
            }
            //元素个数
            size(){
                return this.item.length
            }
        }

通过队列来实现一个击鼓传花的小游戏，每次数到3的人被淘汰，下一个人又从1开始数。

         function jigu(arr){
                //创建队列
                var queue= new Queue()
                //入队
                
                arr.forEach(el => {
                    queue.enqueue(el)
                });
 
                //数数
                let count=1
                while(queue.size()>1){
                    if(count<3){
                        queue.enqueue(queue.delqueue)
                        count++
                    }else{
                        //等于3时
                        queue.delqueue()
                        count=1
                    }
                }
                return queue.front()
            }
            var arr=["鲨鱼辣椒","蜻蜓队长", "嶂螂恶霸", "金龟次郎", "蜗了莱莱","铁甲小宝"]
            console.log(jigu(arr)); //鲨鱼辣椒

此外，我们还需要认识一种队列——优先级队列，普通的队列插入一个元素, 数据会被放在后端， 并且需要前面所有的元素都处理完成后才会处理前面的数据。在有些情况下，元素是要插队的，插入的元素与已存在队列的元素进行优先级比较，将元素插入到正确的位置。

队列优先级的实现：

实现思路：添加元素时,如果队列内无元素，则直接添加；如果有，将当前的优先级和队列中已经存在的元素优先级进行比较, 以获得自己正确的位置。

  class Node{
            constructor(el,priority){
                this.data=el,
                this.priority=priority
            }
        }
        class PriorityQueue{
            constructor(){
                this.item=[]
            }
            enqueue(el,priority){
                //创建新节点 或者直接赋值 let newnode={data:el,priority:priority}
                let newnode=new Node(el,priority)
 
                if(this.item.length==0){
                    //空队列
                    this.item.push(newnode)
                }else{
 
                    let isAdd=false
                    //非空队列
                    for (let i = 0; i < this.item.length; i++) {
                       if (newnode.priority<this.item[i].priority) {
                            this.item.splice(i,0,newnode)
                            isAdd=true
                            break
                       }
                        
                    }
                    //如果遍历完都没有比它优先级大的，就加在最后
                    if (!isAdd) {
                        this.item.push(newnode)
                    }
                }
            }
        }
        let pq=new PriorityQueue()
        pq.enqueue("qqq",10)
        pq.enqueue("qqq",100)
        pq.enqueue("qqq",101)
        console.log(pq.item);