兩種類似數(shù)組的數(shù)據(jù)結(jié)構(gòu)，在添加和刪除元素時(shí)更為可控，他們就是棧和隊(duì)列

棧是一種遵從后進(jìn)先出（LIFO）原則的有序集合。新添加或待刪除的元素都保存在棧的同一端，稱作棧頂，另一端就叫棧底。在棧里，新元素都靠近棧頂，舊元素都接近棧底。

被用在編程語言的編譯器和內(nèi)存中保存變量、方法調(diào)用等，也被用于瀏覽器歷史記錄（瀏覽器的返回按鈕）。

創(chuàng)建一個(gè)基于數(shù)組的棧

創(chuàng)建一個(gè)類來表示棧，利用數(shù)組來保存棧里的元素

class Stack {constructor() {this.items = []} }

數(shù)組允許我們在任何位置添加或刪除元素，由于棧遵循 LIFO 原則，所以需要對元素的添加和刪除做一些限制，接下來為棧聲明一些方法

• push() : 添加新元素到棧頂
• pop() : 移除棧頂?shù)?元素，同時(shí)返回被移除的元素
• peek() : 返回棧頂?shù)脑?#xff0c;不對棧做任何修改
• isEmpty() : 如果棧里沒有任何元素返回 true, 否則返回 false
• clear() : 移除棧里所有的元素
• size() : 返回棧里的元素個(gè)數(shù)

向棧添加元素，首先實(shí)現(xiàn) push() ,向棧里添加新元素，該方法只添加元素到棧頂，可以這樣寫

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

從棧移除元素，實(shí)現(xiàn) pop() 方法，移除棧里的元素，棧遵循 LIFO 原則，移除的是最后添加進(jìn)去的元素

pop() {return this.items.pop() }

限制為 push 和 pop 方法添加和刪除棧中元素，這樣棧就自然遵循了 LIFO 原則

查看棧頂元素，想知道棧里最后添加的元素是什么，可以用 peek 方法，該方法將返回棧頂?shù)脑?/p>peek() {return this.items[this.items.length - 1] }

檢查棧是否為空，實(shí)現(xiàn) isEmpty，如果棧為空的話將返回 true，否則就返回 false

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

實(shí)現(xiàn)棧的長度

size() {return this.items.length }

清空棧元素，實(shí)現(xiàn) clear 方法，移除棧里所有的元素

clear() {this.items = [] }

以上實(shí)現(xiàn)了一個(gè)棧

使用 Stack 類

在深入了解棧的應(yīng)用前，先來了解如何使用 Stack 類。首先需要初始化 Stack 類，然后驗(yàn)證一下棧是否為空（輸出是 true，因?yàn)檫€沒有往棧里添加元素）

const stack = new Stack() console.log(stack.isEmpty()) //true

接下來，往棧里添加一些元素

stack.push(5) stack.push(8)

調(diào)用 peek 方法（）,返回棧頂?shù)脑?/p>console.log(stack.peek()) //8

再添加一個(gè)元素

stack.push(11) console.log(stack.size()) //3 console.log(stack.isEmpty()) //false

繼續(xù)添加元素

stack.push(15)

下圖描繪了我們對棧的操作，以及棧的當(dāng)前狀態(tài)

調(diào)用兩次 pop 方法從棧里移除兩個(gè)元素

stack.pop() stack.pop() console.log(stack.size()) //2

在兩次調(diào)用 pop 方法前，我們的棧里有四個(gè)元素。調(diào)用兩次后，現(xiàn)在棧里僅剩下 5 和 8 了,下圖描繪了這個(gè)執(zhí)行過程

創(chuàng)建一個(gè)基于對象的 Stack 類

使用數(shù)組來存儲元素，在處理大量數(shù)據(jù)時(shí)，需評估如何操作數(shù)據(jù)是最高效的，使用數(shù)組時(shí)，大部分方法的時(shí)間復(fù)雜度是 O(n) ，我們需要迭代整個(gè)數(shù)組直到找到要找的那個(gè)元素，在最壞的情況下需要迭代數(shù)組的所有位置，其中的 n 代表數(shù)組的長度。如果數(shù)組有更多元素的話，所需的時(shí)間會更長。另外，數(shù)組是元素的一個(gè)有序集合，為了保證元素排列有序，它會占用更多的內(nèi)存空間。

