棧

1. 用數(shù)組實現(xiàn)一個順序棧

棧: 當(dāng)某個數(shù)據(jù)集只涉及在一端插入和刪除數(shù)據(jù), 并且滿足后進先出, 就該使用棧這種數(shù)據(jù)結(jié)構(gòu)

順序棧

function Stack() {
  this.dataStore = [];
  this.top = 0;
  this.push = push;
  this.pop = pop;
  this.peek = peek;
  this.length = length;
  this.clear = clear;

  function push(element) {
    return this.dataStore[this.top++] = element;
  }

  function pop() {
    if (this.top > 0) {
      return this.dataStore[--this.top];
    } else {
      return undefined;
    }
  }

  function peek() {
    return this.dataStore[this.top - 1];
  }

  function length() {
    return this.top;  
  }

  function clear() {
    delete this.dataStore;
    this.dataStore = [];
    this.top = 0;
  }
}

// Test
const stack = new Stack();

stack.push(1);
console.log(stack.length());
console.log(stack.pop());

2. 用鏈表實現(xiàn)一個鏈?zhǔn)綏?/h3>

class Stack {
  constructor() {
    this.top = null;
    this.size = 0;
  }

  push(value) {
    ++this.size;
    const Node = new StackNode(value);

    if (this.top == null) {
      this.top = Node;
    } else {
      Node.next = this.top;
      this.top = Node;
    }
  }

  pop() {
    if (this.size <= 0) {
      return null;
    }

    --this.size;
    const PopedNode = this.top;
    this.top = this.top.next;

    return PopedNode.value;
  }

  empty() {
    while (this.top != null) {
      const currentNode = this.top;
      currentNode = null;
      --this.size;
      this.top = this.top.next;
    }
  }

}

class StackNode {
  constructor(data) {
    this.value = data;
    this.next = null;
  }
}

// Test
const stack = new Stack();
stack.push(1);
console.log(stack.size);

3. 編程模擬實現(xiàn)一個瀏覽器的前進、后退功能

class History {
  constructor() {
    this.length;
    this.st = Stack();
    this.vice_st = Stack();
  }

  go(url) {
    this.st.push(url);
  }

  forward(url) {
    this.st.push(url);
  }

  back() {
    const poped = this.st.pop();
    this.vice_st.push(poped);
  }

}

// 鏈?zhǔn)綏?class Stack {
  constructor() {
    this.top = null;
    this.size = 0;
  }

  push(value) {
    ++this.size;
    const Node = new StackNode(value);

    if (this.top == null) {
      this.top = Node;
    } else {
      Node.next = this.top;
      this.top = Node;
    }
  }

  pop() {
    if (this.size <= 0) {
      return null;
    }

    --this.size;
    const PopedNode = this.top;
    this.top = this.top.next;

    return PopedNode.value;
  }

  empty() {
    while (this.top != null) {
      const currentNode = this.top;
      currentNode = null;
      --this.size;
      this.top = this.top.next;
    }
  }

}

class StackNode {
  constructor(data) {
    this.value = data;
    this.next = null;
  }
}

隊列

1.用數(shù)組實現(xiàn)一個順序隊列

class Queue {

  constructor() {

    this.items = [];

  }

  /**

   * 向隊尾添加一個（或多個）新的元素

   * @param {*} element 新元素

   */

  enqueue(element) {

    this.items.push(element)

  }

  /**

   * 移除隊列的第一（即排在隊列最前面的）項，并返回被移除的元素

   */

  dequeue() {

    // 根據(jù)隊列的先進先出原則，使用shift方法

    // shift方法會從數(shù)組中移除存儲在索引為0的元素

    return this.items.shift()

  }

  /**

   * 返回隊列中的第一個元素--最先被添加，也將是最先被移除的元素。

   * 隊列不做任何變動（不移除元素，只返回元素信息）

   */
  front() {

    return this.items[0]

  }



  /**

   * 清除隊列中的所有元素

   */

  clear() {

    this.items = []

  }


  /**

   * 如果隊列中不包含任何元素，返回true，否則返回false

   */

  isEmpty() {

    return this.items.length === 0

  }


  /**

   * 返回隊列包含的元素個數(shù)，與數(shù)組length屬性類似

   */

  size() {

    return this.items.length

  }


  /**

   * 隊列內(nèi)容字符串化

   */

  toString() {

    return this.items.toString()

  }

}

2. 用鏈表實現(xiàn)一個鏈?zhǔn)疥犃?/h3>

//節(jié)點
function Node(data){
    this.data = data;
}
function Queue() {
    var node = new Node(null);
    this.front = node;
    this.rear = node;
}
//長度
Queue.prototype.length = function(){
    var length = 0;
    var node = this.front;
    while(node!=this.rear){
        node = node.next;
        length++;
    }
    return length;
}
Queue.prototype.enterQueue = function(node){
    node.next = null;
    this.rear.next = node;
    this.rear = node;
    return 0;
}
Queue.prototype.deleteQueue = function(){
    var p = this.front.next;
    if(this.rear == this.front){
        return 1;
    }
    this.front.next = p.next;
    if(this.rear == p){
        this.rear = this.front;
    }
    delete p;
}

