前言

棧作為一種數(shù)據(jù)結(jié)構(gòu)，它可以應(yīng)用在很多地方，當(dāng)你需要經(jīng)常獲取剛存放進(jìn)去的數(shù)據(jù)時(shí)，那么棧這種數(shù)據(jù)結(jié)構(gòu)將是你的首選。

棧的實(shí)現(xiàn)方式一般有兩種：數(shù)組實(shí)現(xiàn)和對(duì)象實(shí)現(xiàn)，這兩種實(shí)現(xiàn)方式最終實(shí)現(xiàn)的功能都是一樣的，但是在性能上卻有著很大的差別。

本文將詳細(xì)講解這兩種實(shí)現(xiàn)方式的差異并用TypeScript將其實(shí)現(xiàn)，歡迎各位感興趣的開(kāi)發(fā)者閱讀本文。

數(shù)組實(shí)現(xiàn)棧

本文講解的是棧用代碼的實(shí)現(xiàn)，如果對(duì)棧這種數(shù)據(jù)結(jié)構(gòu)還不是很了解的話，可以移步我的另一篇文章：棧與隊(duì)列

實(shí)現(xiàn)思路

棧的核心思想為后進(jìn)先出(LIFO)，那么我們可以用數(shù)組來(lái)描述棧。

接下來(lái)，我們來(lái)看下，一個(gè)棧都需要具備哪些功能：

• 入棧，添加一個(gè)新元素至棧頂（數(shù)組的末尾）。
• 出棧，將棧頂?shù)脑匾瞥⒎祷乇灰瞥脑亍?/li>
• 獲取棧頂元素，獲取當(dāng)前棧頂元素返回。
• 判斷棧是否為空，判斷棧（數(shù)組）內(nèi)是否有數(shù)據(jù)。
• 清空棧，移除棧內(nèi)所有的元素。
• 獲取棧大小，返回棧里的元素個(gè)數(shù)。
• 輸出棧內(nèi)數(shù)據(jù)，將棧中的所有元素以字符串的形式返回。

我們分析完棧都需要具備哪些功能后，發(fā)現(xiàn)數(shù)組中提供了很多現(xiàn)成的API可以實(shí)現(xiàn)上述功能，接下來(lái)，跟大家分享下上述功能的實(shí)現(xiàn)思路。

• 入棧(push)，可以使用數(shù)組的push方法直接往數(shù)組的末尾添加元素。
• 出棧(pop)，可以使用數(shù)組的pop方法直接移除棧中的元素，該方法會(huì)返回當(dāng)前被移除的元素。
• 棧頂元素(peek)，可以通過(guò)數(shù)組的長(zhǎng)度-1獲取到數(shù)組中的最后一個(gè)元素。
• 棧是否為空(isEmpty)，可以通過(guò)判斷數(shù)組的長(zhǎng)度是否為0來(lái)實(shí)現(xiàn)。
• 清空棧(clear)，可以將數(shù)組直接賦值為空或者調(diào)用出棧方法直至棧中的數(shù)據(jù)為空。
• 棧大小(size)，可以返回?cái)?shù)組的長(zhǎng)度。
• 輸出棧內(nèi)數(shù)據(jù)，可以調(diào)用數(shù)組的toString方法將數(shù)組轉(zhuǎn)換為字符串。

實(shí)現(xiàn)代碼

有了實(shí)現(xiàn)思路后，我們就可以將上述實(shí)現(xiàn)思路轉(zhuǎn)換為代碼了。

• 新建一個(gè)Stack.ts文件
• 定義棧并規(guī)定其類(lèi)型

    private items: any[];

• 在構(gòu)造器中初始化棧

    constructor() {
      this.items = [];
    }

• 根據(jù)實(shí)現(xiàn)思路實(shí)現(xiàn)棧中的函數(shù)

    // 入棧
    push(item:any) {
        this.items.push(item);
    }
    // 出棧
    pop() {
        return this.items.pop();
    }
    // 返回棧頂元素
    peek() {
        return this.items[this.items.length - 1];
    }
    // 判斷棧是否為空
    isEmpty() {
        return this.items.length === 0;
    }
    // 清空棧棧內(nèi)元素
    clear() {
        this.items = [];
    }
    // 獲取棧內(nèi)元素?cái)?shù)量
    size():number{
        return this.items.length;
    }
    // 將棧內(nèi)元素轉(zhuǎn)為字符串
    toString(){
        return this.items.toString();
    }

