學習數(shù)據(jù)結(jié)構(gòu)與算法之棧與隊列

pingan8787 發(fā)布于2019-08-20 18:37 / 3049人閱讀

摘要：于是翻出了機房里的這本學習數(shù)據(jù)結(jié)構(gòu)與算法開始學習程序員的基礎知識。這本書用了我最熟悉的來實現(xiàn)各種數(shù)據(jù)結(jié)構(gòu)和算法，而且書很薄，可以說是一本不錯的入門教程。隊列在頭部刪除元素，尾部添加元素。

本系列所有文章：
第一篇文章：學習數(shù)據(jù)結(jié)構(gòu)與算法之棧與隊列
第二篇文章：學習數(shù)據(jù)結(jié)構(gòu)與算法之鏈表
第三篇文章：學習數(shù)據(jù)結(jié)構(gòu)與算法之集合
第四篇文章：學習數(shù)據(jù)結(jié)構(gòu)與算法之字典和散列表
第五篇文章：學習數(shù)據(jù)結(jié)構(gòu)與算法之二叉搜索樹

起因

最近要準備校招，打開某網(wǎng)站準備開始刷題，發(fā)現(xiàn)算法題根本無法動手，于是覺得這塊需要惡補。(⊙v⊙)嗯，至少得先知道概念吧。于是翻出了機房里的這本《學習JavaScript數(shù)據(jù)結(jié)構(gòu)與算法》開始學習程序員的基礎知識。這本書用了我最熟悉的JS來實現(xiàn)各種數(shù)據(jù)結(jié)構(gòu)和算法，而且書很薄，可以說是一本不錯的入門教程。雖然我是個前端，但是計算機基礎不能丟下。

棧

?？梢岳斫鉃橐环N特殊的數(shù)組。遵循后進先出(LIFO)的原則，元素在棧頂添加和刪除。生活中常用來比作棧的例子主要是一疊盤子或一堆書，但是我覺得不夠形象，因為盤子或書可以從中間被抽走。所以我一般把?？闯蓮椣?，想象一下子彈被一個個推進彈匣中，比如下圖：

(圖片來自谷歌搜索，侵刪)

用JavaScript實現(xiàn)棧

聲明一個構(gòu)造函數(shù)：

function Stack () {
  // 使用數(shù)組來保存棧元素
  var items = []
}

為棧聲明一些方法：

push(elements(s))：添加一個或多個元素到棧頂

pop()：刪除位于棧頂?shù)脑兀⒎祷卦撛?/p>

peek()：返回棧頂元素

isEmpty()：當前棧為空則返回true，否則為false

size()：返回棧的元素個數(shù)

clear()：清空棧

實現(xiàn)push

用數(shù)組的push方法向數(shù)組末尾添加新元素，實現(xiàn)元素入棧

// 棧頂添加
this.push = function (element) {
  items.push(element)
}

實現(xiàn)pop

用數(shù)組的pop方法在數(shù)組末尾刪除一個元素，并返回刪除元素，實現(xiàn)元素出棧

// 棧頂刪除并返回刪除元素
this.pop = function () {
  return items.pop()
}

實現(xiàn)peek

棧頂就是數(shù)組最后一個元素，使用Array[Array.length - 1]獲得

// 返回棧頂元素
this.peek = function () {
  return items[items.length - 1]
}

實現(xiàn)其他方法

隊列里面也用了這些方法，為避免重復，就先多帶帶拿出來了。

// 棧是否為空
this.isEmpty = function () {
  return items.length === 0
}

// 返回棧里的元素個數(shù)
this.size = function () {
  return items.length
}

// 清空棧
this.clear = function () {
  items = []
}

// 打印棧
this.print = function () {
  console.log(items.toString())
}

棧的應用

書上的例子有將十進制轉(zhuǎn)二進制，這里我把后面那個十進制轉(zhuǎn)任意進制的代碼貼出來。

十進制轉(zhuǎn)二進制原理很簡單：把十進制數(shù)不斷除以2直到為0，然后把每次的余數(shù)拼接到一起就是二進制數(shù)。

轉(zhuǎn)其他進制也是類似的方法，只不過是把除以2換成其他數(shù)而已。代碼如下：

// 把十進制轉(zhuǎn)成任何進制
function BaseConverter (decNumber, base) {
  var remStack = new Stack(),
      rem,
      binaryString = "",
      digits = "0123456789ABCDEF"

  // 判斷十進制數(shù)是否為0，把余數(shù)推入棧中
  while (decNumber > 0) {
    rem = Math.floor(decNumber % base)
    remStack.push(rem)
    decNumber = Math.floor(decNumber / base)
  }

  // 把棧中的元素拼接打印出來
  while (!remStack.isEmpty()) {
    binaryString += digits[remStack.pop()]
  }

  // 返回轉(zhuǎn)換的二進制數(shù)
  return binaryString
}

這里的decNumber是要轉(zhuǎn)換的十進制數(shù)，base是要轉(zhuǎn)換的進制，remStack是上面Stack的實例，在remStack中操作棧的方法。這里的digits是對打印出來的數(shù)做一個處理，比如十六進制的數(shù)余數(shù)會大于9，那么就要用A、B、C、D、E、sF來表示10～15。

棧的學習暫時就這樣了，這里貼上代碼地址，有興趣的可以看看：

棧的實現(xiàn)-源代碼