如果我們能直接獲取元素，占用較少的內(nèi)存空間，并且仍然保證所有元素按照我們的需要排列，那不是更好嗎？對于使用 JavaScript 語言實(shí)現(xiàn)棧數(shù)據(jù)結(jié)構(gòu)的場景，我們也可以使用一個(gè)JavaScript 對象來存儲所有的棧元素，保證它們的順序并且遵循 LIFO 原則。我們來看看如何實(shí)現(xiàn)這樣的行為。

首先聲明一個(gè) stack 類

class Stack {constructor() {this.count = 0 //記錄棧的大小this.items = {}} }

向棧中插入元素，因?yàn)槭褂玫氖菍ο?#xff0c; 所以 push 方法只允許我們一次插入一個(gè)元素

push(element) {this.items[this.count] = elementthis.count++ }

對象是鍵值對的集合，所以要向棧中添加元素，可以使用 count 變量作為 items 對象的鍵名，插入的元素則是它的值。在向棧插入元素后，我們遞增 count 變量。

使用 Stack 類，插入元素 5，8

const stack = new Stack() stack.push(5) stack.push(8)

查看 stack

驗(yàn)證一個(gè)棧是否為空, count 屬性也表示棧的大小，因此，我們可以簡單地返回 count 屬性的值來實(shí)現(xiàn) size 方法

size() {return this.count }

驗(yàn)證棧是否為空

isEmpty() {return this.count === 0 }

從棧中彈出元素，對象中沒有直接用的 api ，所以手動實(shí)現(xiàn)

pop() {if (this.isEmpty()) {return undefined}this.count--const result = this.items[this.count]delete this.items[this.count]return result }

首先，我們需要檢驗(yàn)棧是否為空。如果為空，就返回 undefined。如果棧不為空的話，我們會將 count 屬性減 1，并保存棧頂?shù)闹?#xff0c;以便在刪除它之后將它返回。

stack.pop() //8

模擬 pop 操作, 要訪問到棧頂?shù)脑?#xff08;即最后添加的元素 8），我們需要訪問鍵值為 1 的位置。因此我們將 count 變量從 2 減為 1。這樣就可以訪問 items[1]，刪除它，并將它的值返回了。

查看棧頂?shù)脑?/p>peek() {if (this.isEmpty()) {return undefined}return this.items[this.count -1] }

清空該棧，只需要將它的值復(fù)原為構(gòu)造函數(shù)中使用的值即可

clear() {this.items = {}this.count = 0 }

創(chuàng)建 toString 方法

在數(shù)組版本中，我們不需要關(guān)心 toString 方法的實(shí)現(xiàn)，因?yàn)閿?shù)據(jù)結(jié)構(gòu)可以直接使用數(shù)組已經(jīng)提供的 toString 方法。對于使用對象的版本，我們將創(chuàng)建一個(gè) toString 方法來像數(shù)組一樣打印出棧的內(nèi)容。

toString() {if (this.isEmpty()) {return ''}let objString = `${this.items[0]}`for (let i = 1; i < this.count; i++) {objString = `${objString}, ${this.items[i]}`}return objString }

如果棧是空的，我們只需返回一個(gè)空字符串即可。如果它不是空的，就需要用它底部的第一個(gè)元素作為字符串的初始值，然后迭代整個(gè)棧的鍵，一直到棧頂，添加一個(gè)逗號以及下一個(gè)元素如果棧只包含一個(gè)元素，for循環(huán)不會執(zhí)行

除了 toString 方法，我們創(chuàng)建的其他方法的復(fù)雜度均為 O(1)，代表我們可以直接找到目標(biāo)元素并對其進(jìn)行操作（push、 pop 或 peek）。

保護(hù)數(shù)據(jù)結(jié)構(gòu)內(nèi)部元素

在創(chuàng)建別的開發(fā)者也可以使用的數(shù)據(jù)結(jié)構(gòu)或?qū)ο髸r(shí)，我們希望保護(hù)內(nèi)部的元素，只有我們暴露出的方法才能修改內(nèi)部結(jié)構(gòu)，對于 Stack 類來說，要確保元素只會被添加到棧頂，而不是棧底或其他任意位置（比如棧的中間）。

