每周一練之數據結構與算法（Queue）

anquan 發布于2019-08-23 17:10 / 2255人閱讀

摘要：與堆棧區別隊列的操作方式和堆棧類似，唯一的區別在于隊列只允許新數據在后端進行添加。移除隊列的第一項，并返回被移除的元素。三使用隊列計算斐波那契數列的第項。前兩項固定為，后面的項為前兩項之和，依次向后。

這是第二周的練習題，這里補充下咯，五一節馬上就要到了，自己的計劃先安排上了，開發一個有趣的玩意兒。

下面是之前分享的鏈接：

1.每周一練之數據結構與算法（Stack）

2.每周一練之數據結構與算法（LinkedList）

歡迎關注我的 個人主頁 &&  個人博客 && 個人知識庫 && 微信公眾號“前端自習課”

本周練習內容：數據結構與算法 —— Queue

這些都是數據結構與算法，一部分方法是團隊其他成員實現的，一部分我自己做的，有什么其他實現方法或錯誤，歡迎各位大佬指點，感謝。

一、隊列有什么特點，生活中有什么例子?

解題：
1.概念介紹

隊列，又稱為佇列（queue），是先進先出（FIFO, First-In-First-Out）的線性表。在具體應用中通常用鏈表或者數組來實現。隊列只允許在后端（稱為rear）進行插入操作，在前端（稱為front）進行刪除操作。  ——《維基百科》

隊列特點：先進先出操作。
生活中的案例：常見的排隊，在電影院也好，排隊結賬也是，排在第一位的人會先接受服務。

2.與堆棧區別
隊列的操作方式和堆棧類似，唯一的區別在于隊列只允許新數據在后端進行添加。

二、請實現一個隊列，并實現以下方法：

enqueue(element)：向隊列尾部添加一個新的項。

dequeue()：移除隊列的第一項，并返回被移除的元素。

front()：返回隊列中第一個元素 —— 最先被添加，也將是最先被移除的元素。隊列不做任何變動 (不移除元素，只返回元素信息 —— 與 Stack 類的 peek 方法類似)。

tail()：返回隊列中的最后一個元素，隊列不做任何變動。

isEmpty()：如果棧沒有任何元素就返回 true，否則返回 false。

size()：返回隊列包含的的元素個數，與數組的 length 屬性類似。

print()：打印隊列中的元素。

提示：Web 端優先使用 ES6 以上的語法實現。

解題：

 /**
  * 2. 實現一個隊列
  */
class Queue {
    constructor (){
        this.items = []
    }
    // enqueue(element)：向隊列尾部添加一個新的項。
    enqueue( element ){
        this.items.push(element)
    }
    // dequeue()：移除隊列的第一項，并返回被移除的元素。
    dequeue (){
        return this.items.shift()
    }
    // front()：返回隊列中第一個元素 —— 最先被添加，也將是最先被移除的元素。隊列不做任何變動 (不移除元素，只返回元素信息 —— 與 Stack 類的 peek 方法類似)。
    front (){
        return this.items[0]
    }
    // tail()：返回隊列中的最后一個元素，隊列不做任何變動。
    tail (){
        return this.items[this.items.length]
    }
    // isEmpty()：如果棧沒有任何元素就返回 true，否則返回 false。
    isEmpty (){
        return this.items.length === 0
    }
    // size()：返回隊列包含的的元素個數，與數組的 length 屬性類似。
    size (){
        return this.items.length
    }
    // print()：打印隊列中的元素。
    print (){
        console.log(this.items.toString())
    }
}

三、使用隊列計算斐波那契數列的第 n 項。

斐波那契數列（Fibonacci sequence），又稱黃金分割數列、因數學家列昂納多·斐波那契（Leonardoda Fibonacci）以兔子繁殖為例子而引入，故又稱為“兔子數列”，指的是這樣一個數列：

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610...

在數學上，斐波那契數列以如下被以遞推的方法定義：F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n>=3，n∈N*），即前兩項固定為 1，后面的項為前兩項之和，依次向后。在現代物理、準晶體結構、化學等領域，斐波納契數列都有直接的應用。

使用示例如下：

fibonacci(5); --> 5
fibonacci(9); --> 34
fibonacci(14); --> 377

解題：

解題方法1：

/**
 * 3. 使用隊列計算斐波那契數列的第 n 項。
 * 前兩項固定為 1，后面的項為前兩項之和，依次向后。
 * @param {Number} num 
 */

