JavaScript 数据结构:栈和队列

上周小编已经介绍了什么是数据结构,没看过的同学,可以点击

《JavaScript 数据结构:什么是数据结构》

,今天小编会和大家一起学习栈和队列。

Web开发中最常用的两种数据结构是栈和队列,真正理解和灵活使用的开发人员并不多。如果你是开发人员,这两个场景一定不陌生:文本编辑器的“撤销”操作是用栈组织数据;点击事件,就是用队列组织数据。

现在回想起来,这些结构我们早已用过,只是我们不太在意而已 ,作为开发者我们有多少次使用栈和队列?由于他们在设计中的普遍性和相似性,我们有必要深入理解。(文末有彩蛋,一定要看完哦)

栈是一种高效的数据结构,因为数据只能在栈顶添加或删除,所以这样的操作很快,而且容易实现。栈的使用遍布程序语言实现的方方面面。

一摞盘子是现实中最常见例子:只能从最上面取盘子,盘子洗净后,也只能摞在这一摞盘子的最上面。栈被称为一种后入先出(LIFO,last-in-first-out)的数据结构。

为了提供一个更具技术性的堆栈示例,让我们一起回顾下文本编辑器的“撤销”操作。每次添加文本就会添加至文末,即压入堆栈底部(push())。最近的更改代表栈的顶部(peek()),如果用户想撤销最近的更改,堆栈的顶部将被删除,这个过程可以反复撤销(pop()),直到撤销成一个空白的文件!

如图所示,更能方便大家理解栈:

入栈(push):将数据保存到栈顶!

出栈(pop):将栈顶的数据弹出的操作。

定义Stack类的构造函数

我们用数组 dataStore保存栈内元素,构造函数将其初始化为一个空数组。变量 top记录栈顶位置,被构造函数初始化为 0,表示栈顶对应数组的起始位置 0。如果有元素被压入栈,该变量的值将随之变化。

functionStack()

{

this.dataStore=[];

this.top=;

this.push=push;

this.pop=pop;

this.peek=peek;

this.length=length;

}

定义PUSH方法

当向栈中压入一个新元素时,需要将其保存在数组中变量 top所对应的位置,然后将 top值加 1,让其指向数组中下一个空位置。代码如下所示:

functionpush(element)

{

this.dataStore[this.top++]=element;

}

定义pop方法

pop()方法恰好与 push()方法相反——它返回栈顶元素,同时将变量 top的值减 1:

functionpop()

{

return this.dataStore[--this.top];

}

定义peek方法

peek()方法返回数组的第 top-1个位置的元素,即栈顶元素:

functionpeek()

{

return this.dataStore[this.top-1];

}

定义length方法

有时候需要知道栈内存储了多少个元素。 length()方法通过返回变量 top值的方式返回栈内的元素个数:

functionlength()

{

return this.top;

}

定义clear方法

最后,可以将变量 top的值设为 0,轻松清空一个栈:

functionclear() {

this.top=;

}

完整的Stack类

functionStack()

{

this.dataStore=[];

this.top=;

this.push=push;

this.pop=pop;

this.peek=peek;

this.length=length;

}

functionpush(element)

{

this.dataStore[this.top++]=element;

}

functionpop()

{

return this.dataStore[--this.top];

}

functionpeek()

{

return this.dataStore[this.top-1];

}

functionlength()

{

return this.top;

}

functionclear() {

this.top=;

}

队列

类似堆栈,队列是线性数据结构。与堆栈不同,队列只会删除最早添加的数据。

队列是一种列表,不同的是队列只能在队尾插入元素,在队首删除元素。队列用于存储按顺序排列的数据,先进先出,这点和栈不一样,在栈中,最后入栈的元素反而被优先处理。可以将队列想象成在银行前排队的人群,排在最前面的人第一个办理业务,新来的人只能在后面排队,直到轮到他们为止。

队列是一种先进先出( First-In-First-Out, FIFO)的数据结构。队列被用在很多地方,比如提交操作系统执行的一系列进程、打印任务池等,一些仿真系统用队列来模拟银行或杂货店里排队的顾客。

如下图所示,很直观的展示了什么是队列:

队列的两种主要操作是:向队列中插入新元素和删除队列中的元素。插入操作也叫做入队,删除操作也叫做出队。入队操作在队尾插入新元素,出队操作删除队头的元素。

定义Queue构造函数

functionQueue()

{

this.dataStore=[];

this.enqueue=enqueue;

this.dequeue=dequeue;

this.front=front;

this.back=back;

this.toString=toString;

this.empty=empty;

}

添加元素

Enqueue,向队尾添加一个元素

functionenqueue(element)

{

this.dataStore.push(element);

}

删除元素

dequeue,删除队首的元素

functiondequeue(){

return this.dataStore.shift();

}

读取队首和队尾的元素

functionfront()

{

return this.dataStore[];

}

functionback()

{

return this.dataStore[this.dataStore.length-1];

}

判断队列是否为空

functionempty(){

if(this.dataStore.length==)

{

return true;

}

else

{

return false;

}

}

完整的Queue类

functionQueue()

{

this.dataStore=[];

this.enqueue=enqueue;

this.dequeue=dequeue;

this.front=front;

this.back=back;

this.toString=toString;

this.empty=empty;

}

functionenqueue(element)

{

this.dataStore.push(element);

}

functiondequeue(){

return this.dataStore.shift();

}

functionfront()

{

return this.dataStore[];

}

functionback()

{

return this.dataStore[this.dataStore.length-1];

}

functiontoString() {

varretStr="";

for(vari=;i

retStr+=this.dataStore[i] +"\n"; }

returnretStr;

}

functionempty(){

if(this.dataStore.length==)

{

return true;

}

else

{

return false;

}

}

今天小编和大家一起探索了两种线性数据结构:堆栈和队列。堆栈按顺序存储数据并删除最近添加的数据;队列按顺序存储数据,但删除最早添加的数据。堆栈与队列我们会经常遇到,如果需要按顺序组织数据,请优先考虑使用堆栈和队列。

《TypeScript High Performance》

关注本公众号,回复"原版英文电子书",进行下载

公众号

前端达人

长按识别左边二维码关注我

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180610G17T4E00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。

扫码关注云+社区

领取腾讯云代金券