堆疊

堆疊結構，堆疊結構就是在陣列的基礎上限制一些操作

堆疊的常用方法

• push(): 添加一個新元素到堆疊頂

• pop(): 移除堆疊頂元素，同時回傳被移除的元素

• peek(): 回傳堆疊頂元素，不對堆疊做修改

• isEmpty(): 堆疊里無元素則回傳true

• size(): 回傳堆疊的元素個數

• toString(): 將堆疊結構的內容以字符形式回傳

堆疊的代碼實作

function Stack() {
  //堆疊的屬性
  this.items  = []

  //堆疊的操作

  Stack.prototype.push = function(element) {
    this.items.push(element)
  }

  Stack.prototype.pop = function() {
    return this.items.pop()
  }

  Stack.prototype.peek = function() {
    return this.items[this.items.length - 1]
  }

  Stack.prototype.isEmpty = function() {
    return this.items.length == 0
  }

  Stack.prototype.size = function() {
    return this.items.length
  }

  Stack.prototype.toString = function() {
    let resultString = ""
    for (const item of this.items) {
      resultString += item + ' '
    }
    return resultString
  }
}

通過堆疊結構實作二進制轉化為十進制

每次將余數壓入堆疊中，最后出堆疊的順序便是轉化的結果

function dec2Bin(decNumber) {

  let stack = new Stack()
  while (decNumber > 0) {
    stack.push(decNumber % 2)

    decNumber = Math.floor(decNumber / 2)
  }

  let binaryString = ""
  while(!stack.isEmpty()) {
    binaryString += stack.pop()
  }
  return binaryString
}

佇列

佇列分前端后后端，在后端加入元素，在前端洗掉元素

特點：先進先出

佇列常用方法

• enqueue(element): 向佇列尾部添加一個新的項

• dequeue(): 移除佇列的第一項，并回傳移除的元素

• front(): 回傳佇列中第一個元素，不改變原佇列

• isEmpty(): true&false

• size(): 元素個數

• toString(): 將佇列中的內容轉為字串形式

基于陣列的佇列封裝

function Queue() {
  //屬性
  this.items = []
  //方法
  Queue.prototype.enqueue = function(element) {
    this.items.push(element)
  }
  Queue.prototype.dequeue = function() {
    return this.items.shift()
  }
  Queue.prototype.front = function() {
    return this.items[0]
  }
  Queue.prototype.isEmpty = function() {
    return this.items.length == 0
  }
  Queue.prototype.size = function() {
    return this.items.length
  }
  Queue.prototype.toString = function() {
    let resString = ""
    for (const item of this.items) {
      resString += item + " "
    }
    return resString
  }
}

擊鼓傳花游戲的實作

代碼實作

function passGame(nameList, num) {
  let queue = new Queue()
  //先將所有依次加入佇列
  for (const item of nameList) {
    queue.enqueue(item)
  }

  //開始數數
  while(queue.size() > 1) {
    for(let i = 1;i < num;i ++) {
      queue.enqueue(queue.dequeue())
    }
    queue.dequeue()
  }
  let name = queue.front()
  console.log(name)
}
passGame([10,20,30,40],3)

優先級佇列的實作

需要給佇列中的每個專案添加一個priority，表示優先級高低

function PrioityQueue() {

  this.items = []

  function QueueElement(element, priority) {
    this.element = element
    this.priority = priority
  }

  PrioityQueue.prototype.enqueue = function (element, priority) {
    let queueElement = new QueueElement(element, priority)
    //判斷佇列是否未空
    if (this.items.length == 0) {
      this.items.push(queueElement)
    } else {
      let added = false
      for (let i = 0; i < this.items.length; i++) {
        if (queueElement.priority < this.items[i].priority) {
          this.items.splice(i, 0, queueElement)
          added = true
          break
        }
      }
      //不需要插入則直接放入最后
      if (!added) {
        this.items.push(queueElement)
      }
    }
  }
  PrioityQueue.prototype.dequeue = function () {
    return this.items.shift()
  }
  PrioityQueue.prototype.front = function () {
    return this.items[0]
  }
  PrioityQueue.prototype.isEmpty = function () {
    return this.items.length == 0
  }
  PrioityQueue.prototype.size = function () {
    return this.items.length
  }
  PrioityQueue.prototype.toString = function () {
    let resString = ""
    for (const item of this.items) {
      resString += item + " "
    }
    return resString
  }
}