function fibonacci (num){
    if(isNaN(num) || num < 0 || num === 0) return 0
    // // 1. 直接
    // let n1 = 1, n2 = 1, sum
    // for(let i = 3; i <= num; i++){
    //     sum = n1 + n2
    //     n1 = n2
    //     n2 = sum
    // }
    // // 2. 隊列 考慮小于等于2
    // let arr = [], sum
    // num === 1 && (arr = [1])
    // num >= 2 && (arr = [1, 1])
    // for(let i = 3; i <= num; i ++){
    //     sum = arr[i-2] + arr[i-3]
    //     arr.push(sum)
    // }
    // // 3.隊列 進出隊列
    let queue = [], sum;
    for(let i = 1; i <= num; i ++){
        if(i <=2 ){
            queue.push(1)
        }else{
            sum = queue[0] + queue[1]
            queue.push(sum)
            queue.shift()
        }
    }
    return sum
}

解題方法2：

function fibonacci(n) {
    const queue = new Queue();
    queue.enqueue(1);
    queue.enqueue(1);
    
    let index = 0;
    while(index < n - 2) {
        index += 1;
        // 出隊列一個元素
        const delItem = queue.dequeue();
        // 獲取頭部值
        const headItem = queue.front();
        const nextItem = delItem + headItem;
        queue.enqueue(nextItem);
    }
    return queue.tail();  
}
console.log(fibonacci(9)); // 34

四、實現優先隊列 PriorityQueue。

現實中優先隊列的例子很多，比如機場登機的順序，頭等艙和商務艙乘客優先級高于經濟艙乘客。又如在銀行中辦理業務時，VIP 客戶的優先級高于普通客戶。要實現一個優先隊列，有兩種方式：

設置優先級，然后在正確的位置添加元素。

用入列操作添加元素，然后按照優先級移除它們。

本題要求使用第一種方式來實現優先隊列，數值越小優先級越高，若優先級相同時，先入隊的元素，排在前面。

使用示例如下：

let priorityQueue = new PriorityQueue();
priorityQueue.enqueue("leo", 2);
priorityQueue.enqueue("pingan", 1);
priorityQueue.enqueue("robin", 1);
priorityQueue.print();
// pingan - 1
// robin - 1
// leo - 2

解題：

解題方法1：

class PriorityQueue {
  constructor() {
    this._items = [];
  }
  
  enqueue(element, priority) {
        let queueElement = {
            element
            priority
        };

      if (this.isEmpty()) {
        this._items.push(queueElement);
      } else {
        let added = false;
        for (var i = 0; i < this.size(); i++) {
          if (queueElement.priority < this._items[i].priority) {
            this.items.splice(i, 0, queueElement);
            added = true;
            break ;
          }
        }
    
        if (!added) {
          this._items.push(queueElement);
        }
      }
  }

  print() {
      var strArr = [];
      strArr = this._items.map(function (item) {
        return `${item.element}->${item.priority}`;
      });
    
      console.log(strArr.toString()); 
      }
}

解題方法2：

/**
 * 4. 實現優先隊列
 */

class PriorityQueue {
    constructor (){
        this.items = []
    }
    enqueue (element, priority){
        let ele = {element, priority}
        let isAdded = false
        for(let i = 0; i < this.items.length; i++){
            if(ele.priority < this.items[i].priority){
                this.items.splice(i, 0, ele)
                isAdded = true
                break
            }
        }
        !isAdded && this.items.push(ele)
    }
    print (){
        for(let i = 0; i < this.items.length; i++){
            let {element, priority} = this.items[i]
            console.log(`${element} - ${priority}`)
        }
    }
}
let leo = new PriorityQueue()
leo.enqueue("leo", 2);
leo.enqueue("leo1", 1);
leo.enqueue("leo2", 1);
console.log(leo)

五、用隊列實現棧。

利用兩個隊列實現棧，棧的特點是后進先出，可以讓元素入隊 q1，留下隊尾元素讓其他元素出隊，暫存到 q2 中，再讓 q1 中剩下的元素出隊，即最后進的最先出來。

提示：入棧和出棧都在 q1 中完成，q2 只作為臨時中轉空間。

解題：

/**
 * 5. 隊列實現棧
 */
