剑指 Offer 09. 用两个栈实现队

tech2023-01-24  58

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

思路:两个栈(后入先出)实现一个队列(先入先出)

插入一个元素:直接在stack1中压入

删除一个元素的步骤:当stack2不为空时,在stack2的栈顶元素是最先进入队列的元素,可以弹出;当stack2为空时,我们把stack1中的元素逐个弹出并压入stack。由于先进入队列的元素被压到stack1的底端,经过弹出和压入操作后就处于stack2的顶端,又可以直接弹出。

var CQueue = function() { this.stack1=[]; this.stack2=[]; }; CQueue.prototype.appendTail = function(value) { this.stack1.push(value); }; CQueue.prototype.deleteHead = function() { if(this.stack2.length){ //1、stack2不为空,直接取 return this.stack2.pop(); }else{ //2、stack2为空,循环stack1,将里面的元素添加到stack2中 while(this.stack1.length){ this.stack2.push(this.stack1.pop()) } return this.stack2.pop()||-1 } };

 

最新回复(0)