JS数据结构与算法 — 栈与队列
栈与队列分别是两种数据结构，不同语言对于栈和队列有着不同的声明 栈数据结构的特点是 FILO（first in last out） 即先进后出，队列则是 FIFO（first in first out）即先进先出。 1. 数据结构【栈】介绍
其实非常好理解，我们将栈可以看成一个箱子
- 往箱子里面放东西叫做入栈
- 往箱子里面取东西叫做出栈
- 箱子的底部叫做栈底
- 箱子的顶部叫做栈顶
说到栈的特性，肯定会有一句经典的言语来概括：先进后出(LIFO, Last In First Out)
- 往箱子里边放苹果，箱子底部的苹果想要拿出来，得先把箱子顶部的苹果取走才行
2. 数据结构【栈】 代码实现 栈的分类有两种：
- 静态栈(数组实现)
- 动态栈(链表实现)
下面来看看静态栈的实现 首先我们先创建一个类：
function Stack(){
//各种属性和方法的声明
}然后我们需要一种数据结构来保存栈里面的数据：
var items=[];接下来，我们需要给栈声明一些方法：
- push(element):添加一个或是几个新元素到栈顶。
- pop():移除栈顶的元素，同时返回被移除元素。
- peek():返回栈顶的元素，但并不对栈顶的元素做出任何的修改。
- isEmpty():检查栈内是否有元素，如果有返回true，没有返回false。
- clear():清除栈里的元素。
- size():返回栈的元素个数。
- print():打印栈里的元素。
栈的完整代码 我们通过javascript提供的API，实现栈如下：
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());
};
this.toString = function(){
return items.toString();
};
}使用栈 创建完了栈，也给他了方法，然后我们来实例化一个对象：
console.log(stack.isEmpty());
//true
stack.push(1);
stack.push(3);
//添加元素
console.log(stack.peek());
//输出栈顶元素3
console.log(stack.size());
//2
//输出元素个数3. 数据结构【队列】
数据结构的队列长的是这个样子：
其实队列非常好理解，我们将队列可以看成小朋友排队
- 队尾的小朋友到指定的地点了-->出队
- 有新的小朋友加入了-->入队
相对于栈而言，队列的特性是：先进先出
- 先排队的小朋友肯定能先打到饭！
队列也分成两种：
- 静态队列(数组实现)
- 动态队列(链表实现)
这次我就使用数组来实现静态队列了 队列的创建 首先我们声明一个类：
function(){
//这里是队列的属性和方法
}然后我们同样创建一个保存元素的数组：
var items=[];接下来声明一些队列可用的方法：
- enqueue(element):向队列尾部添加一个（或是多个）元素。
- dequeue():移除队列的第一个元素，并返回被移除的元素。
- front():返回队列的第一个元素——最先被添加的也是最先被移除的元素。队列不做任何变动。
- isEmpty():检查队列内是否有元素，如果有返回true，没有返回false。
- size():返回队列的长度。
- print():打印队列的元素。
队列的完整代码 我们通过javascript提供的API，实现队列如下：
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 = function(){
return items.length;
};
this.print = function(){
console.log(items.toString());
};
}使用队列 创建完了队列，也给他了方法，然后我们来实例化一个对象：
var queue=new Queue();
console.log(queue.isEmpty());
//true
queue.enqueue(1);
queue.enqueue(3);
//添加元素
console.log(queue.front());
//返回队列的第一个元素1
console.log(queue.size());
//2
//输出元素个数4. 常见栈与队列的相关面试题 1、实现一个栈，要求实现Push（栈）、Pop（入栈）、Min（返回最小值）的时间复杂度为O（1） 利用一个栈 利用两个栈 2、使用两个栈实现一个队列 3、使用两个队列实现一栈 4、判断入栈顺序的合法性 5、一个数组实现两个栈（共享栈） 利用奇偶位置 两个栈相向而生
参考： https://juejin.im/post/5abca664518825556e5e2ce5 https://juejin.im/post/5819c153da2f60005ddc1e8a
腾讯云开发者