完整代碼請(qǐng)移步：Stack.ts

編寫(xiě)測(cè)試代碼

上述代碼我們實(shí)現(xiàn)了一個(gè)棧，接下來(lái)我們往棧中添加幾條數(shù)據(jù)，測(cè)試棧內(nèi)的方法是否正確執(zhí)行。

• 新建一個(gè)StackTest.js文件
• 實(shí)例化一個(gè)棧

const stack = new Stack();

• 測(cè)試棧內(nèi)方法是否正確執(zhí)行

// 入棧
stack.push("第一條數(shù)據(jù)");
stack.push("第二條數(shù)據(jù)");
// 出棧
stack.pop();
// 返回棧頂元素
console.log(stack.peek());
// 查看棧大小
console.log(stack.size());
// 判斷棧是否為空
console.log(stack.isEmpty());
// 返回棧內(nèi)所有元素
console.log(stack.toString())
// 清空棧
stack.clear()

完整代碼請(qǐng)移步：StackTest.js

執(zhí)行結(jié)果如下

對(duì)象實(shí)現(xiàn)棧

實(shí)現(xiàn)一個(gè)棧最簡(jiǎn)單的方式是通過(guò)數(shù)組存儲(chǔ)每一個(gè)元素。在處理大量數(shù)據(jù)時(shí)，我們需要評(píng)估如何操作數(shù)據(jù)是最高效的。

在使用數(shù)組時(shí)，大部分方法的時(shí)間復(fù)雜度都為O(n),我們需要迭代整個(gè)數(shù)組直至找到目標(biāo)元素，在最壞的情況下我們需要迭代數(shù)組的每一個(gè)位置。數(shù)組是元素的一個(gè)有序集合，為了保證元素排列有序，它會(huì)占用更多的內(nèi)存空間。

如果我們可以直接獲取元素，占用更少的內(nèi)存空間，并且仍然保證所有元素都按照我們的需要進(jìn)行排列，就屬于最優(yōu)解決方案了。

實(shí)現(xiàn)代碼

我們可以使用一個(gè)對(duì)象來(lái)存儲(chǔ)所有的棧元素，保證它們的順序并且遵循LIFO原則。接下來(lái)我們來(lái)看看如何使用對(duì)象來(lái)實(shí)現(xiàn)棧。

• 新建一個(gè)ObjStack.ts文件
• 定義棧對(duì)象結(jié)構(gòu)

interface StackObj {
    [propName: number] : any;
}

• 定義棧并規(guī)定其類(lèi)型，count用于記錄棧的大小。

private items: StackObj;
private count: number;

• 在構(gòu)造器中初始化棧相關(guān)變量

this.items = {};
this.count = 0;

• 入棧，當(dāng)前棧的大小為新元素的key。

push(item: any) {
    this.items[this.count] = item;
    this.count++;
}

• 出棧，當(dāng)前棧大小-1，取出棧頂元素，刪除棧頂元素，返回取出的棧頂元素

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

• 返回棧頂元素，以當(dāng)前棧大小-1為key獲取其對(duì)應(yīng)的value值。

peek() {
    if(this.isEmpty()){
        return undefined;
    }
    return this.items[this.count - 1];
}

• 判斷棧是否為空，清空棧內(nèi)元素，獲取棧內(nèi)元素?cái)?shù)量

// 判斷棧是否為空
isEmpty() {
    return this.count === 0;
   }
// 清空棧內(nèi)元素
clear() {
    this.items = [];
    this.count = 0;
}
// 獲取棧內(nèi)元素?cái)?shù)量
size():number{
    return this.count;
}

• 將棧內(nèi)元素轉(zhuǎn)為字符串，遍歷當(dāng)前棧對(duì)象中的數(shù)據(jù)，將棧中的數(shù)據(jù)用逗號(hào)拼接并返回。

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;
}

完整代碼請(qǐng)移步：ObjStack.ts

編寫(xiě)測(cè)試代碼

