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

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

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

堆栈（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;
}

}

1
2


- 堆栈的最终版本

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 ;
}

1
2
3

- `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;
}

};

1	- 使用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
}
};
```