class Myqueue {
    constructor (){
        this.items = []
    }
    enqueue (element){
        this.items.push(element)
    }
    dequeue (){
        return this.items.shift()
    }
}
class Mystack {
    constructor (){
        this.q1 = new myQueue()
        this.q2 = new myQueue()
    }
    push (element){
        this.q1.enqueue(element)
        this.q2.items = []
        let len = this.q1.items.length
        while(len > 0){
            this.q2.enqueue(this.q1.items[len-1])
            len --
        }
    }
    pop (){
        let result = this.q2.dequeue()
        let len = this.q2.items.length
        this.q1.items = []
        while(len > 0){
            this.q1.enqueue(this.q2.items[len-1])
            len --
        }
        return result
    }
    print (){
        console.log(this.q1.items.toString())
    }
}

這里也可以直接使用第二題定義的Queue來實現：

class QueueStack {
  constructor() {
    this.queue = new Queue();
  }

  push(item) {
    this.queue.enqueue(item);
  }

  pop() {
    // 向隊列末尾追加 隊列長度-1 次，后彈出隊列頭部
    for(let i = 1; i < this.queue.size(); i += 1) {
      this.queue.enqueue(this.queue.dequeue());
    }
    return this.queue.dequeue();
  }

  peek() {
    return this.queue.tail();
  }
}

下周預告

下周將練習集合（Set） 的題目，五一要到咯，也要好好做自己一個項目了。

云服務器 GPU云服務器 webrtc之vad算法算法與數據結構數據結構與算法看動畫學算法之:hashtable

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/103908.html

每周一練之 數據結構與算法（Tree）

摘要：假設一個二叉搜索樹具有如下特征節點的左子樹只包含小于當前節點的數。所有左子樹和右子樹自身必須也是二叉搜索樹。代碼實現二叉樹節點定義來源驗證二叉搜索樹解析 showImg(https://segmentfault.com/img/remote/1460000019005270); 這是第六周的練習題，最近加班比較多，上周主要完成一篇 GraphQL入門教程，有興趣的小伙伴可以看下哈。 ...

zhonghanwen 2019-08-26 13:51 評論0 收藏0
每周一練之 數據結構與算法（Tree）

摘要：假設一個二叉搜索樹具有如下特征節點的左子樹只包含小于當前節點的數。所有左子樹和右子樹自身必須也是二叉搜索樹。代碼實現二叉樹節點定義來源驗證二叉搜索樹解析這是第六周的練習題，最近加班比較多，上周主要完成一篇 GraphQL入門教程，有興趣的小伙伴可以看下哈。下面是之前分享的鏈接： 1.每周一練之數據結構與算法（Stack） 2.每周一練之數據結構與算法（LinkedList） 3...

fizz 2019-05-22 11:25 評論0 收藏0
每周一練之 數據結構與算法（Set）

摘要：一集合是什么與它相關數學概念有哪些解題集合定義集合是一種包含不同元素的數據結構。集合中的元素稱為成員，集合最重要的兩個特點集合中的成員是無序集合中不存在相同成員即無序且唯一。 showImg(https://segmentfault.com/img/remote/1460000019005270); 這是第四周的練習題，五一放假結束，該收拾好狀態啦。下面是之前分享的鏈接： ...

silvertheo 2019-08-23 17:17 評論0 收藏0
每周一練之 數據結構與算法（Stack）

摘要：二實現一個棧，并實現下面方法添加一個新元素到棧頂。移除棧頂的元素，同時返回被移除的元素。十進制轉換為二進制請輸入正確的數值方法簡單實現下面這個方法，其實不太好，因為沒有怎么用到這次要練習的棧方法，哈哈。最近公司內部在開始做前端技術的技術分享，每周一個主題的每周一練，以基礎知識為主，感覺挺棒的，跟著團隊的大佬們學習和復習一些知識，新人也可以多學習一些知識，也把團隊內部學習氛圍營造起來...

hzx 2019-08-23 16:55 評論0 收藏0
每周一練之 數據結構與算法（Dictionary 和 HashTable）

摘要：什么是散列表和散列函數哈希表，也叫散列表，是根據關鍵碼值而直接進行訪問的數據結構。根據鍵值從散列表中移除值。請實現散列表將和存在一個對象中即可定義一個包含和屬性的類并分配到散列表。 showImg(https://segmentfault.com/img/remote/1460000019005270); 這是第五周的練習題，上周忘記發啦，這周是復習 Dictionary 和 Hash...

eternalshallow 2019-08-26 13:51 評論0 收藏0