JavaScript中的数据结构：栈、队列和链表的实现及应用

翻滚的胖子
2023-06-20 10:08:06
JavaScript Java

本文将介绍JavaScript中的数据结构——栈、队列和链表的实现及应用，通过详细讲解函数、函数细节、用法及代码案例，帮助编程小白轻松学习。

栈

栈是一种先进后出（Last In First Out，LIFO）的数据结构，可以通过数组实现。
以下是一个栈的构造函数：

function Stack() {
  var items = [];
  
  this.push = function(element) {
    items.push(element);
  };
  
  this.pop = function() {
    return items.pop();
  };
  
  this.peek = function() {
    return items[items.length - 1];
  };
  
  this.isEmpty = function() {
    return items.length == 0;
  };
  
  this.size = function() {
    return items.length;
  };
  
  this.clear = function() {
    items = [];
  };
  
  this.print = function() {
    console.log(items.toString());
  };
}

该构造函数中实现了以下方法：

push(element)：添加一个（或多个）新元素到栈顶。
pop()：移除栈顶的元素，同时返回被移除的元素。
peek()：返回栈顶的元素，不对栈做任何修改（这个方法不会移除栈顶的元素，仅仅返回它）。
isEmpty()：如果栈里没有任何元素就返回true，否则返回false。
size()：返回栈里的元素个数。这个方法和数组的length属性很类似。
clear()：移除栈里的所有元素。
print()：打印栈里的所有元素。

下面是一个栈的使用示例：

var stack = new Stack();

console.log(stack.isEmpty()); // 输出true

stack.push(5);
stack.push(8);

console.log(stack.peek()); // 输出8

stack.push(11);
console.log(stack.size()); // 输出3
console.log(stack.isEmpty()); // 输出false

stack.push(15);

stack.pop();
stack.pop();

console.log(stack.size()); // 输出2
stack.print(); // 输出5, 8

队列

队列是一种先进先出（First In First Out，FIFO）的数据结构，同样可以通过数组实现。
以下是一个队列的构造函数：

function Queue() {
  var items = [];
  
  this.enqueue = function(element) {
    items.push(element);
  };
  
  this.dequeue = function() {
    return items.shift();
  };
  
  this.front = function() {
    return items[0];
  };
  
  this.isEmpty = function() {
    return items.length == 0;
  };
  
  this.size = function() {
    return items.length;
  };
  
  this.print = function() {
    console.log(items.toString());
  };
}

该构造函数中实现了以下方法：

enqueue(element)：向队列尾部添加一个（或多个）新的项。
dequeue()：移除队列的第一（即排在队列最前面的）项，并返回被移除的元素。
front()：返回队列中第一个元素——最先被添加，也将是最先被移除的元素。队列不做任何变动（不移除元素，只返回元素信息——与Stack类的peek方法非常类似）。
isEmpty()：如果队列中不包含任何元素，返回true，否则返回false。
size()：返回队列包含的元素个数，与数组的length属性类似。
print()：打印队列里的所有元素。

下面是一个队列的使用示例：

var queue = new Queue();

console.log(queue.isEmpty()); // 输出true

queue.enqueue('John');
queue.enqueue('Jack');

queue.print(); // 输出John,Jack
console.log(queue.size()); // 输出2
console.log(queue.isEmpty()); // 输出false

queue.dequeue();
queue.dequeue();

console.log(queue.isEmpty()); // 输出true

链表

链表是一种由一组节点组成的集合，每个节点都使用一个对象的引用指向它的后继。链表分为单向链表、双向链表和循环链表三种类型。
以下是一个单向链表的构造函数：

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);
    var current = null;
    
    if (head == null) {
      head = node;
    } else {
      current = head;
      while (current.next) {
        current = current.next;
      }
      current.next = node;
    }
    length++;
  };
  
  this.insert = function(position, element) {
    if (position >= 0 && position <= length) {
      var node = new Node(element);
      var current = head;
      var previous = null;
      var 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.removeAt = function(position) {
    if (position > -1 && position < length) {
      var current = head;
      var previous = null;
      var index = 0;
      
      if (position == 0) {
        head = current.next;
      } else {
        while (index++ < position) {
          previous = current;
          current = current.next;
        }
        previous.next = current.next;
      }
      length--;
      return current.element;
    } else {
      return null;
    }
  };
  
  this.remove = function(element) {
    var index = this.indexOf(element);
    return this.removeAt(index);
  };
  
  this.indexOf = function(element) {
    var current = head;
    var index = 0;
    
    while (current) {
      if (element === current.element) {
        return index;
      }
      index++;
      current = current.next;
    }
    return -1;
  };
  
  this.isEmpty = function() {
    return length == 0;
  };
  
  this.size = function() {
    return length;
  };
  
  this.getHead = function() {
    return head;
  };
  
  this.toString = function() {
    var current = head;
    var string = '';
    
    while (current) {
      string += current.element + (current.next ? '
' : '');
      current = current.next;
    }
    return string;
  };
  
  this.print = function() {
    console.log(this.toString());
  };
}

该构造函数中实现了以下方法：

append(element)：向链表尾部添加一个新元素。
insert(position, element)：向链表的特定位置插入一个新元素。
removeAt(position)：从链表的特定位置移除一项。
remove(element)：从链表中移除一项。
indexOf(element)：返回元素在链表中的索引。如果链表中没有该元素则返回-1。
isEmpty()：如果链表中不包含任何元素，返回true，否则返回false。
size()：返回链表包含的元素个数。
getHead()：返回链表的头部。
toString()：由于列表项使用了Node类，就需要重写继承自JavaScript对象默认的toString方法，让其只输出元素的值。
print()：打印链表里的所有元素。

下面是一个链表的使用示例：

var list = new LinkedList();
list.append(15);
list.append(10);

console.log(list.indexOf(10)); // 输出1
console.log(list.indexOf(15)); // 输出0
console.log(list.indexOf(13)); // 输出-1

list.insert(1, 13);
console.log(list.toString()); // 输出15
13
10

list.removeAt(1);
console.log(list.toString()); // 输出15
10

本文为翻滚的胖子原创文章,转载无需和我联系,但请注明来自猿教程iskeys.com