js数据结构和算法(二)栈和队列

谁践踏了优雅 2021-09-15 00:50 313阅读 0赞

# 一.栈 #

## 1.定义 ##

栈是一种重要的线性结构。栈（Stack）是一个**后进先出**（Last in first out,LIFO）的线性表，它要求只在表尾进行删除和插入操作。对于栈来说，这个表尾称为栈的栈顶，相应的表头称为栈底。

栈的操作只能在这个线性表的表尾进行：  
    ** 栈的插入操作（Push），叫做进栈，也称为压栈，入栈。**

**     栈的删除操作（Pop），叫做出栈，也称为弹栈。**

## 2.栈的顺序存储结构 ##

因为栈的本质是一个线性表，线性表有两种存储形式，那么栈也有分为**栈的顺序存储结构**和栈的**链式存储结构**。

顺序存储结构：是把数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的。

例如我们编程语言的数组结构就是这样滴。

![Image 1][]

链式存储结构：是把数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的。

很显然，这样说的话链式存储结构的数据元素存储关系并不能反映其逻辑关系，因此需要用一个指针存放数据元素的地址，这样子通过地址就可以找到相关联数据元素的位置。

![Image 1][]

最开始栈中不含有任何数据，叫做空栈，此时栈顶就是栈底。然后数据从栈顶进入，栈顶栈底分离，整个栈的当前容量变大。数据出栈时从栈顶弹出，栈顶下移，整个栈的当前容量变小。

![Image 1][]

## 3.栈操作 ##

### （1）.基本操作 +数字进制间的相互转换 ###

/** *   
     * 栈的构造函数   
     * */   
    function Stack() {   
        // 用数组来模拟栈   
        this.dataStore = []; //底层数据结构是数组  
        this.top = 0; //top应该是等于数组的length的  
    }  
    //栈需要有如下的方法  
    Stack.prototype = {  
        /**  
         * 1. push()  
         * 向栈中压入一个新元素， 需要将其保存在数组中变量 top 所对  
         * 应的位置， 然后将 top 值加 1， 让top指向数组中下一个空位置  
         * 特别注意 ++ 操作符的位置， 它放在 this.top 的后面， 这样新入栈的元素就被放在  
         * top 的当前值对应的位置， 然后再将变量 top 的值加 1， 指向下一个位置  
         * */  
        push:function(element){  
            this.dataStore[this.top++] = element;  
        },  
        /**  
         * pop() 方法恰好与 push() 方法相反——它返回栈顶元素， 同时将变量 top 的值减 1  
         * 也可以改造一下,只--this.top,不返回栈顶元素  
         * */  
        pop:function(){  
            return this.dataStore[--this.top];  
        },  
        /**  
         * peek() 方法返回数组的第 top-1 个位置的元素， 即栈顶元素  
         * */  
        peek:function(){  
            return this.dataStore[this.top-1];  
        },  
        length:function(){  
            return this.top;  
        },  
        clear:function(){  
             this.top = 0;  
        }  
    };  
    //测试 Stack 类的实现  
    var s = new Stack();  
    s.push("David");  
    s.push("Raymond");  
    s.push("Bryan");  
    console.log("length: " + s.length());//length: 3  
    console.log(s.peek());//Bryan  
    var popped = s.pop();  
    console.log("The popped element is: " + popped);//The popped element is: Bryan  
    s.push("Cynthia");  
    s.clear();  
    console.log("length: " + s.length());//length: 0  
    /**
     * 栈的应用一:数字进制间的相互转换
     *
     * 利用栈将一个数字从一种数制转换成另一种数制。
     * 假设想将数字 n 转换为以 b 为基数
     * 的数字， 实现转换的算法如下:
     * (1) 最高位为 n % b， 将此位压入栈。
     * (2) 使用 n/b 代替 n。
     * (3) 重复步骤 1 和 2， 直到 n 等于 0， 且没有余数。
     * (4) 持续将栈内元素弹出， 直到栈为空， 依次将这些元素排列， 就得到转换后数字的字符
     * 串形式。
     *
     * 下面就是该函数的定义， 可以将十进制的数字转化为二至九进制的数字：
     * */
    function mulBase(num, base) {
        var s = new Stack();
        do {
            s.push(num % base);
            num = Math.floor(num /= base);
        } while (num > 0);
        var converted = "";
        while (s.length() > 0) {
            converted += s.pop();
        }
        return converted;
    }
    //将数字转换为二进制
    var newNum = mulBase(32, 2);
    console.log(newNum);// 32 converted to base 2 is 100000 
    //将数字转换为八进制
    var newNum = mulBase(125, 8);
    console.log(newNum); // 125 converted to base 8 is 175

### (2).回文(palindrome) ###

回文就是指一个单词，数组，短语，从前往后或是从后往前都是一样的 12321.racecar

回文最简单的思路就是, 把元素反转后如果与原始的元素相等，那么就意味着这就是一个回文了

