【数据结构】栈与队列

栈与队列分别是两种数据结构，不同语言对于栈和队列有着不同的声明
栈数据结构的特点是 FILO（first in last out） 即先进后出，队列则是 FIFO（first in first out）即先进先出。


1. 数据结构【栈】介绍

图片：zan.png

其实非常好理解，我们将栈可以看成一个箱子

• 往箱子里面放东西叫做入栈
• 往箱子里面取东西叫做出栈
• 箱子的底部叫做栈底
• 箱子的顶部叫做栈顶

说到栈的特性，肯定会有一句经典的言语来概括：先进后出(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();
    };
}

使用栈
创建完了栈，也给他了方法，然后我们来实例化一个对象：

var stack=new Stack();
console.log(stack.isEmpty());
//true
stack.push(1);
stack.push(3);
//添加元素
console.log(stack.peek());
//输出栈顶元素3
console.log(stack.size());
//2
//输出元素个数

3. 数据结构【队列】

图片：line.png

数据结构的队列长的是这个样子：

图片：data.png

其实队列非常好理解，我们将队列可以看成小朋友排队

• 队尾的小朋友到指定的地点了-->出队
• 有新的小朋友加入了-->入队

相对于栈而言，队列的特性是：先进先出

• 先排队的小朋友肯定能先打到饭！

队列也分成两种：

• 静态队列(数组实现)
• 动态队列(链表实现)

这次我就使用数组来实现静态队列了


队列的创建
首先我们声明一个类：

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