JavaScript 数据结构：栈和队列
原创
上周小编已经介绍了什么是数据结构，没看过的同学，可以点击《JavaScript 数据结构：什么是数据结构》，今天小编会和大家一起学习栈和队列。
Web开发中最常用的两种数据结构是栈和队列，真正理解和灵活使用的开发人员并不多。如果你是开发人员，这两个场景一定不陌生：文本编辑器的“撤销”操作是用栈组织数据；点击事件，就是用队列组织数据。
现在回想起来，这些结构我们早已用过，只是我们不太在意而已 ，作为开发者我们有多少次使用栈和队列？由于他们在设计中的普遍性和相似性，我们有必要深入理解。（文末有彩蛋，一定要看完哦）
栈
栈是一种高效的数据结构，因为数据只能在栈顶添加或删除，所以这样的操作很快，而且容易实现。栈的使用遍布程序语言实现的方方面面。
一摞盘子是现实中最常见例子：只能从最上面取盘子，盘子洗净后，也只能摞在这一摞盘子的最上面。栈被称为一种后入先出（LIFO,last-in-first-out）的数据结构。
为了提供一个更具技术性的堆栈示例，让我们一起回顾下文本编辑器的“撤销”操作。每次添加文本就会添加至文末，即压入堆栈底部（push()）。最近的更改代表栈的顶部(peek())，如果用户想撤销最近的更改，堆栈的顶部将被删除，这个过程可以反复撤销(pop())，直到撤销成一个空白的文件！
如图所示，更能方便大家理解栈：
入栈（push）：将数据保存到栈顶！
出栈（pop）：将栈顶的数据弹出的操作。
定义Stack类的构造函数
我们用数组 dataStore保存栈内元素，构造函数将其初始化为一个空数组。变量 top记录栈顶位置，被构造函数初始化为 0，表示栈顶对应数组的起始位置 0。如果有元素被压入栈，该变量的值将随之变化。
function Stack()
{
this.dataStore=[];
this.top =0;
this.push =push;
this.pop =pop;
this.peek=peek;
this.length=length;
}定义PUSH方法
当向栈中压入一个新元素时，需要将其保存在数组中变量 top所对应的位置，然后将 top值加 1，让其指向数组中下一个空位置。代码如下所示：
function push(element)
{
this. dataStore[this.top++]=element;
}定义pop方法
pop()方法恰好与 push()方法相反——它返回栈顶元素，同时将变量 top的值减 1：
function pop()
{
return this.dataStore[--this.top];
}定义peek方法
peek()方法返回数组的第 top-1个位置的元素，即栈顶元素：
function peek()
{
return this.dataStore[this. top-1];
}定义length方法
有时候需要知道栈内存储了多少个元素。 length()方法通过返回变量 top值的方式返回栈内的元素个数：
function length()
{
return this.top;
}定义clear方法
最后，可以将变量 top的值设为 0，轻松清空一个栈：
function clear() {
this. top = 0;
}完整的Stack类
function Stack()
{
this.dataStore=[];
this.top =0;
this.push =push;
this.pop =pop;
this.peek=peek;
this.length=length;
}
function push(element)
{
this. dataStore[this.top++]=element;
}
function pop()
{
return this.dataStore[--this.top];
}
function peek()
{
return this.dataStore[this. top-1];
}
function length()
{
return this.top;
}
function clear() {
this.top=0;
}队列
类似堆栈，队列是线性数据结构。与堆栈不同，队列只会删除最早添加的数据。
队列是一种列表，不同的是队列只能在队尾插入元素，在队首删除元素。队列用于存储按顺序排列的数据，先进先出，这点和栈不一样，在栈中，最后入栈的元素反而被优先处理。可以将队列想象成在银行前排队的人群，排在最前面的人第一个办理业务，新来的人只能在后面排队，直到轮到他们为止。
队列是一种先进先出（ First-In-First-Out， FIFO）的数据结构。队列被用在很多地方，比如提交操作系统执行的一系列进程、打印任务池等，一些仿真系统用队列来模拟银行或杂货店里排队的顾客。
如下图所示，很直观的展示了什么是队列：
队列的两种主要操作是：向队列中插入新元素和删除队列中的元素。插入操作也叫做入队，删除操作也叫做出队。入队操作在队尾插入新元素，出队操作删除队头的元素。
定义Queue构造函数
function Queue()
{
this.dataStore=[];
this.enqueue=enqueue;
this.dequeue=dequeue;
this.front=front;
this.back=back;
this.toString=toString;
this.empty = empty;
}添加元素
Enqueue，向队尾添加一个元素
function enqueue(element)
{
this. dataStore.push( element);
}删除元素
dequeue,删除队首的元素
function dequeue(){
return this.dataStore. shift();
}读取队首和队尾的元素
function front()
{
return this.dataStore[0];
}
function back()
{
return this.dataStore[this.dataStore.length-1];
}判断队列是否为空
function empty(){
if (this.dataStore.length==0)
{
return true;
}
else
{
return false;
}
}完整的Queue类
function Queue()
{
this.dataStore=[];
this.enqueue=enqueue;
this.dequeue=dequeue;
this.front=front;
this.back=back;
this.toString=toString;
this.empty = empty;
}
function enqueue(element)
{
this. dataStore.push(element);
}
function dequeue(){
return this.dataStore. shift();
}
function front()
{
return this.dataStore[0];
}
function back()
{
return this.dataStore[this.dataStore.length-1];
}
function toString() {
var retStr = "";
for (var i = 0; i < this. dataStore. length; ++ i) {
retStr += this. dataStore[ i] + "\n"; }
return retStr;
}
function empty(){
if (this.dataStore.length==0)
{
return true;
}
else
{
return false;
}
}小节
今天小编和大家一起探索了两种线性数据结构：堆栈和队列。堆栈按顺序存储数据并删除最近添加的数据；队列按顺序存储数据，但删除最早添加的数据。堆栈与队列我们会经常遇到，如果需要按顺序组织数据，请优先考虑使用堆栈和队列。
《TypeScript High Performance》
关注本公众号，回复"原版英文电子书"，进行下载
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。