单链表

'use strict';

function Node(value) {
  this.value = value;
  this.next = null;
}

function LList() {
  this.head = new Node('head');
  this.find = find;
  this.insert = insert;
  this.remove = remove;
  this.display = display;
}

function find(item) {
  let currNode = this.head;
  while (currNode.value !== item && currNode !== null) {
    currNode = currNode.next;
  }
  return currNode;
}

function insert(value, item) {
  const newNode = new Node(value);
  let current;
  if (item) {
    current = this.find(item);
    //console.log(current.value)
    newNode.next = current.next;
  } else {
    current = this.head;
    while (current.next !== null) {
      current = current.next;
    }
  }
  current.next = newNode;
}

function display() {
  let currNode = this.head;
  while (currNode !== null) {
    console.log(currNode.value);
    currNode = currNode.next;
  }
}

function remove(item) {
  let currNode = this.head;
  while (currNode.next !== null && currNode.next.value !== item) {
    currNode = currNode.next;
  }
  if (currNode.next !== null) {
    let rmNode = currNode.next;
    currNode.next = rmNode.next;
    rmNode.next = null;
  }
}

const cities = new LList();
cities.insert('Conway', 'head');
cities.insert('Russellville', 'Conway');
cities.insert('Alma', 'Russellville');
cities.insert('testNode');
cities.display();
console.log('-------------');
cities.remove('Alma');
cities.display();

队列

'use strict';

function Queue() {
  this.dataScore = [];
  this.head = 0;
  this.tail = 0;
  this.enqueue = enqueue;
  this.dequeue = dequeue;
  this.front = front;
  this.back = back;
  this.queueToString = queueToString;
  this.empty = empty;
};

function enqueue(element) {
  this.dataScore[this.tail++] = element;
};
function dequeue() {
  this.tail--;
  return this.dataScore.shift();
};
function front() {
  if (this.empty()) return '';
  return this.dataScore[this.head];
};
function back() {
  if (this.empty()) return '';
  return this.dataScore[this.tail - 1];
}
function queueToString() {
  if (this.empty()) return '';
  let str = '';
  let i = this.head;
  while (i < this.tail) {
    str += this.dataScore[i] + ' ';
    i++;
  }

  return str;
};
function empty() {
  if (this.tail === this.head) return true;

  return false;
};

const q = new Queue();
q.enqueue('a');
q.enqueue('b');
q.enqueue('c');
q.enqueue('d');
q.enqueue('e');
q.enqueue('f');
console.log(q.queueToString())
console.log(q.front(), q.back())
q.dequeue();
console.log(q.front(), q.back())

栈

'use strict';

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

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

function pop() {
  const item = this.dataStore[this.top-- - 1];
  this.dataStore.splice(this.top, 1);

  return item;
};

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

function length() {
  return this.top;
};

function clear() {
  this.dataStore.splice(0, this.top);
  this.top = 0;
}

function empty() {
  if (this.top === 0) return true;
  return false;
};

function mulBase(num, base) {
  let s = new Stack();
  if (num < base) return num;
  let tmp = num;
  while (tmp / base >= 1) {
    s.push(tmp % base);
    tmp = parseInt(tmp / base, 10);
  }
  s.push(1);
  let converted = '';
  while (s.length() > 0) {
    converted += s.pop();
  }

  return converted;
}

console.log(mulBase(17, 2))

function Queue(stack1, stack2) {
  this.tailStack = stack1;
  this.headStack = stack2;
  this.enqueue = enqueue;
  this.dequeue = dequeue;
  this.queueToString = queueToString;
  this.empty = queueEmpty;
}

function enqueue(element) {
  this.tailStack.push(element);
}
function dequeue() {
  if (this.headStack.empty()) {
    while (!this.tailStack.empty()) {
      this.headStack.push(this.tailStack.pop());
    }
  }
  return this.headStack.pop();
}
function queueToString() {
  if (this.empty()) return '';
  let str = '';
  if (!this.headStack.empty()) {
    let i = this.headStack.top - 1;
    while (i >= 0) {
      str += this.headStack.dataStore[i--] + ' ';
    }
  }
  if (!this.tailStack.empty()) {
    let i = 0;
    while (i < this.tailStack.top) {
      str += this.tailStack.dataStore[i++] + ' ';
    }
  }

  return str;
}
function queueEmpty() {
  if (this.tailStack.empty() && this.headStack.empty()) return true;
  return false;
}
const s1 = new Stack();
const s2 = new Stack();
const q = new Queue(s1, s2);

console.log(q.empty());
q.enqueue('a');
q.enqueue('b');
q.enqueue('c');
q.enqueue('d');
console.log(q.queueToString());
q.dequeue();
console.log(q.queueToString());
q.dequeue();
console.log(q.queueToString());
console.log(q.empty());