2020-06-04

Daily Algorithm

4 分鐘閱讀文 (大約 628 個字)

用原生js實作堆疊

用原生javascript來實做堆疊，

堆疊（Stack），如同字面意義，你可以想像成一疊堆疊的書，或是一疊堆疊的碗盤。堆疊遵守last in first out（LIFO）原則，也就是最後放入的會被放在最後面，它也會是最先被移除的。沿用書本的比喻，第一本書會被堆在最下面，第二本、第三本一本本往上堆，最後一本就會在最上面，若你想要抽出第一本，撇開直接抽取導致書本全部跌落的暴力情況，你必須要從最上面那一本開始，一本本移除。不管你要取得哪一本，最後一本總是最先被移除的。

要實作的方法有：
push 新增元素
pop 移除最新/最上方的元素
peek 查看目前最新的元素
clear 移除堆疊裡所有元素
計算屬性：
isEmpty 查看目前堆疊情況，若無堆疊則回傳false，若堆疊中有元素傳true
size 回傳目前堆疊中元素總數

類別

因為很多方法跟js中原生陣列方法很像，所以運用陣列來做。

class Stack {
  constructor() {
    this.stack = [];
  }
}

push

push會將新的元素加在堆疊的尾端，跟陣列的push一樣

1
2
3

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

note

Array.push

pop

pop會刪除堆疊最尾端的元素，並且回傳它

1
2
3

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

note

Array.pop

peek

查看目前在堆疊最尾端的元素，不會回傳

1 2	const length = this.stack.length; return this.stack[length - 1];

clear

清除堆疊裡全部元素

1
2
3

clear() {
  this.stack.length = 0;
};

getStack

取得整個堆疊

1
2
3

getStack() {
  return this.stack;
}

size

計算屬性。取得目前堆疊長度

1
2
3

get size() {
  return this.stack.length;
};

isEmpty

計算屬性。根據目前堆疊是否為空回傳布林值

1
2
3

get isEmpty() {
  return this.stack.length !== 0 ? false : true;
}

全部程式碼：

class Stack {
  constructor() {
    this.stack = [];
  }
  get size() {
    return this.stack.length;
  };
  get isEmpty() {
    return this.stack.length !== 0 ? false : true;
  }
  push(element) {
    this.stack.push(element);
  };
  pop() {
    return this.stack.pop();
  };
  peek() {
    const length = this.stack.length;
    return this.stack[length - 1];
  };
  clear() {
    this.stack.length = 0;
  };
  getStack() {
    return this.stack;
  }
}

// 實際操作
const stack = new Stack();
stack.push(1);
stack.push(2);
// stack [1, 2]
console.log(stack.size); //2
console.log(stack.isEmpty); //false
stack.pop(); //2
console.log(stack.size) //1

參考

JavaScript資料結構及演算法實作

# 演算法

用原生js實作堆疊

類別

push

note

pop

note

peek

clear

getStack

size

isEmpty

參考

Your browser is out-of-date!