使用 WeakMap 實(shí)現(xiàn)類

WeakMap 可以存儲鍵值對，其中鍵是對象，值可以是任意數(shù)據(jù)類型,如果用 WeakMap 來存儲 items 屬性（數(shù)組版本）， Stack 類就是這樣的：

const items = new WeakMap() //聲明一個(gè) WeakMap 類型的變量 itemsclass Stack {constructor() {items.set(this, []) //以 this（Stack 類自己的引用）為鍵，把代表?xiàng)５臄?shù)組存入 items。}push(element) {//從 WeakMap 中取出值，即以 this 為鍵（行{2}設(shè)置的）從 items 中取值。const s = items.get(this)s.push(element)}pop() {const s = items.get(this)const r = s.pop()return r} }

items 在 Stack 類里是真正的私有屬性

ECMAScript 類屬性提案（易讀性更好）

class Stack {#count = 0#items = 0//方法 }

用棧解決問題

如何解決十進(jìn)制轉(zhuǎn)二進(jìn)制問題，以及任意進(jìn)制轉(zhuǎn)換的算法。

從十進(jìn)制到二進(jìn)制

該十進(jìn)制數(shù)除以 2（二進(jìn)制是滿二進(jìn)一）并對商取整，直到結(jié)果是 0 為止。舉個(gè)例子，把十進(jìn)制的數(shù) 10 轉(zhuǎn)化成二進(jìn)制的數(shù)字，過程大概是如下這樣。

function decimalToBinary(decNumber) {const remStack = new Stack()let number = decNumberlet rem let binaryString = ''while (number > 0) {rem = Math.floor(number % 2) //js 不區(qū)分整數(shù)和浮點(diǎn)數(shù)，使用 Math.floor 返回整數(shù)部分，得到余數(shù)remStack.push(rem) //放入棧里number = Math.floor(number / 2) //繼續(xù)除以2，直到結(jié)果等于0時(shí)，才會停止 }while (!remStack.isEmpty()) {binaryString += remStack.pop().toString() //用 pop 方法把棧中的元素都移除，把出棧的元素連接成字符串}return binaryString }

測試

console.log(decimalToBinary(233)) //11101001 console.log(decimalToBinary(10)) //1010 console.log(decimalToBinary(1000)) //1111101000

進(jìn)制轉(zhuǎn)換算法

修改上面的算法，使之能把十進(jìn)制轉(zhuǎn)換成基數(shù)為 2～36 的任意進(jìn)制。除了把十進(jìn)制數(shù)除以 2 轉(zhuǎn)成二進(jìn)制數(shù)，還可以傳入其他任意進(jìn)制的基數(shù)為參數(shù)，就像下面的算法這樣。

function baseConverter(decNumber, base) {const remStack = new Stack()const digits = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'let number = decNumberlet remlet baseString = ''if (!(base >= 2 && base <= 36)) {return ''}while (number > 0) {rem = Math.floor(number % base)remStack.push(rem)number = Math.floor(number / base)}while (!remStack.isEmpty()) {baseString += digits[remStack.pop()]}return baseString }console.log(baseConverter(100345, 2)); // 11000011111111001 console.log(baseConverter(100345, 8)); // 303771 console.log(baseConverter(100345, 16)); // 187F9 console.log(baseConverter(100345, 35)); // 2BW0

我們只需要改變一個(gè)地方。在將十進(jìn)制轉(zhuǎn)成二進(jìn)制時(shí)，余數(shù)是 0 或 1；在將十進(jìn)制轉(zhuǎn)成八進(jìn)制時(shí)，余數(shù)是 0～7；但是將十進(jìn)制轉(zhuǎn)成十六進(jìn)制時(shí)，余數(shù)是 0～9 加上 A、 B、 C、 D、 E 和 F（對應(yīng) 10、 11、 12、 13、 14 和 15）。因此，我們需要對棧中的數(shù)字做個(gè)轉(zhuǎn)化才可以（行{6}和行{7}）。因此，從十一進(jìn)制開始，字母表中的每個(gè)字母將表示相應(yīng)的基數(shù)。字母 A 代表基數(shù) 11， B 代表基數(shù) 12，以此類推。

總結(jié)

以上是生活随笔為你收集整理的数据结构算法 二进制转十进制_数据结构 - 栈的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。