日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學無先后，達者為師

網站首頁 編程語言 正文

TypeScript數組實現棧與對象實現棧的區別詳解_其它

作者：神奇的程序員 ? 更新時間： 2022-11-15 編程語言

前言

棧作為一種數據結構，它可以應用在很多地方，當你需要經常獲取剛存放進去的數據時，那么棧這種數據結構將是你的首選。

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

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

數組實現棧

本文講解的是棧用代碼的實現，如果對棧這種數據結構還不是很了解的話，可以移步我的另一篇文章：棧與隊列

實現思路

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

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

  • 入棧，添加一個新元素至棧頂（數組的末尾）。
  • 出棧，將棧頂的元素移除并返回被移除的元素。
  • 獲取棧頂元素，獲取當前棧頂元素返回。
  • 判斷棧是否為空，判斷棧（數組）內是否有數據。
  • 清空棧，移除棧內所有的元素。
  • 獲取棧大小，返回棧里的元素個數。
  • 輸出棧內數據，將棧中的所有元素以字符串的形式返回。

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

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

實現代碼

有了實現思路后，我們就可以將上述實現思路轉換為代碼了。

  • 新建一個Stack.ts文件
  • 定義棧并規定其類型
    private items: any[];
  • 在構造器中初始化棧
    constructor() {
      this.items = [];
    }
  • 根據實現思路實現棧中的函數
    // 入棧
    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;
    }
    // 清空棧棧內元素
    clear() {
        this.items = [];
    }
    // 獲取棧內元素數量
    size():number{
        return this.items.length;
    }
    // 將棧內元素轉為字符串
    toString(){
        return this.items.toString();
    }

完整代碼請移步：Stack.ts

編寫測試代碼

上述代碼我們實現了一個棧，接下來我們往棧中添加幾條數據，測試棧內的方法是否正確執行。

  • 新建一個StackTest.js文件
  • 實例化一個棧
const stack = new Stack();
  • 測試棧內方法是否正確執行
// 入棧
stack.push("第一條數據");
stack.push("第二條數據");
// 出棧
stack.pop();
// 返回棧頂元素
console.log(stack.peek());
// 查看棧大小
console.log(stack.size());
// 判斷棧是否為空
console.log(stack.isEmpty());
// 返回棧內所有元素
console.log(stack.toString())
// 清空棧
stack.clear()

完整代碼請移步：StackTest.js

執行結果如下

對象實現棧

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

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

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

實現代碼

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

  • 新建一個ObjStack.ts文件
  • 定義棧對象結構
interface StackObj {
    [propName: number] : any;
}
  • 定義棧并規定其類型，count用于記錄棧的大小。
private items: StackObj;
private count: number;
  • 在構造器中初始化棧相關變量
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];
}
  • 判斷棧是否為空，清空棧內元素，獲取棧內元素數量
// 判斷棧是否為空
isEmpty() {
    return this.count === 0;
   }
// 清空棧內元素
clear() {
    this.items = [];
    this.count = 0;
}
// 獲取棧內元素數量
size():number{
    return this.count;
}
  • 將棧內元素轉為字符串，遍歷當前棧對象中的數據，將棧中的數據用逗號拼接并返回。
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

編寫測試代碼

上述代碼我們用對象實現了一個棧，接下來我們往棧中添加幾條數據，測試棧內的方法是否正確執行。

  • 新建一個StackObjTest.js文件
  • 實例化一個棧
const stack = new ObjStack();
  • 測試棧內方法是否正確執行
// 入棧
stack.push("第一條數據");
stack.push("第二條數據");
// 出棧
stack.pop();
// 返回棧頂元素
console.log(stack.peek());
// 查看棧大小
console.log(stack.size());
// 判斷棧是否為空
console.log(stack.isEmpty());
// 返回棧內所有元素
console.log(stack.toString())
// 清空棧
stack.clear()

完整代碼請移步：StackObjTest.js

執行結果如下

二者的區別

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

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

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

十進制轉二進制

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

  • 聲明一個函數參數為一個十進制數
const decimalToBinaryStack = function (decNumber) {
}
  • 函數內部聲明一個變量，用于接收當前傳進來的參數進行除法運算后得到的值。
// 傳進來的十進制數
let number = decNumber;
  • 函數內部實例化一個棧，用于保存模運算后得出的值。
  • 函數內部聲明兩個變量，用戶保存當前模運算的值和最終生成的二進制字符串
// 余數
let rem;
// 二進制結果
let binaryString = "";
  • while循環，判斷當前參數進行除法運算后得到的值是否為0，如果不為0就對當前結果進行模運算，將模運算得到的值入棧，對當前結果進行除法運算，直至當前結果為0。
while (number > 0) {
    // 模運算
    rem = Math.floor(number % 2);
    // 將余數入棧
    stack.push(rem);
    // 當前十進制結果除以二
    number = Math.floor(number / 2);
}
  • while循環，將棧中的數據取出拼接到二進制結果字符串中去
while (!stack.isEmpty()) {
    binaryString += stack.pop().toString();
}
  • 返回二進制結果字符串
return binaryString;

完整代碼請移步：Examples.js

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

原文鏈接：https://juejin.cn/post/6844904165374689287

欄目分類
最近更新