/**
     * 栈的应用二: 回文
     * 使用栈，可以轻松判断一个字符串是否是回文。 将拿到的字符串的每个字符按从左至
     * 右的顺序压入栈。 当字符串中的字符都入栈后， 栈内就保存了一个反转后的字符串， 最后
     * 的字符在栈顶， 第一个字符在栈底.
     *
     * 字符串完整压入栈内后， 通过持续弹出栈中的每个字母就可以得到一个新字符串， 该字符
     * 串刚好与原来的字符串顺序相反。 我们只需要比较这两个字符串即可， 如果它们相等， 就
     * 是一个回文。
     * */
    //下例是一个利用前面定义的 Stack 类， 判断给定字符串是否是回文的程序。
    function isPalindrome(word) {
        var s = new Stack();//要引用 栈的构造函数
        for (var i = 0; i < word.length; ++i) {
            s.push(word[i]);
        }
        var rword = "";
        while (s.length() > 0) {
            rword += s.pop();
        }
        if (word == rword) {
            return true;
        }else {
            return false;
        }
    }
    var word = "hello";
    if (isPalindrome(word)) {//hello不是回文
        console.log(word + "是回文.");
    }else {
        console.log(word + "不是回文");
    }
    word = "racecar"
    if (isPalindrome(word)) {//racecar是回文.
        console.log(word + "是回文.");
    }else {
        console.log(word + "不是回文");
    }

### (3).递归与使用栈模拟递归过程 ###

/**
     * 8.递归与使用栈模拟递归过程
     * 栈常常被用来实现编程语言， 使用栈实现递归即为一例
     * 5! = 5 * 4 * 3 * 2 * 1 = 120
    //斐波那契递归
    function factorial(n) {
        if (n === 0) {
            return 1;
        }else {
            return n * factorial(n-1);
        }
    }
    console.log(factorial(5));//120
    
    //使用栈模拟上面的递归
    function fact(n) {
        var s = new Stack();//要引用 栈的构造函数
        while (n > 1) {
            s.push(n--);
        }
        var product = 1;
        while (s.length() > 0) {
            product *= s.pop();
        }
        return product;
    }
    console.log(fact(5));//120

# 二.队列 #

1.定义

\* 队列是一种列表，**只能在队尾插入元素，在队首删除元素**。  
\* 队列用于存储按顺序排列的数据， **先进先出**， 先进队列的元素优先处理。

\* 可以将队列想象成在银行前排队的人群.

![Image 1][]

\*与栈比较  
相反：队列是一种先进先出（First In First Out, FIFO）的线性表。  
相同：队列也是一种重要的线性结构，实现一个队列同样需要顺序表或链表作为基础。

2.队列的链式存储结构

队列既可以用链表实现，也可以用顺序表实现。跟栈相反的是，栈一般我们用顺序表来实现，而队列我们常用链表来实现，简称为链队列。

3.操作

//队列类的构造函数
    function Queue() {
        this.dataStore = []; //使用数组作为底层数据对象
    }
    //队列有如下的方法  
    Queue.prototype = { 
    	// enqueue(element) 向队尾添加一个元素,借助push
        enqueue:function(element){
        	this.dataStore.push(element);
        },
        // dequeue() 删除队首的元素,借助shift
        dequeue:function(){
        	return this.dataStore.shift();
        },
        // front() 读取队首元素
        front:function(){
        	return this.dataStore[0];
        },
        //back() 读取队尾元素
        back:function(){
        	return this.dataStore[this.dataStore.length-1];
        },
    	//queueToString() 方法显示队列内的所有元素：
    	queueToString:function() {
    	    var retStr = "";
    	    for (var i = 0; i < this.dataStore.length; ++i) {
    	        retStr += this.dataStore[i] + "\n";
    	    }
    	    return retStr;
    	},
    	//empty() 判断队列是否为空
    	empty: function() {
    	    if (this.dataStore.length == 0) {
    	        return true;
    	    }else {
    	        return false;
    	    }
    	}
    }; 
    // 测试程序
    var q = new Queue();
    q.enqueue("Meredith");
    q.enqueue("Cynthia");
    q.enqueue("Jennifer");
    console.log("显示队列内的所有元素:"+q.queueToString());//Meredith Cynthia Jennifer
    q.dequeue();
    console.log("显示队列内的所有元素:"+q.queueToString());// Cynthia Jennifer
    console.log("队首: " + q.front());// 队首: Cynthia
    console.log("队尾: " + q.back());//队尾: Jennifer

三.参考：

[鱼C工作室][C]

[常见数据结构与算法javascript实现][javascript]

[数据结构与算法JavaScript (一) 栈][JavaScript _]

[学习JavaScript数据结构与算法（一）：栈与队列][JavaScript]

[Image 1]: 
[C]: http://blog.fishc.com/2025.html
[javascript]: http://blog.csdn.net/haoshidai/article/details/52263191
[JavaScript _]: https://www.cnblogs.com/aaronjs/p/4200430.html
[JavaScript]: https://www.imooc.com/article/4543