栈、队列、Set

[sfyr111]

栈(Stack)

栈的特点：
先进后出，后进先出

栈的方法：
1push: 推入
2pop: 推出

示意图
https://upload.wikimedia.org/wikipedia/commons/thumb/2/29/Data_stack.svg/391px-Data_stack.svg.png

javascript实现

const Stack = function () {
  let count = 0
  let storage = {}

  this.push = function (value) {
    storage[count] = value
    count++
  }

  this.pop = function () {
    if (count === 0) return undefined

    count--
    const result = storage[count]
    delete storage[count]
    return result
  }

  this.peek = function () {
    return storage[count - 1]
  }

  this.size = function () {
    return count
  }
}

队列(queue)

队列的特点：先进先出

javascript实现

function Queue () {
  let collection = []

  this.print = function (element) {
    console.log(collection)
  }

  this.enqueue = function (element) {
    collection.push(element)
  }

  this.dequeue = function () {
    return collection.shift()
  }

  this.front = function () {
    return collection[0]
  }

  this.size = function () {
    return collection.length
  }

  this.isEmpty = function () {
    return (collection.length === 0)
  }
}

优先级队列(PriorityQueue)

优先级队列特点：根据插入元素的优先级插入指定队列位置

javascript实现

function PriorityQueue () {
  let collection = []

  this.print = function () {
    const result = collection.map(item => item[0])
    console.log(result)
  }

  this.enqueue = function (element) {
    if (this.isEmpty()) {
      collection.push(element)
    } else {
      let added = false
      for (let i = 0; i < collection.length; i++) {
        if (element[1] < collection[i][1]) {
          collection.splice(i, 0, element)
          added = true
          break // 一旦满足插入条件跳出循环
        }
      }
      if (!added) { // 优先级最小的情况插入队列
        collection.push(element)
      }
    }
  }

  this.dequeue = function () {
    const result = collection.shift()
    return result[0]
  }

  this.front = function () {
    const result = collection[0]
    return result[0]
  }

  this.size = function () {
    return collection.length
  }

  this.isEmpty = function () {
    return (collection.length === 0)
  }
}

Set数据结构

Set数据结构的特点： 不存在重复数据
Set方法：add添加， remove删除，size长度

javascript实现

const MySet = function () {
  let collection = []

  this.has = function (element) {
    return collection.indexOf(element) !== -1
  }

  this.values = function () {
    return collection
  }

  this.add = function (element) {
    if (!this.has(element)) {
      collection.push(element)
      return true
    }
    return false
  }

  this.remove = function (element) {
    if (this.has(element)) {
      let index = collection.indexOf(element)
      collection.splice(index, 1)
      return true
    }
    return false
  }

  this.size = function () {
    return collection.length
  }

  this.union = function (otherSet) { // 连接
    let unionSet = new MySet()
    let thisSetVal = this.values()
    let otherSetVal = otherSet.values()

    thisSetVal.forEach(item => unionSet.add(item))
    otherSetVal.forEach(item => unionSet.add(item))
    return unionSet
  }

  this.intersection = function (otherSet) { // 交集
    let intersectionSet = new MySet()
    let thisSetVal = this.values()

    thisSetVal.forEach(item => {
      if (otherSet.has(item)) {
        intersectionSet.add(item)
      }
    })
    return intersectionSet
  }

  // 返回thisSet不属于otherSet的值
  this.defference = function (otherSet) {
    let defferenceSet = new MySet()
    let thisSetVal = this.values()

    thisSetVal.forEach(item => {
      if (!otherSet.has(item)) {
        defferenceSet.add(item)
      }
    })
    return defferenceSet
  }

  // thisSet是否为otherSet的子集
  this.subset = function (otherSet) {
    let thisSetVal = this.values()
    return thisSetVal.every(item => {
      return otherSet.has(item)
    })
  }
}