隊列

和棧很類似，只是原則不同，隊列是先進先出（FIFO），又稱先來先服務。隊列在頭部刪除元素，尾部添加元素。生活中隊列的例子就是排隊了，這也很容易理解。

用JavaScript實現(xiàn)隊列

同樣聲明構(gòu)造函數(shù)：

function Queue () {
  var items = []
}

隊列的方法：

enqueue(elements(s))：向隊列尾部添加一個或多個元素

dequeue()：移除隊列頭部的元素并返回

front()：返回隊列頭部的元素

其他的和棧一樣。

實現(xiàn)enqueue

用push方法推入元素

// 向隊列尾部添加元素
this.enqueue = function (element) {
  items.push(element)
}

實現(xiàn)dequeue

用shift方法刪除第一個數(shù)組元素，并返回刪除的元素

// 刪除隊列頭部的元素并返回刪除元素
this.dequeue = function () {
  return items.shift()
}

實現(xiàn)front

直接返回第一個數(shù)組元素

// 返回隊列頭部的元素
this.front = function () {
  return items[0]
}

隊列的應用

書上有講優(yōu)先隊列和循環(huán)隊列的應用，這里就簡單講一下優(yōu)先隊列的原理：

要實現(xiàn)優(yōu)先隊列有兩種思路：一是將元素按正確的位置添加到隊列中，然后元素正常在隊列頭部被刪除；二是元素在隊列尾部不按優(yōu)先級正常入列，然后按優(yōu)先級刪除對應元素。

書上是按第一種思路實現(xiàn)的優(yōu)先隊列，這里限于篇幅就貼上代碼地址：

隊列的實現(xiàn)-源代碼

接下來談談循環(huán)隊列的應用——擊鼓傳花游戲

function hotPotato (nameList, num) {
  var queue = new Queue()

  // 參與者的名字入列
  for (var i = 0; i < nameList.length; i++) {
    queue.enqueue(nameList[i])
  }

  var eliminated = ""

  // 隊列中的最后一個人為勝者
  while (queue.size() > 1) {
    // 按設定的擊鼓次數(shù)，每個人都從隊列頭部出列轉(zhuǎn)到隊列尾部（模擬傳花）
    for (var i = 0; i < num; i++) {
      queue.enqueue(queue.dequeue())
    }
    // 到了規(guī)定次數(shù)后，在隊列頭部的人（相當于拿到花）被淘汰
    eliminated = queue.dequeue()
    console.log(eliminated + "在擊鼓傳花游戲中被淘汰")
  }

  // 勝者出列并被返回
  return queue.dequeue()
}

其中nameList是參與游戲的名字列表，num是擊鼓次數(shù)。

隊列學習就暫時到這里，明天繼續(xù)學習鏈表。

云服務器 GPU云服務器算法與數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法教程數(shù)據(jù)結(jié)構(gòu)與算法答案

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/84767.html

發(fā)表評論

登陸后可評論

0條評論

pingan8787

男|高級講師

我要關(guān)注我要私信

TA的文章

查詢tensorflow版本

閱讀 727·2023-04-25 22:50
記錄不存在則插入，存在則更新 → MySQL 的實現(xiàn)方式有哪些？

閱讀 1580·2021-10-08 10:05
阿里云存儲，讓更多的創(chuàng)新在身邊發(fā)生

閱讀 1004·2021-09-30 09:47
自動化測試系列（三）|UI測試

閱讀 1955·2021-09-28 09:35
C++入門—namespace的使用傻傻分不清楚&C++中函數(shù)的參數(shù)也可以配備胎&a

閱讀 857·2021-09-26 09:55
大數(shù)求余C++（超級牛逼）

閱讀 3451·2021-09-10 10:51
【C語言進階】字符串&內(nèi)存函數(shù)

閱讀 3455·2021-09-02 15:15
80VPS：日本/香港CN2服務器首月420元(續(xù)費600元),E5/16G/1TB/20M帶寬

閱讀 3323·2021-08-05 09:57

成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！

學習數(shù)據(jù)結(jié)構(gòu)與算法之棧與隊列

相關(guān)文章

Javascript數(shù)組系列一之棧與隊列

**學習數(shù)據(jù)結(jié)構(gòu)與算法之鏈表**

**學習數(shù)據(jù)結(jié)構(gòu)與算法之集合**

Javascript數(shù)組系列五之增刪改和強大的 splice()

發(fā)表評論

0條評論

pingan8787

男|高級講師

TA的文章

查詢tensorflow版本

記錄不存在則插入，存在則更新 → MySQL 的實現(xiàn)方式有哪些？

阿里云存儲，讓更多的創(chuàng)新在身邊發(fā)生

自動化測試系列（三）|UI測試

C++入門—namespace的使用傻傻分不清楚&C++中函數(shù)的參數(shù)也可以配備胎&a

大數(shù)求余C++（超級牛逼）

【C語言進階】字符串&內(nèi)存函數(shù)

80VPS：日本/香港CN2服務器首月420元(續(xù)費600元),E5/16G/1TB/20M帶寬

最新活動

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！

學習數(shù)據(jù)結(jié)構(gòu)與算法之棧與隊列

相關(guān)文章

發(fā)表評論

0條評論

男|高級講師

TA的文章

最新活動

上云采購季！| 2核2G4M爆款云服務器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！