JavaScript數據結構與算法—— 棧

王巖威發布于2019-08-23 15:11 / 2816人閱讀

摘要：棧數據結構棧是一種遵循后進先出原則的有序集合。新添加的或待刪除的元素都保存在棧的同一端，叫做棧頂，另一端叫棧底。在棧中，新元素靠近棧頂，舊元素接近棧底。

我們可以在數組的任何位置上刪除或者添加元素，但有時候我們還需要在元素的添加或刪除時有更多控制的數據結構，有兩種數據結構類似于數組，但在添加或刪除元素時更為可控，它們就是棧和隊列。
本節主要介紹棧。

1.棧數據結構

棧是一種遵循后進先出（LIFO）原則的有序集合。新添加的或待刪除的元素都保存在棧的同一端，叫做棧頂，另一端叫棧底。在棧中，新元素靠近棧頂，舊元素接近棧底。如下圖所示：

2.創建棧

// 首先創建一類表示棧
function Stack(){
    let items = []; // 選擇數組來保存棧中的元素 
    //各種屬性和方法
}

下面要為棧聲明一些方法：

push()  //  添加一個或多個新元素到棧頂
pop()  //  移除棧頂元素，同時返回被移除的元素
peek()  // 僅僅返回棧頂元素，不對棧做任何修改
isEmpty()  //  如果棧中沒有元素返回true，否則返回false
clear()  // 移除棧中所有元素
size()  // 返回棧中元素的個數（和數組length類似）

2.1 向棧添加元素

this.push() = function(element) {
    items.push(element);
}

2.2 從棧移除元素

this.pop = function() {
    items.pop();
}

2.3 查看棧頂元素

this.peek = function() {
    return items[items.length - 1];
}

2.4 查看棧是否為空

this.isEmpty = function(){
    return items.length === 0;
}
this.size = function() {
    return items.lenght;
}

2.5 清空和打印棧元素

this.clear = function() {
    items = [];
} 
this.print = function() {
    console.log(items.toString());
}

經過上述的方法的添加，我們就完整的創建了一了個棧 Stack。

3.棧的應用—十進制轉N進制

首先我們寫出將十進制轉為二進制：

function divideBy2(decNum) {
    var remStack = new Stack(),
        rem,
        binaryString = "";
    // 將十進制數除2的余數放入一個stack中    
    while(decNum > 0) {
        // 取余
        rem = Math.floor(decNum % 2);
        // 入棧
        remStack.push(rem);
        decNum = Math.floor(decNum / 2);
    }    
    // 從棧中取出轉化為字符串然后連接起來構成二進制
    while(!remStack.isEmpty()) {
        // 出棧
        binaryString += remStack.pop().toString();
    } 
    return binaryString;
}

下面十進制轉化N進制算法

function divideByN(decNum, n) {
    var remStack = new Stack(),
        rem,
        binaryString = "",
        digits = "0123456789ABCDEF";
    // 將十進制數除N的余數放入一個stack中    
    while(decNum > 0) {
        // 取余
        rem = Math.floor(decNum % n);
        // 入棧
        remStack.push(rem);
        decNum = Math.floor(decNum / n);
    }    
    // 從棧中取出轉化為字符串然后連接起來構成二進制
    while(!remStack.isEmpty()) {
        // 出棧 使用digits方便在16進制中做個對應轉化
        binaryString += digits[remStack.pop()];
    } 
    return binaryString;
}

GPU云服務器云服務器 javascript全棧視頻 javascript全棧教程 javascript全棧開發 javascript快速全棧開發

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/101649.html

學習JavaScript數據結構與算法（一）：棧與隊列

摘要：之數組操作接下來就是數據結構的第一部分，棧。以字符串顯示棧中所有內容方法的實現說明需要往棧中添加新元素，元素位置在隊列的末尾。的前端樂園原文鏈接寒假前端學習學習數據結構與算法，棧與隊列本系列的第一篇文章: 學習JavaScript數據結構與算法（一），棧與隊列第二篇文章：學習JavaScript數據結構與算法（二）：鏈表第三篇文章：學習JavaScript數據結構與算法（三）：集合第...

Flink_China 2019-08-19 17:23 評論0 收藏0
JavaScript的數據結構與算法（一） —— 棧

摘要：棧是一種遵從后進先出原則的有序集合。新添加的或待刪除的元素都保存在棧的末尾。稱作棧頂，另一端就叫棧底。在棧里，新元素都靠近棧頂，舊元素都靠近棧底。提供可操作的方法入棧出棧，但是會移掉棧中的數據。棧是一種遵從后進先出(LIFO)原則的有序集合。新添加的或待刪除的元素都保存在棧的末尾。稱作棧頂，另一端就叫棧底。在棧里，新元素都靠近棧頂，舊元素都靠近棧底。 javascript提供可操作的...

quietin 2019-08-21 17:12 評論0 收藏0
JavaScript 數據結構與算法之美 - 棧內存與堆內存、淺拷貝與深拷貝

摘要：棧內存與堆內存淺拷貝與深拷貝，可以說是前端程序員的內功，要知其然，知其所以然。棧內存與堆內存中的變量分為基本類型和引用類型。 showImg(https://segmentfault.com/img/bVbuvnj?w=900&h=250); 前言想寫好前端，先練好內功。棧內存與堆內存、淺拷貝與深拷貝，可以說是前端程序員的內功，要知其然，知其所以然。筆者寫的 JavaScrip...

dailybird 2019-08-23 18:26 評論0 收藏0
CSS技巧 - 收藏集 - 掘金

摘要：筆者作為一位，將工作以來用到的各種優秀資料神器及框架整理在此，畢竟好記性不如爛鍵盤，此前端知識點大百科全書前端掘金，，不定期更新技巧前端掘金技巧，偶爾更新。計算數組的極值技巧使你的更加專業前端掘金一個幫你提升技巧的收藏集。 CSS 樣式畫各種圖形 - 前端 - 掘金下面是一些我在 CSS 中經常用到的圖案，還有一些是在css-tricks看到的。記錄一下，以后會用到。會持續更新… 一、...

Jonathan Shieber 2019-08-29 12:33 評論0 收藏0
CSS技巧 - 收藏集 - 掘金

摘要：筆者作為一位，將工作以來用到的各種優秀資料神器及框架整理在此，畢竟好記性不如爛鍵盤，此前端知識點大百科全書前端掘金，，不定期更新技巧前端掘金技巧，偶爾更新。計算數組的極值技巧使你的更加專業前端掘金一個幫你提升技巧的收藏集。 CSS 樣式畫各種圖形 - 前端 - 掘金下面是一些我在 CSS 中經常用到的圖案，還有一些是在css-tricks看到的。記錄一下，以后會用到。會持續更新… 一、...

SHERlocked93 2019-08-22 11:04 評論0 收藏0