簡單了解JavaScript資料結構與演算法之棧

1.認識

堆疊：（stack）又稱為堆疊，它是一種運算受限的線性表。遵循後進先出（LIFO）

棧頂：限定僅在表尾進行插入和刪除操作的線性表，

棧底：限定僅在表頭進行插入和刪除操作的線性表。

進棧：向一個棧插入新元素又稱為進棧、入棧或壓棧，它是把新元素放到棧頂元素的上面，使之成為新的棧頂元素；出

棧：從一個棧刪除元素又稱作出棧或退棧，它是把棧頂元素刪除掉，使其相鄰的元素成為新的棧頂元素

2.面向過程方法源碼編寫棧

2.1思考

面向過程是什麼：

面向過程就是將解決問題的步驟分析出來，

然後用函數實現，

只要一步一步的執行呼叫他就可以了。

2.2需要實現的方法

1. push（element ）增加一個或多個元素到棧頂
2. pop（）刪除錢頂的元素，並返回移除的元素
3. peek（）返回棧頂的元素
4. isEmpty（）用於判斷棧是否為空，空則為空
5. clear（）用於清空棧的元素
6. size（）用於返回棧中元素的個數

在實現之前我們思考一下我們怎麼實現

首先我們借用數組的方法來實現，所以我們需要創建

一個空數組來模擬堆疊

2.3原始碼實現，並呼叫類別建構

一個類，用數組來模擬，

在類別中書寫各種方法

部分呼叫數組的方法。

總的來說就是用類別來包裝

陣列的方法來實現堆疊的模擬

class Stack {
   constructor() {
       this.item = []
         }
   push(element) {
        this.item.push(element)
               }
   pop() {
      return this.item.pop()
          }
   peek() {
       return this.item[this.item.length - 1]
            }
   isEmpty() {
       return this.item.length === 0
            }
   clear() {
         this.item = []
   size() {
          return this.item.length
            }
        }
//實例化Stack類別const stack = new Stack()
stack.push(4)
stack.push(6)
console.log( stack.pop())
console.log(stack.peek())
console.log(stack.isEmpty())
console.log(stack.size())

運行結果：

3.用物件導向的方法來源碼書寫

3.1思考物件

導向：

就是將建構問題的事物，分解成若干個對象，

建立對像不是為了完成某個步驟，而是為了

描述某個事物在解決問題過程的行為

3.2需要實現的方法

1. push（element ）增加一個或多個元素到棧頂
2. pop（）刪除錢頂的元素，並返回移除的元素
3. peek（）返回棧頂的元素
4. isEmpty（）用於判斷棧是否為空，空則為空
5. clear（）用於清空棧的元素
6. size（）用於返回棧中元素的個數
7. toString()用於將棧以字符串的形式打印

那麼在實現這個類，我們用對象來模擬堆疊

3.3源碼及使用類別

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
            }
    peek() {
          if(this.isEmpty()){
               return undefined
               }
         return this.items[this.count-1]
            }
    isEmpty() {
         return this.count===0
            }
    clear() {
        this.items={}
        this.count=0
          }
    size() {
       return this.count
           }
    toString(){
       if(this.isEmpty()){
        return undefined
               }
         let objectString=`${this.items[0]}`
          for(let i=1;i<this.count;i++){
               objectString=`${objectString},${this.items[i]}`
               }
         return objectString
            }
        }

  const stack = new Stack()
  stack.push(23)
  stack.push(34)
  stack.push(80)
  console.log( stack.pop())
  console.log(stack.peek())
  console.log(stack.isEmpty())
  console.log(stack.size())
  console.log(stack.toString())

在使用物件來模擬堆疊時，採用了鍵：值的方式

來儲存數據，例如this.items[this.count]=element

在這個結構中用this.count來記錄堆疊的大小，

當我們向裡面插入一個數字時，就指派count為鍵

插入的值為值。這時候就需要將this.count++.

關於pop（）與peek（），toString()方法都需要

先判斷堆疊是否為空，如果為空則回傳undefined。