JavaScript數(shù)據(jù)結(jié)構(gòu)《隊列》

saucxs 發(fā)布于2019-08-21 16:47 / 499人閱讀

摘要：在隊列的這種數(shù)據(jù)結(jié)構(gòu)里面，新增的元素都在尾部，要移除的元素都在頂部。代碼實現(xiàn)下面用代碼來實現(xiàn)隊列這個數(shù)據(jù)結(jié)構(gòu)，同樣都采用的語法，我們先定義一個類來表示隊列，然后在這個類的基礎(chǔ)上定義一下方法來模擬隊列的行為。

隊列和棧非常的類似，但是他們采用了不同的原則，棧采用的是后進先出，隊列正好相反，采用的是先進先出的原則。隊列的定義如下

隊列是遵循FIFO(先進先出)原則的有序集合，新添加的元素保存在隊列的尾部，要移除的元素保存在隊列的頂部。在隊列的這種數(shù)據(jù)結(jié)構(gòu)里面，新增的元素都在尾部，要移除的元素都在頂部。

舉一個生活中的例子，在我們平時去吃肯德基吃飯時肯定要排隊，這條隊伍就可以看做是一個隊列，排在隊伍前面的就是隊列的頂部，隊伍后面的就是隊列的尾部，后來的人都要排在隊伍的后面（隊列的尾部），這就符合了隊列先進先出的原則了（先排隊的可以先點餐）。

代碼實現(xiàn)

下面用代碼來實現(xiàn)隊列這個數(shù)據(jù)結(jié)構(gòu)，同樣都采用ES6的語法，我們先定義一個類Queue來表示隊列，然后在這個類的基礎(chǔ)上定義一下方法來模擬隊列的行為。

class Queue {

  constructor() {
    // 定義一個數(shù)組來保存隊列里面的元素
    this.items = []
  }

  // 在隊列尾部添加一個或者多個元素
  enqueue(element) { }
    
  // 移除隊列頂部的元素，并返回被移除的元素
  dequeue() { }
    
  // 清空隊列
  remove() { }
    
  // 返回隊列頂部的元素，不對隊列本身做修改
  front() { }
    
  // 判斷隊列是否為空
  isEmpty() { }
    
  // 返回隊列里面元素的個數(shù)
  length() { }
}

這樣我們就定義好一個基類了，下面來分別實現(xiàn)隊列的行為方法

enqueue

第一個要實現(xiàn)的就是enqueue方法，這個方法接收一個參數(shù)，然后把該參數(shù)插入隊列的尾部，因為這里我們是用數(shù)組來存儲隊列的元素的，所以可以用數(shù)組的push方法來實現(xiàn)該操作，代碼如下

 enqueue (element) {
   this.items.push(element)
 }

dequeue

下面接著實現(xiàn)dequeue方法，這個方法會從隊列里面移除項，由于隊列遵循的是先進先出的原則，所以我們要移除的元素就是隊列頂部的元素，同樣因為這里我們是用數(shù)組來存儲隊列的元素的，所以可以用數(shù)組的shift方法來實現(xiàn)該操作。代碼如下

dequeue () {
    return this.items.shift()
}

remove

接著來實現(xiàn)remove方法，改方法會移除隊列里面所有的項，同理我們把保存隊列元素的數(shù)組置空就好了，代碼如下

remove () {
    this.items = []
}

front

上面的方法都是對隊列本身有修改的，接下來要實現(xiàn)的方法front做的是只讀操作，front方法會返回隊列頂部的元素但不對隊列本身進行修改，代碼實現(xiàn)如下

front () {
    return this.items[0]
}

isEmpty

isEmpty方法判斷隊列是否為空，也就是保存隊列的數(shù)組的長度是否等于0，代碼實現(xiàn)如下

isEmpty () {
    return this.items.length === 0
}

length

最后一個方法返回隊列的長度，同理就是返回保存隊列元素的數(shù)組的長度就好了，代碼如下

length () {
    return this.item.length
}

這里和棧一樣添加一個輔助方法print來打印棧里面的元素，方便我們觀察調(diào)試，這個方法和隊列的行為無關(guān)，只是一個輔助方法

print（）{
    this.items.forEach((item, index) => {
        console.log(`${index+1}:${item}`)
    })
}

這樣隊列的方法就全部寫好了，最后完整Queue類的代碼如下

class Queue {

  constructor() {
    // 定義一個數(shù)組來保存隊列里面的元素
    this.items = []
  }

  // 在隊列尾部添加一個或者多個元素
  enqueue (element) {
      this.items.push(element)
  }
  // 移除隊列頂部的元素，并返回被移除的元素
  dequeue() { 
      return this.items.shift()
  }
  // 清空隊列
  remove() {
      this.items = []
  }
  // 返回隊列頂部的元素，不對隊列本身做修改
  front() { 
      return this.items[0]
  }
  // 判斷隊列是否為空
  isEmpty() { 
      return this.items.length === 0
  }
  // 返回隊列里面元素的個數(shù)
  length() { 
      return this.item.length
  }
    
  print（）{
      this.items.forEach((item, index) => {
          console.log(`${index+1}:${item}`)
      })
  }
}

使用Queue類

要使用這個類我們得先實例化它

const queue = new Queue()

queue.isEmpty() // true

queue.push("我是隊列的第一個元素")
queue.push("我是隊列的第二個元素")

queue.print() // 1: 我是隊列的第一個元素 2：我是隊列的第二個元素

queue.dequeue() // 我是隊列的第一個元素

queue.front() // 我是隊列的第二個元素

queue.length() // 1

queue.isEmpty() // false

queue.remove() // 這時隊列里面已經(jīng)沒有元素了

queue.isEmpty() // true

總結(jié)

隊列這種數(shù)據(jù)結(jié)構(gòu)運用的是非常的廣泛的，就比如javaScript的運行機制，我們都知道javaScript是單線程的，是不能同時執(zhí)行多個任務(wù)，但是單線程就意味著所有任務(wù)需要排隊。但是在javaScript里面，很多時候阻止線程運行的很慢的是網(wǎng)絡(luò)IO之類，這時候CPU是空閑的，這樣就會造成資源的浪費。所以javaScript在主線程之外實現(xiàn)了一個任務(wù)隊列，像IO之類比較慢的操作暫時都會掛在任務(wù)隊列上，這樣不會影響到主線程上任務(wù)的執(zhí)行，等到IO的響應(yīng)回來后再回到主線程上來執(zhí)行掛起的任務(wù)。例子就是我們的Ajax請求，定時器等。