3. 實現(xiàn)一個循環(huán)隊列

function Queue(maxSize) {
    this.data = new Array(maxSize);
    this.front = 0;//頭指針
    this.rear = 0;//尾指針
    this.maxSize = maxSize;
}
//長度
Queue.prototype.length = function(){
    return (this.rear-this.front+this.maxSize)%this.maxSize;
}
Queue.prototype.enterQueue = function(data){
    if((this.rear+1)%this.maxSize==this.front){
        //滿
        return 1;
    }
    this.data[this.rear] = data;
    this.rear = (this.rear+1)%this.maxSize;
    return 0;
}
Queue.prototype.deleteQueue = function(){
    if(this.front == this.rear){
        //空
        return 1;
    }
    this.front = (this.front+1)%this.maxSize;
    return 0;
}

鏈表

1. 實現(xiàn)單鏈表、循環(huán)鏈表、雙向鏈表，支持增刪操作

class Node {  // 鏈表節(jié)點
  constructor(element) {
    this.element = element;
    this.next = null;   // 節(jié)點的指向下個節(jié)點的指針
  }
}


class NodeList {   //  鏈表
  constructor(item) {
    this.head = new Node(item);   //  初始化鏈表的頭節(jié)點
  }
  /**
   * @description 插入元素
   * @param {需要插入的元素} newItem 
   * @param {插入到某一元素之后} beforeItem 
   */
  insertInNext(newItem, beforeItem) {
    let newNode = new Node(newItem);
    if (beforeItem) { //  判讀是否是插入到指定節(jié)點后面，如果不是則插入到最后一個節(jié)點。
      let currNode = this.find(beforeItem);
      newNode.next = currNode.next;
      currNode.next = newNode;
    } else {
      let lastNode = this.findLastNode();
      lastNode.next = newNode;
    }
  }
  /**
   * @description 刪除元素
   * @param {刪除的元素} newItem 
   */
  remove(item) {
    let preNode = this.findPreNode(item);  //  找到前一節(jié)點，將前一節(jié)點的next指向該節(jié)點的next
    if (preNode.next != null) {
      preNode.next = preNode.next.next;
    }
  }
  /**
   * @description 查找元素的節(jié)點
   * @param {查找的元素} item 
   */
  find(item) { //  根據(jù)元素查找節(jié)點
    let currNode = this.head;
    while (currNode.element !== item && currNode) {
      if (currNode.next) {
        currNode = currNode.next;
      } else {
        currNode = null;
      }
    }
    return currNode;
  }
  /**
   * @description 查找最后一個節(jié)點
   */
  findLastNode() {
    let currNode = this.head;
    while (currNode.next) {
      currNode = currNode.next;
    }
    return currNode;
  }
  /**
   * @description 查找元素的前一節(jié)點
   * @param {查找的元素} item 
   */
  findPreNode(item) {
    let currNode = this.head;
    while (currNode && currNode.next && currNode.next.element !== item) {
      if (currNode.next) {
        currNode = currNode.next;
      } else {
        currNode = null;
      }
    }
    return currNode;
  }
  toString() {
    let currNode = this.head;
    let strList = [];
    while (currNode.next) {
      strList.push(JSON.stringify(currNode.element));
      currNode = currNode.next;
    }
    strList.push(JSON.stringify(currNode.element));
    return strList.join('->')
  }
}

2. 實現(xiàn)單鏈表反轉(zhuǎn)

// 判斷對象是否為空
function isEmptyObject(obj) {
  for (var name in obj) {
  return false;
}
  return true;
} 

function ReverseList(pHead) {
    if (isEmptyObject(pHead)) {
        return false;
    }
    var pre = null;
    var next = null;
    while (pHead != null) {
        next = pHead.next;
        pHead.next = pre;
        pre = pHead;
        pHead = next;
    }
    return pre;
}

3. 實現(xiàn)兩個有序的鏈表合并為一個有序鏈表

var mergeTwoLists = function(l1, l2) {
  if (!l1) return l2;
  if (!l2) return l1;
  let head;
  if (l1.val <= l2.val) {
    head = l1;
    head.next = mergeTwoLists(l1.next, l2);
  } else {
    head = l2;
    head.next = mergeTwoLists(l1, l2.next);
  }
  return head
}

4. 實現(xiàn)求鏈表的中間結(jié)點

var middleNode = function(head) {
  var tail = mid = head;  //  尾部和中間結(jié)點指針
  var count = 0;
  while (tail.next !== null) {
    tail = tail.next;
    count ++;
    if (count === 2) {
      mid = mid.next;
      count = 0;
    }
  }
  if (count === 1) {
    mid = mid.next;
  }
  return mid;
}

參考資料

• js數(shù)據(jù)結(jié)構(gòu)和算法（二）棧和隊列
• JS中的算法與數(shù)據(jù)結(jié)構(gòu)——棧(Stack)
• MDN - Object.is
• 在 Javascript 中學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法
• js創(chuàng)建一條通用鏈表
• Javascript數(shù)據(jù)結(jié)構(gòu)與算法--隊列(順序隊列、優(yōu)先隊列、循環(huán)隊列)的實現(xiàn)與用法