数据结构-----堆栈和队列

从数据（事物）转移到结构（组织方式）

数据是一种事物， 组织事物的方式方法有很多种，而这些方式方法就是我们所谓的结构；对于一个数据来说， 我们使用什么方式方法来组织这个数据，完全取决于我们的需求，不同类型的需求，会有不同类型的数据结构去满足。

堆栈 （LIFO last In first out）

文本编辑器的“撤消”操作使用堆栈来组织数据

• 线性的数据结构（按照顺序组织数据）

堆栈示例：

想象一下文本编辑器的撤销操作，每次将文本添加到文本编辑器中时，将此文本推入堆栈。文本编辑器的第一个加法器代表堆栈的底部; 最新的更改代表了堆栈的顶部。如果用户想要撤消最近的更改，则堆栈的顶部将被删除。这个过程可以重复，直到没有更多的堆栈添加，这是一个空白的文件！

堆栈结构---图解

• 堆栈的操作

• push(data)：添加数据
• pop(data)：删除最近添加的数据

• 堆栈代码的实现

function Stack(){
     this._size=0;   // 数据推送到容器的次数
     this._storage={ };  // 存储数据的容器（堆栈）
}

创建了构造函数Stack()，其所产生的实例都具有上面两个属性_size和_storage。

• 堆栈的方法

  • push(data)

  为了 让所有的实例都能使用这个方法，将其添加到原型上。

  需求：

  • 添加数据时，增加堆栈的大小
  • 添加数据的时候，都保留添加的顺序

  // 方法添加到原型，保证每一个实例都能使用
   Stack.prototype.push=function(data){
          var size=++this._size;  // 每次添加一次数据，this._size增加1
          this._storage[size]=data; // 把size作为堆栈的索引值，保存要存储的data
     }
  

  • pop()

  删除最近添加的数据，减少_this.size一个，返回删除的数据

  Stack.prototype.pop=function(){
      var size=this._size,
               deleteData; // 连续定义了两个变量，一个初始化了(栈的大小)，一个未初始化
  
     // 放在先调用pop，后调用push，出现长度size为0 的错误，只有当存储数据的时候，才执行删除的操作
  if(size){
    
      deleteData=this._storage[size]; // 初始化为最近添加的数据     
  
       delete this._storage[size];
     this.size--;
  
      return deleteData;
     }
    
  }
  

• 堆栈的最终版本

function Stack() {
    this._size = 0;
    this._storage = {};
}
 
Stack.prototype.push = function(data) {
    var size = ++this._size;
    this._storage[size] = data;
};
 
Stack.prototype.pop = function() {
    var size = this._size,
        deletedData;
 
    if (size) {
        deletedData = this._storage[size];
 
        delete this._storage[size];
        this._size--;
 
        return deletedData;
    }
};

队列 （FIFO ）

• 线性数据结构
• 只删除最先的添加数据（最旧的数据）
• 队列的操作
  • enqueue(data) ：将数据添加到队列中
  • dequeue(data) ：将最先添加到的数据删除（最旧的数据删除）

执行队列

function Queue(){
     this._oldestIndex = 1; // 原先数据的索引（最早的索引）
     this._newstIndex = 1; //  队列分配的最大数字（动态的更新，表示队列的最新位置）
     this._storage = {};  // 存储空间大小
}

创建了一个构造函数Queue，然后，添加三个属性。

• 队列的方法

  • size()

  返回队列的正确大小

  Queue.prototype.size = function(){
          return this._newestIndex - this._oldestIndex ;
  }
  

  • enqueue（data）

  使用this._newestIndex作为一个this._storage，并且this._newestIndex增加1

Queue.prototype.enqueue = function(data){
      this._storage[this._newestIndex] = data;
      this._newestIndex++; 
} 

使用this._newestIndex来创建新的位置，存放data数据，然后更新this._newestIndex的值。

• dequeue()

删除队列中的最旧的数据，删除完后，更新_oldestIndex的值。

Queue.prototype.dequeue = function() {
    var oldestIndex = this._oldestIndex,
        newestIndex = this._newestIndex,
        deletedData;
 
    if (oldestIndex !== newestIndex) {
        deletedData = this._storage[oldestIndex];
        delete this._storage[oldestIndex];
        this._oldestIndex++;
 
        return deletedData; // 返回当前删除的数据
    }
};

• 完整的队列实现

function Queue() {
    this._oldestIndex = 1;
    this._newestIndex = 1;
    this._storage = {};
}
 
Queue.prototype.size = function() {
    return this._newestIndex - this._oldestIndex;
};
 
Queue.prototype.enqueue = function(data) {
    this._storage[this._newestIndex] = data;
    this._newestIndex++;
};
 
Queue.prototype.dequeue = function() {
    var oldestIndex = this._oldestIndex,
        newestIndex = this._newestIndex,
        deletedData;
 
    if (oldestIndex !== newestIndex) {
        deletedData = this._storage[oldestIndex];
        delete this._storage[oldestIndex];
        this._oldestIndex++;
 
        return deletedData;
    }
};

• 使用javascript实现队列

//code.stephenmorley.org
function Queue() {
    var a = [], b = 0;
    this.getLength = function () {
        return a.length - b
    };
    this.isEmpty = function () {
        return 0 == a.length
    };
    this.enqueue = function (b) {
        a.push(b)
    };
    this.dequeue = function () {
        if (0 != a.length) {
            var c = a[b];
            2 * ++b >= a.length && (a = a.slice(b), b = 0);
            return c
        }
    };
    this.peek = function () {
        return 0 < a.length ? a[b] : void 0
    }
};

结论

两个线性数据结构：堆栈和队列。堆栈按顺序存储数据，并删除最近添加的数据; 队列按顺序存储数据，但删除最旧的添加数据。

• 参考连接

https://code.tutsplus.com/series/data-structures-in-javascript--cms-772