【前端數據結構基礎】棧

peixn 發(fā)布于2019-08-26 12:00 / 2645人閱讀

摘要：前言棧是一種高效的數據結構，因為數據只能在棧頂添加或刪除，所以這樣的操作很快且很容易實現。棧被稱為一種后入先出，的數據結構。二構造棧數據結構我們將使用實現棧結構，各部分功能使用注釋說明。參考資料數據結構與算法描述第章棧

前言

棧是一種高效的數據結構，因為數據只能在棧頂添加或刪除，所以這樣的操作很快且很容易實現。

一、什么是棧

棧是一種特殊的列表，棧內的元素只能通過列表的一端訪問，這一端稱之為棧頂。
棧被稱為一種后入先出（LIFO，last-in-first-out）的數據結構。
由于棧具有后入先出的特點，所以任何不在棧頂的元素都無法訪問，我們必須先拿掉上面的元素才能訪問其棧底的元素。
對棧的主要操作是將一個元素壓入棧和將一個元素彈出棧，入棧使用push()方法，出棧使用pop()方法。

二、構造棧數據結構

我們將使用JavaScript實現棧結構，各部分功能使用注釋說明。
存儲數據我們使用的是數組。

/**
 * Stack 構造方法
 */
function Stack () {
  this.dataStore = []
  this.top = 0
  this.push = push
  this.pop = pop
  this.peek = peek
  this.clear = clear
  this.length = length
}

/**
 * push() 該方法用于向棧壓入元素
 * 向棧中壓入一個新元素，將其保存在數組中變量top所對應的位置
 * 然后將 top + 1 讓其指向數組中下一個空位置
 * @param {*} element
 */
function push (element) {
  this.dataStore[this.top++] = element
}

/**
 * pop() 該方法用于從棧頂推出元素
 * 返回棧頂元素，同時將變量top - 1
 */
function pop () {
  return this.dataStore[--this.top]
}

/**
 * peek() 該方法用于返回數組的第 top - 1 個位置的元素
 */
function peek () {
  return this.dataStore[this.top - 1]
}

/**
 * length() 該方法用于獲取棧的長度
 * 返回當前top值即可獲得棧內元素個數
 */
function length () {
  return this.top
}

/**
 * clear() 該方法用于清空棧
 * 將top設為0
 */
function clear () {
  this.top = 0
}

三、棧的應用 數制間的相互轉換

我們可以利用棧將一個數字從一種數制轉換為另一種數制。
假設想將數字n轉換為以b為基數的數字，實現的算法如下：

最高位為 n%b，將此位壓入棧。

使用 n/b 代替n。

重復步驟1和2，直到n等于0，且沒有余數。

持續(xù)將棧內元素彈出，直到棧空，依次將這些元素排列即可。

此算法只針對基數為2-9的情況
代碼實現如下：

function mulBase (num, base) {
  let s = new Stack()
  do {
    s.push(num % base)
    num = Math.floor(num /= base)
  } while (num > 0) {
    let converted = ""
    while (s.length() > 0) {
      converted += s.pop()
    }
    return converted
  }
}

回文

使用棧，我們可以判斷一個字符串是否為回文。
字符串完整壓入棧內后，通過持續(xù)彈出棧中的每一個字母就可以得到一個新的字符串，該字符串剛好與原來的字符串順序相反。我們只需要比較兩個字符串即可。如果相等，就是一個回文。

function isPalindrome (word) {
  let s = new Stack()
  for (let i = 0; i < word.length; ++i) {
    s.push(word[i])
  }
  let rword = ""
  while (s.length() > 0) {
    rword += s.pop()
  }
  if (word == rword) {
    return true
  } else {
    return false  
  }
}

結束語

以上就是對JavaScript實現棧的介紹。

參考資料：數據結構與算法JavaScript描述 第4章 棧

GPU云服務器云服務器前端基礎前端基礎教程前端零基礎零基礎前端

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

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

前端進擊的巨人（二）：棧、堆、隊列、內存空間

摘要：中有三種數據結構棧堆隊列。前端進擊的巨人一執(zhí)行上下文與執(zhí)行棧，變量對象中解釋執(zhí)行棧時，舉了一個乒乓球盒子的例子，來演示棧的存取方式，這里再舉個栗子搭積木。對于基本類型，棧中存儲的就是它自身的值，所以新內存空間存儲的也是一個值。面試經常遇到的深淺拷貝，事件輪詢，函數調用棧，閉包等容易出錯的題目，究其原因，都是跟JavaScript基礎知識不牢固有關，下層地基沒打好，上層就是豆腐渣工程，...

edgardeng 2019-08-23 14:43 評論0 收藏0
學習JavaScript數據結構與算法（一）：棧與隊列

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

Flink_China 2019-08-19 17:23 評論0 收藏0
前端基礎進階（一）：內存空間詳細圖解

摘要：一棧數據結構與不同，中并沒有嚴格意義上區(qū)分棧內存與堆內存。引用數據類型的值是保存在堆內存中的對象。不允許直接訪問堆內存中的位置，因此我們不能直接操作對象的堆內存空間。為了更好的搞懂變量對象與堆內存，我們可以結合以下例子與圖解進行理解。 showImg(https://segmentfault.com/img/remote/1460000009784102?w=1240&h=683); ...

_Suqin 2019-08-21 18:30 評論0 收藏0
【進階1-3期】JavaScript深入之內存空間詳細圖解

摘要：進階期理解中的執(zhí)行上下文和執(zhí)行棧進階期深入之執(zhí)行上下文棧和變量對象但是今天補充一個知識點某些情況下，調用堆棧中函數調用的數量超出了調用堆棧的實際大小，瀏覽器會拋出一個錯誤終止運行。（關注福利，關注本公眾號回復[資料]領取優(yōu)質前端視頻，包括Vue、React、Node源碼和實戰(zhàn)、面試指導）本周正式開始前端進階的第一期，本周的主題是調用堆棧，今天是第3天。本計劃一共28期，每期重點攻...

coordinate35 2019-08-23 13:47 評論0 收藏0
Meteor——以NodeJS為基礎環(huán)境，MongoDB為數據環(huán)境的全棧開發(fā)平臺！

摘要：當一個應用啟動時，會自動加載這些庫，為應用提供了一個基礎環(huán)境。也就是說，模板文件只能包含以這三種標簽為頂層標簽的片段。在中，我們需要判斷當前的具體運行環(huán)境，以便執(zhí)行相應的代碼。一、全棧開發(fā)平臺 - 不僅僅是前端 Meteor和那些名聲如雷貫耳的前端框架，比如Angular, React等都不一樣，它是一個采用單一開發(fā)語言的全棧開發(fā)的平臺：開發(fā)者可以使用JavaScript同時進...

chenatu 2019-06-26 16:55 評論0 收藏0