225. 232. 队列、堆栈相互模拟实现
2018-12-16 本文已影响0人
Jason_Shu
首先我们看看两者的特性，队列是「先进先出」，堆栈是「先进后出」，如果使用其中一个数据结构来实现另一个数据结构的效果，可以采取两个该数据结构来实现。如：使用两个「堆栈」来模拟「队列」效果。
- 用队列模拟实现堆栈效果
实现如下功能：
- push(x) -- 元素 x 入栈
- pop() -- 移除栈顶元素
- top() -- 获取栈顶元素
- empty() -- 返回栈是否为空
思路： 申明两个「队列」queue1和queue2。一开始如果都为空就把数据push到queue1中，然后如果要查看「堆栈」。然后如果pop()就把两个队列中，不为空的那个「队列」依次弹出元素丢到另一个为空的「队列」中，直到长度为1, 这剩下的一个就是pop()所要的结果。
代码如下：
/**
* Initialize your data structure here.
*/
var MyStack = function() {
// 初始化两个「队列」
this.queue1 = [];
this.queue2 = [];
};
/**
* Push element x onto stack.
* @param {number} x
* @return {void}
*/
MyStack.prototype.push = function(x) {
if(this.queue1.length === 0 && this.queue2.length === 0) {
// 最开始如果都没有数据，就直接放在queue1中
this.queue1.push(x);
} else {
// 之后有了数据还要push，就把数据丢到那个长度不为0的「队列」中
if(this.queue1.length === 0) {
this.queue2.push(x);
} else {
this.queue1.push(x);
}
}
};
/**
* Removes the element on top of the stack and returns that element.
* @return {number}
*/
MyStack.prototype.pop = function() {
if(this.queue1.length === 0) {
while(this.queue2.length !== 1) {
this.queue1.push(this.queue2.shift());
}
return this.queue2.shift();
} else {
while(this.queue1.length !== 1) {
this.queue2.push(this.queue1.shift());
}
return this.queue1.shift();
}
};
/**
* Get the top element.
* @return {number}
*/
MyStack.prototype.top = function() {
if(this.queue1.length === 0) {
return this.queue2[this.queue2.length - 1]
} else {
return this.queue1[this.queue1.length - 1]
}
};
/**
* Returns whether the stack is empty.
* @return {boolean}
*/
MyStack.prototype.empty = function() {
if(this.queue1.length === 0 && this.queue2.length === 0) {
return true;
}
return false;
};
/**
* Your MyStack object will be instantiated and called as such:
* var obj = Object.create(MyStack).createNew()
* obj.push(x)
* var param_2 = obj.pop()
* var param_3 = obj.top()
* var param_4 = obj.empty()
*/
- 用「堆栈」模拟实现「队列」
实现如下功能：
- push(x) -- 将一个元素放入队列的尾部。
- pop() -- 从队列首部移除元素。
- peek() -- 返回队列首部的元素。
- empty() -- 返回队列是否为空。
思路：申明两个「堆栈」stack1和stack2，然后此处就直接定一个「输入栈」（stack1）和一个「输出栈」（stack2）。push操作都把元素丢入stack1，然后在pop操作的时候，把stack1中的元素依次弹出到stack2，然后把stack2最上面的元素pop出，就是pop操作的结果，然后还要把剩下的元素，依次弹出到stack1中。（注意：在用「队列」模拟实现「堆栈」的pop操作中，在得到pop的结果后无后续操作，使得两个「队列」可以相互调用，即无规定哪个「队列」来作「输入队列」或者「输出队列」，在此处会规定）
/**
* Initialize your data structure here.
*/
var MyQueue = function() {
this.stack1 = [];
this.stack2 = [];
};
/**
* Push element x to the back of queue.
* @param {number} x
* @return {void}
*/
MyQueue.prototype.push = function(x) {
// 规定stack1「堆栈」为「输入栈」
this.stack1.push(x);
};
/**
* Removes the element from in front of queue and returns that element.
* @return {number}
*/
MyQueue.prototype.pop = function() {
let temp;
while(this.stack1.length !== 0) {
// 把「输入栈」中的元素全部弹出到stack2「输出栈」中，然后pop弹出stack2中的元素即
// 为所要的结果
this.stack2.push(this.stack1.pop());
}
// 将结果用temp变量先记录下来
temp = this.stack2.pop();
// 后续操作：将「输出栈」中剩余的所有元素弹出到「输入栈」中
while(this.stack2.length !== 0) {
this.stack1.push(this.stack2.pop());
}
return temp;
};
/**
* Get the front element.
* @return {number}
*/
MyQueue.prototype.peek = function() {
return this.stack1[0];
};
/**
* Returns whether the queue is empty.
* @return {boolean}
*/
MyQueue.prototype.empty = function() {
if(this.stack1.length === 0 && this.stack2.length === 0 ) return true;
return false;
};
/**
* Your MyQueue object will be instantiated and called as such:
* var obj = Object.create(MyQueue).createNew()
* obj.push(x)
* var param_2 = obj.pop()
* var param_3 = obj.peek()
* var param_4 = obj.empty()
*/
