1. 题目描述
用两个栈实现一个队列。队列的声明如下:
请实现它的两个函数appendTail
和deleteHead
,分别完成在队列尾部插入结点和在队列头部删除结点的功能。
2. 解题思路
一个栈用来存储插入队列数据,一个栈用来从队列中取出数据。
从第一个栈向第二个栈转移数据的过程中:数据的性质已经从后入先出变成了先入先出。
3. 代码
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
| class Queue { constructor() { this.stack1 = [] this.stack2 = [] }
appendTail(value) { this.stack1.splice(0, 0, value) }
deleteHead() { if (this.stack2.length === 0) { let length = this.stack1.length for (let i = 0; i < length; ++i) { this.stack2.splice(0, 0, this.stack1.shift()) } }
return this.stack2.length === 0 ? null : this.stack2.shift() } }
let queue = new Queue() queue.appendTail(1) queue.appendTail(2) queue.appendTail(3)
console.log(queue.deleteHead()) queue.appendTail(1)
console.log(queue.deleteHead()) console.log(queue.deleteHead()) console.log(queue.deleteHead())
|