JavaScript数组、栈、队列数据结构实现教程

JavaScript数据结构实战：数组、栈与队列的实现详解

前言

所谓数据结构，本质上是指数据元素之间存在的一种或多种特定关系的集合。

常见的数据结构类型包括：

数组、队列（queue）、堆（heap）、栈（stack）、链表（linked list）、树（tree）、图（graph）以及散列表（hash）。

本文将重点介绍数组、栈和队列这三种基础数据结构，并展开详细讨论。

数组操作详解

一、数组

数组是日常开发中使用频率最高的数据结构。在JavaScript中，数组的大小是动态分配的。本文不会罗列JavaScript数组的所有内置方法，而是聚焦于数据结构视角下常用的操作方法。

创建和初始化数组


//创建空数组
var array = new Array();
//[]
//初始化数组
var array = new Array(1,2,3);
var array = Array.of(1,2,3);//ES6的方法
//[1,2,3]
//创建大小为5的数组
var array = new Array();//ES6的方法
//[undefined,undefined,undefined,undefined,undefined]
//给数组赋值
var array = new Array();
array[0] = 1 ;
array[1] = 2 ;
array[2] = 3 ;
//[1,2,3]

添加元素

向数组末尾添加元素


var number = [1,2,3];
number[number.length] = 4;
//[1,2,3,4]
//或者
var number = [1,2,3];
number.push(4);
//[1,2,3,4]

向数组开头添加元素


var number = [1,2,3];
number.unshift(0);
//[0,1,2,3]
number.unshift(-2,-1);
//[-2,-1,0,1,2,3]

在数组的任意指定位置插入元素

利用splice方法进行插入


//在索引1后面添加2，3，4
var number = [1,5,6];
number.splice(1,0,2,3,4);
//[1,2,3,4,5,6]

删除元素

删除数组第一个元素


var number = [1,2,3];
number.shift();
//[2,3]

删除数组中任意位置的元素

使用splice方法删除指定位置的元素


var numebr = [1,2,3,4,5,6];
//如果想删除元素3
number.splice(2,1);
//[1,2,4,5,6]
//如果想删除元素4，5
number.splice(3,2);

排序操作

数组反序


var number = [3,2,1];
number.reverse();
//[1,2,3]

自然排序


var numebr = [2,3,4,1,3,7];
number.sort();
//[1,2,3,3,4,7]

自定义排序逻辑

这种自定义排序的逻辑类似于Java中实现comparator接口，应用场景非常广泛。


var number = [4,5,6,7,1,2,3,8,9,10,11,12,13];
number.sort();
//[1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]

直接进行自然排序可能会出现不符合预期的结果，例如期望得到[1,2,3,4,5,6,7,8,9,10,11,12,13]，此时就需要通过自定义排序函数来解决该问题。


var number = [4,5,6,7,1,2,3,8,9,10,11,12,13];
function compare(a,b){
 if(a < b){
 return -1;
 }
 if(a > b){
 return 1;
 }
 return 0;
}
number.sort(compare);
//[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13]

除了基础类型，还可以对任意对象类型的数组进行排序。例如，假设有一个包含名字和年龄属性的Person对象数组，我们可能希望根据年龄字段进行排序。


var friends = [{name:'李晨',age:40},{name:'范冰冰',age:35}];
function comparePerson(a,b){
 if(a.age < b.age){
 return -1;
 }
 if(a.age > b.age){
 return 1;
 }
 return 0;
}
friends.sort(comparePerson);
//[{name:'范冰冰',age:35},{name:'李晨',age:40}]

搜索操作

搜索主要涉及两个方法：indexOf方法返回与参数匹配的第一个元素的索引，而lastIndexOf方法返回与参数匹配的最后一个元素的索引。


var number = [1,3,4,3,56,6,7,4];
number.indexOf(3);//1
number.lastIndexOf(3)//3

栈的实现原理

二、栈

栈是一种遵循后进先出（LIFO）原则的有序集合。新添加或待删除的元素都保存在栈的末尾，称为栈顶；另一端称为栈底。在栈结构中，新元素靠近栈顶，旧元素接近栈底。在JavaScript中，变量保存和函数调用均使用栈机制进行存储。

首先，我们需要创建一个类来表示栈，并选择一种数据结构来存储栈内元素。这里我们选用之前介绍的数组：var items = [];。接下来，为栈声明以下核心方法：

push(elements(s))：向栈顶添加一个或多个新元素
pop()：移除栈顶元素，并返回被移除的元素值
peek()：获取栈顶元素，但不修改栈的状态
isEmpty()：如果栈内没有元素则返回true，否则返回false
clear()：清空栈中的所有元素
size() ：返回栈中元素的总个数

如果仔细阅读了上一节关于数组的内容，那么使用JavaScript实现一个栈将变得非常简单。此处直接展示完整代码，不再对每个方法进行单独解释。


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 = funciton(){
 console.log(items.toString());
 }
}

队列与优先队列构建

三、队列

队列是一组遵循先来先服务（FIFO）原则的有序项。元素在队列尾部添加，并从顶部移除。最新添加的元素位于队列末尾。

在现实生活中，排队是常见的例子。在计算机科学中，打印队列是一个典型应用：先点击打印的文档会优先被打印。

创建队列

同样，我们先创建一个类来表示队列。所需的数据结构依然是数组，声明为var items = []。

声明队列可用的操作方法：

enqueue(element(s))：向队尾添加一个或多个新项
dequeue()：移除队列中第一个（即最前端）的元素，并返回被移除的元素
front()：返回队列中的第一个元素
isEmpty() ：如果队列中不包含元素则返回true，否则返回false
size()：返回队列中包含元素的个数

完整的Queue类实现


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.clear = function(){
 items = [];
 }
 this.size = funciton(){
 return items.length;
 }
 this.print = function(){
 console.log(items.toString());
 }
}

优先队列

在优先队列中，每个元素都被赋予优先级。访问元素时，具有最高优先级的元素会被优先删除。优先队列表现出最高进先出的行为特征。例如，医院急救室为病人赋予优先级（基于病情严重程度），具有最高优先级的病人会最先得到治疗。

实现优先队列主要有两种方案：

设置优先级，并在添加元素时将其放置在正确的位置；
通过入列操作添加元素，然后按照优先级顺序移除它们。

本文采用第一种方案进行实现。


function PriorityQueue(){
 var items = [];
 funciton QueueElement(element,priority){
 this.element = element;
 this.priority = priority;
 }
 function comparePriority(a,b){
 if(a.priority > b.priority){
  return 1;
 }
 if(a.priority < b.priority){
  return -1;
 }
 return 0;
 }
 this.enqueue = funciton(element,priority){
 var queueElement = new QueueElement(element,priority);
 items.push(queueElement);
 items.sort(comparePriority);
 }
 //其它方法和默认的Queue实现相同
}

当然，enqueue方法的实现方式多种多样，本文提供的方案效率并非最高，但易于理解。其核心逻辑是将插入的元素根据优先级进行排序，从而确保高优先级的元素先被移除。

总结

以上就是本文的全部内容，希望这些内容能对您的学习或工作有所帮助。如有疑问，欢迎留言交流，感谢大家对本站的支持。

JavaScript数据结构实战：数组、栈与队列的实现详解

JavaScript数据结构实战：数组、栈与队列的实现详解

数组操作详解

栈的实现原理

队列与优先队列构建

实用工具推荐