快捷導(dǎo)航

JavaScript數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)之數(shù)組、棧與隊列

更新時間：2017年05月02日 10:27:52 投稿：daisy

這篇文章主要給大家介紹了JavaScript數(shù)據(jù)結(jié)構(gòu)之數(shù)組、棧與隊列的相關(guān)資料，文中對數(shù)組、棧與隊列的使用方法進行了詳細的總結(jié)，相信對大家具有一定的參考學(xué)習(xí)價值，需要的朋友們下面來一起看看吧。

前言

數(shù)據(jù)結(jié)構(gòu)就是關(guān)系，沒錯，就是數(shù)據(jù)元素相互之間存在的一種或多種特定關(guān)系的集合。

常用的數(shù)據(jù)結(jié)構(gòu)有：

數(shù)組，隊列（queue），堆（heap）,棧（stack），鏈表（linked list ），樹（tree），圖（graph）和散列表（hash）

本文主要介紹的是數(shù)組、棧與隊列，下面來一起看看詳細的介紹吧。

一、數(shù)組

數(shù)組是平時使用最常用的數(shù)據(jù)結(jié)構(gòu)，在JavaScript中數(shù)組是動態(tài)的分配大小,在這里我不會介紹JavaScript里面數(shù)組的所有的方法，而是針對數(shù)據(jù)結(jié)構(gòu)這個方向談?wù)勊玫降姆椒ā?/p>

創(chuàng)建和初始化數(shù)組

//創(chuàng)建空數(shù)組
var array = new Array();
//[]
//初始化數(shù)組
var array = new Array(1,2,3);
var array = Array.of(1,2,3);//ES6的方法
//[1,2,3]
//創(chuàng)建大小為5的數(shù)組
var array = new Array();//ES6的方法
//[undefined,undefined,undefined,undefined,undefined]
//給數(shù)組賦值
var array = new Array();
array[0] = 1 ;
array[1] = 2 ;
array[2] = 3 ;
//[1,2,3]

添加元素

往數(shù)組后添加元素

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]

往數(shù)組前面添加元素

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

往數(shù)組的任意位置插入元素

運用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方法刪除數(shù)組任意位置的元素

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里面實現(xiàn)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]

仿佛看起有點不對啊，我們應(yīng)該想要的是
[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]

這還只是最簡單的，也可以對任何對象類型進行數(shù)組排序。例如，對象Person有名字和年齡屬性，我們希望根據(jù)年齡排序

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方法返回與參數(shù)匹配的第一個元素的索引，lastIndexOf返回與參數(shù)匹配的最后一個元素的索引。

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

二、棧

棧是一種遵循后進先出(LIFO)原則的有序集合。新添加的或待刪除的元素都保存在棧的末尾，稱作棧頂，另一端就叫棧底。在棧里，新元素都靠近棧頂，舊元素都接近棧底。在JavaScript中變量保存和函數(shù)調(diào)用都是用棧存儲的。

首先創(chuàng)建一個類來表示一個棧，需要一種數(shù)據(jù)結(jié)構(gòu)來保存棧里的元素。這里我們就選擇剛學(xué)的數(shù)組：var items = [];
接下來，為我們的棧聲明一些方法：

push(elements(s)) :添加一個（或幾個）新元素到棧頂
pop() :移除棧頂?shù)脑?，同時返回被移除的元素
peek() :獲取棧頂?shù)脑?，不對棧做出任何修?/li>
isEmpty() :如果棧里沒有任何元素就返回true,否則返回false；
clear() :清空棧
size() :返回棧元素的個數(shù)

如果上一節(jié)數(shù)組認真看了，我相信用JavaScript實現(xiàn)一個棧是非常簡單的。在這里就直接來代碼了，不用一個方法一個方法去解釋了。

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());
 }
}

三、隊列

隊列是遵循先來先服務(wù)(FIFO)原則的一組有序的項。隊列在尾部添加新元素，并從頂部移除元素。最新添加的元素排在隊列的末尾。

在現(xiàn)實生活中常見的例子就是排隊。
在計算機科學(xué)中，一個常見的例子就是打印隊列，先點擊打印的文檔會被先打印。

創(chuàng)建隊列

同樣先創(chuàng)建一個類來表示一個隊列。需要用到的數(shù)據(jù)結(jié)構(gòu)同樣是數(shù)組var items = [];

聲明可用的方法：

enqueue(element(s)) :向隊尾添加一個（或多個）新的項
dequeue() :移除隊列的第一（即排在隊列最前面的）項，并返回被移除的元素。
front() :返回隊列中第一個元素
isEmpty() :如果隊列中不包含元素返回true，否則返回false
size() :返回隊列包含元素的個數(shù)

完整的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());
 }
}

優(yōu)先隊列

在優(yōu)先隊列中，元素被賦予優(yōu)先級。當訪問元素的時，具有最高優(yōu)先級的元素先刪除。優(yōu)先隊列具有最高進先出的行為特征。例如：醫(yī)院的急救室為病人賦予優(yōu)先級（這個優(yōu)先級可以指病情嚴重的成程度），具有最高優(yōu)先級的病人最先得到治療。

實現(xiàn)一個優(yōu)先隊列有兩種選項：

設(shè)置優(yōu)先級，然后在正確的位置添加元素；
用入列操作添加元素，然后按照優(yōu)先級移除它們。

我們這里采用第一種。

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實現(xiàn)相同
}

當然，這個enqueue的實現(xiàn)方法很多種，我這效率不是最高的，但是容易理解。將插入的元素根據(jù)優(yōu)先級排個序，那么先出去的就是優(yōu)先級最高的了。

總結(jié)

以上就是這篇文章的全部內(nèi)容了，希望本文的內(nèi)容對大家的學(xué)習(xí)或者工作能帶來一定的幫助，如果有疑問大家可以留言交流，謝謝大家對腳本之家的支持。

您可能感興趣的文章: