题目详情

难度：简单

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 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]

提示

  • 1 <= values <= 10000
  • 最多会对 appendTail、deleteHead 进行 10000 次调用

思路分析

代码方面，因为我这边是用JavaScript，所以栈就通过数组来模拟。

首先我们先分析一下需求，需要实现两个函数，appendTail 和 deleteHead ，就是一个是尾部插入函数，一个头部弹出函数。

要求是用两个栈去模拟队列的操作，栈的特点是后进先出，队列的特点是新进先出。就是要通过栈的 push和 pop来实现队列的操作。

因为插入数据的时候是一样的，都是从尾部插入数据。所以区别就在于弹出的时候，一个是最先进去的最先弹出，一个是最后进去的最先弹出。

我们可以通过简单的模拟操作来看一下：

有四个数据，A,B,C,D。我们分别通过栈和队列将所有数据依次插入，再依次弹出。

栈的插入过程：A->B->C->D
栈的弹出过程：D->C->B->A

队列的插入过程：A->B->C->D
队列的弹出过程：A->B->C->D

根据过程我们可以看出，两个数据结构的插入顺序是一致的，都是：A->B->C->D，而弹出顺序，栈的弹出顺序与插入顺序是完全相反的，队列的插入顺序与弹出顺序是一致的。

那么我们就很好推断出 既然栈的弹出与插入顺序是相反的，那么我们用两个栈，栈A插入一次数据，然后弹出一次数据，栈B按照栈A数据弹出的顺序插入一次数据，然后栈B再弹出数据，这样的话，经过两次翻转，就可以使 弹出数据的顺序=插入数据的循序。

具体例子如下：

栈A按照正常的顺序插入弹出：

栈A的插入过程：A->B->C->D
栈A的弹出过程：D->C->B->A

然后栈B按照栈A的弹出顺序依次将数据压入栈B，再依次弹出：

栈B的插入过程：D->C->B->A
栈B的弹出过程：A->B->C->D

这个时候，栈B的弹出顺序=栈A的插入过程，就可以通过栈A插入数据+栈B弹出数据来模拟队列。

明白了原理，接下来就是代码的实现。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
var CQueue = function () {
    //定义两个数组模拟栈的操作
    this.queue1 = []
    this.queue2 = []
};

/** 
 * @param {number} value
 * @return {void}
 */
CQueue.prototype.appendTail = function (value) {
    //插入数据就正常的使用插入操作就可以了
    this.queue1.push(value)
};

/**
 * @return {number}
 */
CQueue.prototype.deleteHead = function () {
    //先判断一下当前的栈内有没有数据，没有就直接返回-1
    if (this.queue1.length === 0) {
        return -1
    } else {
        //有先将栈1中的数据依次弹出，然后按照弹出的顺序依次插入到栈2
        while (this.queue1.length > 0) {
            this.queue2.push(this.queue1.pop())
        }
        //现在栈2的栈顶元素就是栈1的首元素，直接弹出
        let temp = this.queue2.pop()
        //弹出后，再将栈2的元素依次的弹出，然后再按照弹出的顺序依次插入到栈1，恢复栈1原来的数据顺序（去除首元素之后的数据）
        while (this.queue2.length > 0) {
            this.queue1.push(this.queue2.pop())
        }
		//返回头部元素
        return temp
    }
};

/**
 * Your CQueue object will be instantiated and called as such:
 * var obj = new CQueue()
 * obj.appendTail(value)
 * var param_2 = obj.deleteHead()
 */