前言

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

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

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

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

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

實現(xiàn)思路

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

接下來，我們來看下，一個棧都需要具備哪些功能：

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

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

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

實現(xiàn)代碼

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

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

    private items: any[];

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

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

• 根據(jù)實現(xiàn)思路實現(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)元素數(shù)量
    size():number{
        return this.items.length;
    }
    // 將棧內(nèi)元素轉(zhuǎn)為字符串
    toString(){
        return this.items.toString();
    }

完整代碼請移步：Stack.ts

編寫測試代碼

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

• 新建一個StackTest.js文件
• 實例化一個棧

const stack = new Stack();

• 測試棧內(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()

完整代碼請移步：StackTest.js

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

對象實現(xiàn)棧

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

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

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

實現(xiàn)代碼

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

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

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

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

private items: StackObj;
private count: number;

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

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

• 入棧，當前棧的大小為新元素的key。

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

• 出棧，當前棧大小-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;
}

• 返回棧頂元素，以當前棧大小-1為key獲取其對應的value值。

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

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

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

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

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

完整代碼請移步：ObjStack.ts

編寫測試代碼

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

• 新建一個StackObjTest.js文件
• 實例化一個棧

const stack = new ObjStack();

• 測試棧內(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()

完整代碼請移步：StackObjTest.js

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

二者的區(qū)別

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

對象可以通過key直接訪問到目標元素時間復雜度為O(1)，我們可以直接目標元素進行操作，速度明顯比數(shù)組快了很多倍。

接下來，我們通過一個實例來看看這兩者在執(zhí)行速度上的差異。

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

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

• 聲明一個函數(shù)參數(shù)為一個十進制數(shù)

const decimalToBinaryStack = function (decNumber) {
}

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

// 傳進來的十進制數(shù)
let number = decNumber;

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

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

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

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

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

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

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

return binaryString;

完整代碼請移步：Examples.js

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

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

最新評論