JavaScript数据结构与算法（4）栈和队列

以你之姓@ 2022-02-27 17:48 286阅读 0赞

参考文章：  
[https://www.cnblogs.com/xiaohuochai/p/8174742.html][https_www.cnblogs.com_xiaohuochai_p_8174742.html]

**1.栈**

栈是一种遵从后进先出(LIFO)原则的有序集合。新添加的或待删除的元素都保存在栈的末尾。称作栈顶，另一端就叫栈底。在栈里，新元素都靠近栈顶，旧元素都靠近栈底。

为栈声明一些方法：  
push(element(s))：添加一个（或几个）新元素到栈顶  
pop()：移除栈顶的元素，同时返回被移除的元素  
peek()：返回栈顶的元素，不对栈做任何修改（这个方法不会移除栈顶的元素，仅仅返回它）  
isEmpty()：如果栈里没有任何元素就返回true，否则返回false  
clear()：移除栈里的所有元素  
size()：返回栈里的元素个数。这个方法和数组的length属性很类似

现在通过数组的方法来实现栈，代码如下：

//我们将创建一个类来表示栈
    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(){//如果栈内没有任何元素就返回true，否则返回false
        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();
      };
    }

使用Stack类（栈）：

//首先，我们需要初始化Stack类。
    let stack = new Stack(); 
    
    //验证一下栈是否为空（输出是true，因为还没有往栈里添加元素）
    console.log(stack.isEmpty()); //输出为true
    
    //接下来，往栈里添加一些元素
    stack.push(5);
    stack.push(8); 
    
    console.log(stack.peek()); //输出8 
    
    //再添加一个元素
    stack.push(11);
    console.log(stack.size()); //输出3
    console.log(stack.isEmpty()); //输出false 
    
    //然后，调用两次pop方法从栈里移除2个元素：
    stack.pop();
    stack.pop();
    console.log(stack.size()); //输出2
    stack.print(); //输出[5, 8]

**2.ECMAScript 6 和 Stack 类**

用 ES6 语法声明 Stack 类:

我们创建了一个可以当作类来使用的Stack函数。JS函数都有构造函数，可以用来模拟类的行为。我们声明了一个私有的items变量，它只能被Stack函数/类访问。然而，这个方法为每个类的实例都创建一个items变量的副本。因此，如果要创建多个Stack实例，它就不太适合了

class Stack {
     	constructor () {
    	 	this.items = []; //{1}
    	}
     
     	push(element){
     		this.items.push(element);
     	}
     	
     	//其他方法
     	
    }

我们只是用ES6的简化语法把Stack函数转换成Stack类。这种方法不能像其他语言（Java、C++、C\#）一样直接在类里面声明变量，只能在类的构造函数constructor里声明（行\{1\}），在类的其他函数里用this.nameofVariable就可以引用这个变量。

尽管代码看起来更简洁、更漂亮，变量items却是公共的。ES6的类是基于原型的。虽然基于原型的类比基于函数的类更节省内存，也更适合创建多个实例，却不能够声明私有属性（变量）或方法。而且，在这种情况下，我们希望Stack类的用户只能访问暴露给类的方法。否则，就有可能从栈的中间移除元素（因为我们用数组来存储其值），这不是我们希望看到的。

看看ES6语法有没有其他的方法可以创建私有属性。

这个问题打算专门写个笔记。

1.Symbol

2.WeakMap

有一种数据类型可以确保属性是私有的，这就是WeakMap。WeakMap可以存储键值对，其中键是对象，值可以是任意数据类型。

如果用WeakMap来存储items变量，Stack类就是这样的：

行\{1\}，声明一个WeakMap类型的变量items。行\{2\}，在constructor中，以this（Stack类自己的引用）为键，把代表栈的数组存入items。行\{3\}，从WeakMap中取出值，即以this为键（行\{2\}设置的）从items中取值.

