数据结构（四）——栈与队列

栈数据结构

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

1. 创建一个基于数组的栈

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

class Stack {
  constructor() {
    this.items = []; //用数组保存栈
  }
  // 向栈中添加元素
  push(e) {
    this.items.push(e);
  }
  // 向栈中移除元素
  pop() {
    return this.items.pop();
  }
  // 查找栈顶元素
  peek(){
    return this.items[this.items.length-1]
  }
  // 检查栈是否为空
  isEmpty(){
    return this.items.length===0
  }
  //获取元素个数
  size(){
    return this.items.length
  }
  // 清空栈元素
  clear(){
    return this.items.length=[]
  }
}

2.创建一个基于 JavaScript 对象的 Stack 类

class StackObj {
 constructor() {
   this.count = 0;
   this.items = {};
 }
 // 向栈中添加元素
 push(e) {
   this.items[count] = e;
   this.count++;
 }
 // 向栈中移除元素
 pop() {
   if (this.isEmpty()) {
     return undefined;
   }
   this.count--;
   const result = this.items[this.count];
   delete this.items[this.count];
   return result;
 }
 // 查找栈顶元素
 peek() {
   if (this.isEmpty()) {
     return undefined;
   }
   return this.items[this.count - 1];
 }
 // 验证一个栈是否为空
 isEmpty() {
   return this.items.count === 0;
 }
 //验证一个栈的大小
 size() {
   return this.items.count;
 }
 // 清空栈元素
 clear() {
   this.items = {};
   this.count = 0;
 }
 // 创建 toString 方法
 toString() {
   if (this.isEmpty()) {
     return "";
   }
   let objString = `${this.item[0]}`;
   for (let i = 1; i < this.count; i++) {
     objString = `${objString},${this.item[i]}`;
   }
   return objString;
 }
}

队列数据结构

队列是遵循先进先出（FIFO，也称为先来先服务）原则的一组有序的项。队列在尾部添加新元素，并从顶部移除元素。最新添加的元素必须排在队列的末尾。

创建队列

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

class Queue {
  constructor() {
    this.count = 0;
    this.lowestCount = 0;
    this.items = {};
  }
  // 向队列添加元素
  enqueue(e) {
    this.items[count] = e;
    this.count++;
  }

  // 从队列中移除元素
  dequeue() {
    if (this.isEmpty()) {
      return undefined;
    }
    this.count--;
    const result = this.items[this.lowestCount];
    delete this.items[this.lowestCount];
    this.lowestCount++;
    return result;
  }
  // 查找列头元素
  peek() {
    if (this.isEmpty()) {
      return undefined;
    }
    return this.items[this.lowestCount];
  }
  // 验证一个队列是否为空
  isEmpty() {
    return this.items.count - this.lowestCount === 0;
  }
  //验证一个队列的大小
  size() {
    return this.items.count - this.lowestCount;
  }
  // 清空栈元素
  clear() {
    this.items = {};
    this.count = 0;
    this.lowestCount = 0;
  }
}