第四章 堆疊

自我理解

說明

堆疊是一種遵循后進先出(LIFO)原則的有序集合.新添加元素或待洗掉的元素都保存在同一端,稱為堆疊頂,另一端稱為堆疊底,新的元素靠近堆疊頂,舊元素接近堆疊底.

作用

堆疊也被用在編程語言的編譯器和記憶體中保存變數,方法呼叫等,也被用于瀏覽器歷史記錄(瀏覽器的回傳按鈕).堆疊的實際應用非常廣泛.在回溯問題中,它可以存盤訪問過的任務或路徑,撤銷操作.Java和C#用堆疊來存盤變數和方法的呼叫,特別是處理遞回演算法的時,有可能拋出一個堆疊溢位例外

簡單圖解

可以看到堆疊的資料結構只有一個口,進出資料都走這個口,這也導致了它有后進先出(LIFO)的原則,有點像是一種思想或者是一種約定吧!!!

一個堆疊基本方法

• push(element(s)) : 添加一個(或幾個)新元素到堆疊頂
• pop() : 彈出堆疊頂元素,并回傳
• peek() : 獲取堆疊頂元素
• isEmpty() : 判斷堆疊中是否有元素
• clear() : 移除堆疊中的所有元素
• size() : 回傳堆疊的元素個數

使用陣列撰寫一個堆疊

export class StackArray{
    // 堆疊的元素多少  這里可以去掉,直接那陣列的length屬性
    private stackSize:number = 0;
    // 堆疊內部元素
    private stackList:Array<any> = [];
    //建構式
    constructor() {
    }

    // 添加一個或者多個元素
    push(...elements : any){
        this.stackList = this.stackList.concat(elements);
        this.stackSize += elements.length;
        return;
    }
    // 彈出堆疊頂元素,并回傳
    pop(){
        if(this.stackSize > 0){
            this.stackSize--;
            // return  this.stackList.splice(this.size, 1);
            return this.stackList.pop();
        }
    }
    // 獲取堆疊頂元素
    peek(){
        return this.stackList[this.stackSize - 1];
    }
    // 判斷堆疊中是否有元素
    isEmpty(){
        return this.stackSize <= 0;
    }
    // 移除堆疊中的所有元素
    clear(){
       this.stackList.splice(0, this.stackSize);
       this.stackSize = 0;
    }
    // 獲取元素個數
    size(){
        return this.stackSize;
    }
}  

使用物件撰寫一個堆疊

export class StackObject{
    // 堆疊的元素多少
    private stackSize:number = 0;
    // 堆疊內部元素
    private stackObject:any = {};
    //建構式
    constructor() {
    }

    // 添加一個或者多個元素
    push(...elements : any){
        elements.forEach((element:any) => {
            this.stackObject[++this.stackSize] = element;
        })
    }
    // 彈出堆疊頂元素,并回傳
    pop(){
        if(this.stackSize > 0){
            let result = this.stackObject[this.stackSize];
            delete this.StackObject[this.stackSize];
            this.stackSize--;
            return result;
        }
    }
    // 獲取堆疊頂元素
    peek(){
        return this.stackObject[this.stackSize];
    }
    // 判斷堆疊中是否有元素
    isEmpty(){
        return this.stackSize <= 0;
    }
    // 移除堆疊中的所有元素
    clear(){
       this.stackObject = {};
       this.stackSize = 0;
    }
    // 獲取元素個數
    size(){
        return this.stackSize;
    }
}  

書中代碼

陣列版

export default class StackArray<T> {
  private items: T[];

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

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

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

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

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

  size() {
    return this.items.length;
  }

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

  toArray() {
    return this.items;
  }

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

物件版

export default class Stack<T> {
  private count: number;
  private items: any;

  constructor() {
    this.count = 0;
    this.items = {};
  }

  push(element: T) {
    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;
  }

  size() {
    return this.count;
  }

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

leetcode對應訓練

標籤：JavaScript

上一篇：第三章 陣列

下一篇：第五章 佇列與雙端佇列