Javascript數據結構與算法（三）棧

kohoh_ 發布于2019-08-26 14:01 / 1325人閱讀

摘要：保護數據結構內部元素下劃線命名約定這只是一種約定，只能依賴于開發人員具備的常識用的限定作用于實現類實現了假的私有屬性，雖然基本類型不可變，但由于新增的方法仍然能取到所有屬性，而且是數組的形式，但我們操作的是棧，不應該出現這種行為。

棧是一種遵循后進先出（ILFO）原則的有序集合，新添加或待刪除的元素都保存在棧的同一段，稱為棧頂，另一端就叫棧底。現實中很多例子采用了這種數據結構，比如一摞書，疊放的盤子。棧通常用來保存變量、方法調用，當然也可以用于瀏覽器歷史記錄。

基于數組的棧 創建類

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

向棧頂添加元素

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

從棧頂移除元素

pop() {
    return this.items.pop();
  }

查看棧頂元素

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

檢查棧是否為空

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

清空棧元素

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

轉化為數組

toArray() {
    return this.items;
  }

轉化為字符串

toString() {
    return this.items.toString();
  }

基于Javascript對象的stack類 創建stack類

class Stack {
  constructor() {
    this.count = 0;//記錄棧的大小，幫助我們進行添加和刪除操作
    this.items = {};
  }

添加元素

push(element) {
    this.items[this.count] = element;
    this.count++;
  }

刪除元素

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

驗證一個棧是否為空和它的大小

isEmpty() {
    return this.count === 0;
  }

  size() {
    return this.count;
  }

查看棧頂的值并將棧清空

peek() {
    if (this.isEmpty()) {
      return undefined;
    }
    return this.items[this.count - 1];
  };
clear() {
    /* while (!this.isEmpty()) {
        this.pop();
      } */
    this.items = {};
    this.count = 0;
  };

轉為字符串

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

總結

除了toString方法，我們創建的其他方法的時間復雜度均是O(1),代表我們可以直接扎到目標元素并對其進行操作。

注意

目前為止我們使用的是ES6語法類，由于JavaScript語言的特點，類并不能跟其他語言一樣具有私有屬性，也就是在外部可以引用私有屬性，對其進行賦值等操作。看以下的代碼了解一下：

const stack = new Stack();
console.log(Object.getOwnPropertyNames(stack));//["count","items"]
console.log(Object.keys(stack));//["count","items"]
console.log(stack.items);//直接訪問私有屬性

那么問題來了，我們只想讓用戶使用我們暴露出來的屬性或者方法，我們該怎么實現私有屬性呢。筆者看了前輩總結的，直接把它寫上來。

保護數據結構內部元素 下劃線命名約定

class stack{
    constructor(){
        this._count = 0;
        this._items = {};
    }
};

這只是一種約定，只能依賴于開發人員具備的常識

用E2015的限定作用于Symbol實現類

const _items = Symbol("stackItems");
class Stack{
    constructor(){
        this[_items] = [];
    }
};

實現了假的私有屬性，雖然Symbol基本類型不可變，但由于ES2015新增的Object.getOwnPropertySymbols方法仍然能取到所有Symbol屬性，而且是數組的形式，但我們操作的是棧，不應該出現這種行為。別急，還有第三個方案

用ES2015的WeakMap實現類

const items = new WeakMap();
class Stack{
    constructor(){
        items.set(this,[]);
    },
    push(element){
        const s = items.get(this);
        s.push(element);
    }
}

這樣我們就實現了一個實現了一個完全的私有屬性，但是代碼可讀性對于筆者真的太難受了，不知道你們怎么覺得呢。

棧的實踐 進制轉換算法

function baseConverter(decNumber, base) {
  const remStack = new Stack();
  const digits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
  let number = decNumber;
  let rem;
  let baseString = "";

  if (!(base >= 2 && base <= 36)) {
    return "";
  }

  while (number > 0) {
    rem = Math.floor(number % base);
    remStack.push(rem);
    number = Math.floor(number / base);
  }

  while (!remStack.isEmpty()) {
    baseString += digits[remStack.pop()];
  }

平衡圓括號算法

function parenthesesChecker(symbols) {
  
const stack = new Stack();
  const opens = "([{";
  const closers = ")]}";
  let balanced = true;
  let index = 0;
  let symbol;
  let top;

  while (index < symbols.length && balanced) {
    symbol = symbols[index];
    if (opens.indexOf(symbol) >= 0) {
      stack.push(symbol);
    } else if (stack.isEmpty()) {
      balanced = false;
    } else {
      top = stack.pop();
      if (!(opens.indexOf(top) === closers.indexOf(symbol))) {
        balanced = false;
      }
    }
    index++;
  }
  return balanced && stack.isEmpty();
}

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

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

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

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

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

Flink_China 2019-08-19 17:23 評論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
JavaScript 數據結構與算法之美 - 棧內存與堆內存、淺拷貝與深拷貝

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

dailybird 2019-08-23 18:26 評論0 收藏0
[ JavaScript ] 數據結構與算法 —— 棧

摘要：而且目前大部分編程語言的高級應用都會用到數據結構與算法以及設計模式。新添加的或待刪除的元素都保存在棧的同一端，稱作棧頂，另一端就叫棧底。在棧里，新元素都靠近棧頂，舊元素都接近棧底。前言 JavaScript是當下最流行的編程語言之一，它可以做很多事情：數據可視化（D3.js，Three.js，Chart.js）; 移動端應用(React Native,Weex,AppCan,Fl...

everfight 2019-08-26 13:31 評論0 收藏0