题目

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

思路分析

我们所学的每一种数据结构，本质上研究的是对数据如何存储和使用，这就必然涉及到增加，删除，修改，获取这四个操作，日常工作其实所作的也逃不掉这四种业务。

那么在考虑实现这些方法时，我们优先考虑如何实现增加，道理很简单，只有先增加，才能继续研究如何删除，修改，获取，否则，没有数据，怎么研究?

就这道题目而言，我们先考虑如何实现appendTail方法，两个栈分别命名为stack_1 和 stack_2，其中 stack_1 用来存储数据，队列 appendTail 方法只能操作 stack_1

接下来考虑 deleteHead 方法，队列的头，在 stack_1 的底部，栈是先进后出，目前取不到，可不还有stack_2么，把stack_1里的元素都倒入到stack_2中，这样，队列的头就变成了stack_2的栈顶，这样不就可以执行stack_2.pop()来删除了么。执行完pop后，需要把stack_2里的元素再倒回到stack_1么，不需要，现在队列的头正好是stack_2的栈顶，恰好可以操作，队列的 deleteHead 方法借助栈的pop方法完成，队列的head方法借助栈的top方法完成。

如果stack_2是空的怎么办？把stack_1里的元素都倒入到stack_2就可以了，这样，如果stack_1也是空的，说明队列就是空的，返回null就可以了。

appendTail始终都操作stack_1，deleteHead和head方法始终都操作stack_2。

代码实现

Stack

  1. class Stack {
  2.   constructor() {
  3.     this.count = 0;
  4.     this.items = {};
  5.   }
  6.   push(element) {
  7.     this.items[this.count] = element;
  8.     this.count++;
  9.   }
  10.   pop() {
  11.     if (this.isEmpty()) {
  12.       return undefined;
  13.     }
  14.     this.count--;
  15.     const result = this.items[this.count];
  16.     delete this.items[this.count];
  17.     return result;
  18.   }
  19.   top() {
  20.     if (this.isEmpty()) {
  21.       return undefined;
  22.     }
  23.     return this.items[this.count - 1];
  24.   }
  25.   isEmpty() {
  26.     return this.count === 0;
  27.   }
  28.   size() {
  29.     return this.count;
  30.   }
  31.   clear() {
  32.     /* while (!this.isEmpty()) {
  33.         this.pop();
  34.       } */
  35.     this.items = {};
  36.     this.count = 0;
  37.   }
  38.   toString() {
  39.     if (this.isEmpty()) {
  40.       return '';
  41.     }
  42.     let objString = `${this.items[0]}`;
  43.     for (let i = 1; i < this.count; i++) {
  44.       objString = `${objString},${this.items[i]}`;
  45.     }
  46.     return objString;
  47.   }
  48. }

StackQueue

  1. class StackQueue {
  2.   constructor() {
  3.     this.stack_1 = new Stack()
  4.     this.stack_2 = new Stack()
  5.   }
  7.   appendTail(ele) {
  8.     this.stack_1.push(ele)
  9.   }
  11.   head() {
  12.     if (this.stack_2.isEmpty() && this.stack_1.isEmpty()) {
  13.       return null
  14.     }
  16.     if (this.stack_2.isEmpty()) {
  17.       while (!this.stack_1.isEmpty()) {
  18.         this.stack_2.push(this.stack_1.pop())
  19.       }
  20.     }
  22.     return this.stack_2.top()
  23.   }
  25.   deleteHead() {
  26.     if (this.stack_2.isEmpty() && this.stack_1.isEmpty()) {
  27.       return null
  28.     }
  30.     if (this.stack_2.isEmpty()) {
  31.       while (!this.stack_1.isEmpty()) {
  32.         this.stack_2.push(this.stack_1.pop())
  33.       }
  34.     }
  36.     return this.stack_2.pop()
  37.   }
  38. }