题目链接

题目描述：

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

示例 1：

输入：
[“CQueue”,”appendTail”,”deleteHead”,”deleteHead”]
[[],[3],[],[]]
输出：[null,null,3,-1]

示例 2：

输入：
[“CQueue”,”deleteHead”,”appendTail”,”appendTail”,”deleteHead”,”deleteHead”]
[[],[],[5],[2],[],[]]
输出：[null,-1,null,null,5,2]

解题思路

  首先理解题目所给实例的字符串数组的意思：CQueue初始化、appendTail入队、deleteHead出队并返回出队元素。也就是说字符串数组就是记录操作的指令，而输入的int数组包含需要入队的元素。这里要注意输出的数组，它并不是指当前队列内元素的状态，而是仅仅指每一个操作的返回情况，实际上只有deleteHead有返回情况。
  其次就是用双栈实现队列的进队入队的思路了。要清楚这两种数据结构的特点，栈是先进后出，队列是先进先出。显然单一的栈是不能实现队列的进队入队操作滴～那么如何利用双栈呢？举一个例子，1，2，3元素按序进入第一个栈input，此时input从栈顶到栈底的元素依次为3，2，1。现在想要实现出队顺序为1，2，3，将第一个栈的元素依次出栈并入栈到第二个栈output，此时output从栈顶到栈底的元素依次为1，2，3，显然此时出栈的顺序为1，2，3，即利用了双栈实现了队列操作。
  最后就是三个函数的功能设计了。

  1. 题目不要求我们在初始化时候做事情，所以构造函数CQueue可以不用管；
  2. 根据实例我们发现入队appendTail不要求返回值，仅仅进队就好。所以一行入栈代码即可解决；
  3. deleteHead出队操作就需要一丢丢分析了，不仅要求元素出队，还要返回出队的元素，而且队空时要返回-1 if-else逻辑
  4. 如果input和output均为空，说明此时队列为空，返回-1；
  5. 否则无论此时input是否为空，只要output不为空，就说明output还有未出栈的元素，优先操作output；
  6. 否则，output为空而input不为空，需要将input元素全部压入output中，再操作output。

  现在给出c++和JavaScript版本代码～

c++

  1. class CQueue {
  2. public:
  3.     CQueue() {
  5.     }
  7.     void appendTail(int value) {
  8.         input.push(value);
  9.     }
  11.     int deleteHead() {
  12.         if(input.empty() && output.empty()) //双栈均为空
  13.             return -1;
  14.         else if(!output.empty()){          //output栈不为空，说明还有未出队的元素
  15.             int result = output.top();
  16.             output.pop();
  17.             return result;
  18.         }
  19.         else{                             //output栈为空，再执行删除需要input元素出栈入栈
  20.             while(!input.empty()){
  21.                 int value = input.top();
  22.                 input.pop();
  23.                 output.push(value);
  24.             }
  26.             int result = output.top();
  27.             output.pop();
  28.             return result;
  29.         }
  31.     }
  32. private:
  33.     stack<int> input;
  34.     stack<int> output;
  35. };

JavaScript

  1. var CQueue = function() {
  2.     this.output = [];
  3.     this.input = [];
  4. };
  6. /** 
  7.  * @param {number} value
  8.  * @return {void}
  9.  */
  10. CQueue.prototype.appendTail = function(value) {
  11.     this.input.push(value);
  12. };
  14. /**
  15.  * @return {number}
  16.  */
  17. CQueue.prototype.deleteHead = function() {
  18.     const {input, output} = this;       //es6 解构赋值
  19.     if(!output.length && !input.length){
  20.         return -1;
  21.     }
  22.     else if(output.length){
  23.         return output.pop();
  24.     }
  25.     else{
  26.         while(input.length){
  27.             output.push(input.pop());
  28.         }
  29.         return output.pop();
  30.     }
  31. };

如果有错误或者不严谨的地方，请务必给予指正，十分感谢。