数据结构

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。

栈

简介

栈是一种遵从后进先出（LIFO）原则的有序集合。

栈的方法

1
2
3
4
5
6
push(element(s))      添加一个（或多个）新元素到栈顶
pop()                 移除栈顶的元素，同时返回栈顶元素
peek()                返回栈顶元素，不对栈做任何修改
isEmpty()             判断栈里有无元素
clear()               移除栈里的所有元素
size()                返回栈里的元素个数

栈的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
function Stack() {
  var items = []

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

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

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

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

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

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

  this.print = function() {
    console.log(items.toString())
  }
}

栈的使用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//进制转换
function baseConverter(decNumber, base) {
  var remStack = new Stack(),
    rem,
    baseString = '',
    digits = '0123456789ABCDEF'
  while (decNumber > 0) {
    rem = Math.floor(decNumber % base)
    remStack.push(rem)
    decNumber = Math.floor(decNumber / base)
  }

  while (!remStack.isEmpty()) {
    baseString += digits[remStack.pop()]
  }

  return baseString
}

//baseConverter(100345, 2) --> 1100001111111001
//baseConverter(100345, 8) --> 303771
//baseConverter(100345, 16) --> 187F9

队列

简介

队列是遵循先进先出（FIFO）原则的一组有序的项

队列的方法

1
2
3
4
5
6
enqueue(element(s))     向队列尾部添加一个（或多个）新的项
dequeue()               移除队列第一项，并返回被移除的元素
front()                 返回队列第一项，队列不做任何修改
isEmpty()               判断队列是否为空
clear()                 清空队列
size()                  返回队列元素个数

队列的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
function Queue() {
  var items = []

  this.enqueue = function(element) {
    items.pop(element)
  }

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

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

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

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

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

  this.print = function() {
    console.log(items.toString())
  }
}

设置队列优先级

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
//最小优先队列
function PriorityQueue() {
  var items = []

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

  this.enqueue = function(element, priority) {
    var queueElement = new QueueElement(element, priority)
    if (this.isEmpty()) {
      items.push(queueElement)
    } else {
      var added = false
      for (var i = 0; i < items.length; i++) {
        if (queueElement.priority < items[i].priority) {
          items.splice(i, 0, queueElement)
          added = true
          break
        }
      }
    }
    if (!added) {
      items.push(queueElement)
    }
  }
}

链表

简介

链表是一种物理存储单元上非连续、非顺序的存储结构

链表方法

1
2
3
4
5
6
7
8
append(element)                 向链表尾部添加一项
insert(position, element)       向链表指定位置添加一项
remove(element)                 移除一项
indexOf(element)                返回元素在链表中的位置，没有则返回-1
removeAt(position)              特定位置移除一项
isEmpty()                       链表是否为空
size()                          链表长度
toString()                      输出元素的值

链表的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
function LinkedList(){
  var Node = function(element){
    this.element = element;
    this.next = null;
  }

  var length = 0;
  var head = null;

  this.append = function(element){
    var node = new Node(element),
        current;

    if(head === null){
      head = node;
    }else{
      current = head;
      while (current.next) {
        current = current.next;
      }
      current.next = node;
    }
    length++;
  };

  this.removeAt = function(position){
    if(position > -1 && position < length){
      var current = head,
          previous,
          index = 0;
      if(position ==== 0){
          head = current.next;
      }else{
        while(index++ < position){
          previous = current;
          current = current.next;
        }
        //此处要跳过current，从而移除它
        previous.next = current.next;
      }
      length--;
      return current.element;
    }else{
      return null;
    }
  };

  this.insert = function(position, element){
    if(position >= 0 && position <= length){
      var node = new Node(element),
          current = head,
          previous,
          index = 0;

      if(position === 0){
        node.next = current;
        head = node;
      }else{
        while (index++ < position) {
          previous = current;
          current = current.next;
        }
        node.next = current;
        previous.next = node;
      }
      length++;
      return true;
    }else{
      return false;
    }
  };

  this.toString = function(){
    var current = head,
        str = '';
    while (current) {
      string += ',' + current.element;
      current = current.next;
    }
    return str.slice(1);
  };

  this.indexOf = function(){
    var current = head,
        index = 0;
    while(current){
      if(element === current.element){
        return index++;
      }
      index++;
      current = current.next;
    }
    return -1;
  };

  this.remove = function(element){
    var index = this.indexOf(element);
    return this.removeAt(index);
  };

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

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

  this.getHead = function(){
    return head;
  }
}
0%