现在知道，items在Stack类里是真正的私有属性了，但还有一件事要做。items现在仍然是在Stack类以外声明的，因此谁都可以改动它。要用一个闭包（外层函数）把Stack类包起来，这样就只能在这个函数里访问WeakMap：

当Stack函数里的构造函数被调用时，会返回Stack类的一个实例（行\{5\}）

现在，Stack类有一个名为items的私有属性。虽然它很丑陋，但毕竟实现了私有属性。然而，用这种方法的话，扩展类无法继承私有属性。鱼与熊掌不可兼得。

栈的完整代码如下:

事实上，尽管ES6引入了类的语法，仍然不能像在其他编程语言中一样声明私有属性或方法。有很多种方法都可以达到相同的效果，但无论是语法还是性能，这些方法都有各自的优点和缺点

哪种方法更好？这取决于在实际项目中如何使用算法，要处理的数据量，要创建的实例个数，以及其他约束条件

**3.队列**

Queue类和Stack类非常类似，只是添加和移除元素的原则不同。

接下来需要声明一些队列可用的方法：

enqueue(element(s))：向队列尾部添加一个（或多个）新的项。  
dequeue()：移除队列的第一（即排在队列最前面的）项，并返回被移除的元素。  
front()：返回队列中第一个元素——最先被添加，也将是最先被移除的元素。队列不 做任何变动（不移除元素，只返回元素信息——与Stack类的peek方法非常类似）。  
isEmpty()：如果队列中不包含任何元素，返回true，否则返回false。  
size()：返回队列包含的元素个数，与数组的length属性类似。

创建类来表示一个队列：

使用Queue类：

let queue = new Queue();
    console.log(queue.isEmpty()); //输出true 
    
    queue.enqueue("John");
    queue.enqueue("Jack"); 
    
    queue.enqueue("Camila");
    
    queue.print();
    console.log(queue.size()); //输出3
    console.log(queue.isEmpty()); //输出false
    queue.dequeue();
    queue.dequeue();
    queue.print();

**4.用 ECMAScript 6 语法实现的 Queue 类**

和第3章一样，我们也可以用ECMAScript 6语法编写Queue类。在这种方法中，我们要用一个WeakMap来保存私有属性items，并用外层函数（闭包）来封装Queue类。

**5.优先队列**

元素的添加和移除是基于优先级的。

实现一个优先队列，有两种选项：设置优先级，然后在正确的位置添加元素；或者用入列操作添加元素，然后按照优先级移除它们。在这个示例中，我们将会在正确的位置添加元素，因此可以对它们使用默认的出列操作：

默认的Queue类和PriorityQueue类实现上的区别是，要向PriorityQueue添加元素，需要创建一个特殊的元素（行\{1\}）。这个元素包含了要添加元素，需要创建一个特殊的元素（行\{1\}）。这个元素包含了要添加到队列的元素（它可以是任意类型）及其在队列中的优先级

如果队列为空，可以直接将元素入列（行\{2\}）。否则，就需要比较该元素与其他元素的优先级。当找到一个比要添加的元素的priority值更大（优先级更低）的项时，就把新元素插入到它之前（根据这个逻辑，对于其他优先级相同，但是先添加到队列的元素，我们同样遵循先进先出的原则）。要做到这一点，我们可以用JavaScript的array类的splice方法。 一旦找到priority值更大的元素，就插入新元素（行\{3\}）并终止队列循环（行\{4\}）。这样， 队列也就根据优先级排序了

如果要添加元素的priority值大于任何已有的元素，把它添加到队列的末尾就行了（行\{5\}）：

代码测试：

var priorityQueue = new PriorityQueue(); 
    priorityQueue.enqueue("John", 2);
    priorityQueue.enqueue("Jack", 1);
    priorityQueue.enqueue("Camila", 1); 
    priorityQueue.print();

[https_www.cnblogs.com_xiaohuochai_p_8174742.html]: https://www.cnblogs.com/xiaohuochai/p/8174742.html