上述代碼我們用對(duì)象實(shí)現(xiàn)了一個(gè)棧，接下來(lái)我們往棧中添加幾條數(shù)據(jù)，測(cè)試棧內(nèi)的方法是否正確執(zhí)行。

• 新建一個(gè)StackObjTest.js文件
• 實(shí)例化一個(gè)棧

const stack = new ObjStack();

• 測(cè)試棧內(nèi)方法是否正確執(zhí)行

// 入棧
stack.push("第一條數(shù)據(jù)");
stack.push("第二條數(shù)據(jù)");
// 出棧
stack.pop();
// 返回棧頂元素
console.log(stack.peek());
// 查看棧大小
console.log(stack.size());
// 判斷棧是否為空
console.log(stack.isEmpty());
// 返回棧內(nèi)所有元素
console.log(stack.toString())
// 清空棧
stack.clear()

完整代碼請(qǐng)移步：StackObjTest.js

執(zhí)行結(jié)果如下

二者的區(qū)別

數(shù)組大部分方法的時(shí)間復(fù)雜度都為O(n)，數(shù)組中的元素是一個(gè)有序集合，為了保證元素排列有序，它會(huì)占用更多的內(nèi)存空間。

對(duì)象可以通過(guò)key直接訪問(wèn)到目標(biāo)元素時(shí)間復(fù)雜度為O(1)，我們可以直接目標(biāo)元素進(jìn)行操作，速度明顯比數(shù)組快了很多倍。

接下來(lái)，我們通過(guò)一個(gè)實(shí)例來(lái)看看這兩者在執(zhí)行速度上的差異。

十進(jìn)制轉(zhuǎn)二進(jìn)制

把十進(jìn)制轉(zhuǎn)為二進(jìn)制，需要將該十進(jìn)制除以2并對(duì)商取整，直到結(jié)果是0為止。

• 聲明一個(gè)函數(shù)參數(shù)為一個(gè)十進(jìn)制數(shù)

const decimalToBinaryStack = function (decNumber) {
}

• 函數(shù)內(nèi)部聲明一個(gè)變量，用于接收當(dāng)前傳進(jìn)來(lái)的參數(shù)進(jìn)行除法運(yùn)算后得到的值。

// 傳進(jìn)來(lái)的十進(jìn)制數(shù)
let number = decNumber;

• 函數(shù)內(nèi)部實(shí)例化一個(gè)棧，用于保存模運(yùn)算后得出的值。
• 函數(shù)內(nèi)部聲明兩個(gè)變量，用戶保存當(dāng)前模運(yùn)算的值和最終生成的二進(jìn)制字符串

// 余數(shù)
let rem;
// 二進(jìn)制結(jié)果
let binaryString = "";

• while循環(huán)，判斷當(dāng)前參數(shù)進(jìn)行除法運(yùn)算后得到的值是否為0，如果不為0就對(duì)當(dāng)前結(jié)果進(jìn)行模運(yùn)算，將模運(yùn)算得到的值入棧，對(duì)當(dāng)前結(jié)果進(jìn)行除法運(yùn)算，直至當(dāng)前結(jié)果為0。

while (number > 0) {
    // 模運(yùn)算
    rem = Math.floor(number % 2);
    // 將余數(shù)入棧
    stack.push(rem);
    // 當(dāng)前十進(jìn)制結(jié)果除以二
    number = Math.floor(number / 2);
}

• while循環(huán)，將棧中的數(shù)據(jù)取出拼接到二進(jìn)制結(jié)果字符串中去

while (!stack.isEmpty()) {
    binaryString += stack.pop().toString();
}

• 返回二進(jìn)制結(jié)果字符串

return binaryString;

完整代碼請(qǐng)移步：Examples.js

實(shí)現(xiàn)代碼如上所述，唯一不同的就是一個(gè)使用的是對(duì)象棧一個(gè)使用的數(shù)組棧，接下來(lái)我們來(lái)看下不同棧的運(yùn)行時(shí)間差距。

以上就是TypeScript數(shù)組實(shí)現(xiàn)棧與對(duì)象實(shí)現(xiàn)棧的區(qū)別詳解的詳細(xì)內(nèi)容，更多關(guān)于TypeScript數(shù)組對(duì)象實(shí)現(xiàn)棧的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論