今天稍微停下前进的脚步，来看下队栈的左右互搏术。
前两天学习了队列和栈以后，今天就可以试着来用两个栈实现队列的功能 或者 用两个队列来实现栈的功能。
数据结构之---栈实现队列
1. 用两个栈实现一个队列
1.1 题目分析
栈是先进后出，队列是先进先出，但可以用两个栈来模拟一个队列的功能，来实现队列中主要的enqueue，dequeue， head 方法。
1.2 思路分析
我们所学的每一种数据结构，本质上都是对数据如何存储和使用的研究，这就必然涉及到增删改查，那么考虑实现这些方法时，我们优先考虑如何实现数据的增加，只有存在了数据，才能够后续的操作。
所以如何实现队列中的增加数据方法enqueue呢？
- 给两个栈分别命名为 stack1，stack2。那有了这两个栈以后，可以选取其中一个来存储数据，比如说stack1，那么队列的enqueue方法就很容易了，直接利用栈的push方法就能够添加数据。
接下来考虑队列中的删除dequeue方法
- 首先要注意下dequeue方法是删除队列中的头部元素，而此时队首是在stack1栈底的，目前来说还取不到。
- 这个时候stack2该上场了，可以把stack1中的元素都依次移除并压入stack2中，这样的话，stack2的栈顶就变成了队首，不就可以利用stack2的pop方法来移除元素了嘛。
那队列的head方法呢
- 执行完stack2的pop方法后，还需要把数据再移回stack1里吗？
其实不需要了，因为此时队首正好是stack2的栈顶，而队列的head方法就可以利用栈的top方法来实现了。- 如果stack2是空的怎么办？那stack1的元素都移除到stack2就可以了。
- 如果stack1也是空的呢，那就说明队列中没有元素了，此时返回null就可以了。
注意到了吗，这里又用到了分而治之 的思想，还记得之前在哪里用过吗？
对，就是在给栈添加获取最小值方法的时候用过，当时也是用了两个栈来实现。
这里的话enqueue始终都操作stack1，dequeue和head方法始终都操作stack2。
1.3 代码实现
{
class StackQueue {
constructor() {
this.stack1 = new Stack();
this.stack2 = new Stack();
}
// 初始化stack，伪造私有方法
_initStack() {
if (this.stack1.isEmpty() && this.stack2.isEmpty()) {
return null; // 如果两个栈都是空的，那么队列中就没有元素
}
if (this.stack2.isEmpty()) {
// 如果stack2是空的，那么此时stack1一定不为空
while (!this.stack1.isEmpty()) {
this.stack2.push(this.stack1.pop()); // 把stack1的元素移除到stack2中
}
}
}
// 向队尾添加一个元素
enqueue(item) {
this.stack1.push(item); // 把数据存入到stack1中
}
// 删除队首的一个元素
dequeue() {
this._initStack();
return this.stack2.pop();
}
// 返回队首的元素
head() {
this._initStack();
return this.stack2.top();
}
}
var stackQueue = new StackQueue();
stackQueue.enqueue(1);
stackQueue.enqueue(4);
stackQueue.enqueue(8);
console.log(stackQueue.head()); // 1
stackQueue.dequeue();
stackQueue.enqueue(9);
console.log(stackQueue.head()); // 4
stackQueue.dequeue();
console.log(stackQueue.head()); // 8
console.log(stackQueue.dequeue()); // 8
console.log(stackQueue.dequeue()); // 9
}
是不是觉得很简单呢，梳理清楚队列和栈的特性就OK啦。
接下来让我们继续修炼，用队列实现栈吧！
2. 用两个队列实现一个栈
2.1 题目分析
队列是先进先出，栈是先进后出，(不断重复这两个知识点) 但可以用两个队列来模拟一个栈的功能，来实现栈中主要的push，pop， top 方法。
你可能会想到利用上边的套路来实现这个需求，但是最后的结果你会发现是不正确的。因为 把stack1的元素移除到stack2中，此时的两个栈中的数据就首尾交换了，而如果此处换成队列 this.queue2. enqueue(this.queue1. dequeue())，
你会发现由于队列的特性，此时的两个队列还是一样的，首尾并没有交换。
so 我们来换个思路
2.2 思路分析
和上边一样，我们先考虑如何实现栈的存储数据push方法:
- 给两个队列分别命名为 queue1，queue2。实现push方法时，利用队列的enqueue方法，如果两个队列都为空，那么默认向queue1里添加数据；如果有一个不为空，那么就向这个不为空的队列里添加数据。
top方法就简单了:
- 利用队列的tail方法，两个队列要么都为空，要么有一个不为空，那么返回不为空队列的尾部元素就是栈顶元素了.
接下来思考比较复杂的pop方法:
- pop方法删除的是栈顶，但此时栈顶元素是队列的尾部元素，而队尾元素是不能删除的。
- 但每次执行pop时，可以将不为空的a队列里的元素循环删除并放入到另一个b队列中，直到a队列中只剩下一个元素，此时a队列的这个元素就是队列的尾部元素，也就是栈顶元素了，那pop方法就简单了，利用a队列的dequeue方法就可以了。
在具体的实现中，需要额外定义两个变量，dataQueue和emptyQueue:
- dataQueue始终指向那个不为空的队列
- emptyQueue始终指向那个为空的队列
2.3 代码实现
{
class QueueStack {
constructor() {
this.queue1 = new Queue();
this.queue2 = new Queue();
this.dataQueue = null; // 存放数据的队列
this.emptyQueue = null; // 存放备份数据的队列
}
// 初始化队列数据，模拟私有方法 确认哪个队列存放数据，哪个队列做备份
_initQueue() {
if (this.queue1.isEmpty()) {
this.dataQueue = this.queue2;
this.emptyQueue = this.queue1;
} else {
// 都为空的话 默认是 队列1
this.dataQueue = this.queue1;
this.emptyQueue = this.queue2;
}
}
// 往栈里压入一个元素
push(item) {
this._initQueue();
this.dataQueue.enqueue(item);
}
// 返回栈顶的元素
top() {
this._initQueue();
return this.dataQueue.tail();
}
// 把栈顶的元素移除
pop() {
this._initQueue();
while (this.dataQueue.size() > 1) {
// 利用备份队列转移数据，
this.emptyQueue.enqueue(this.dataQueue.dequeue()); // 数据队列和备份队列交换了身份
}
return this.dataQueue.dequeue(); // 移除数据队列的头部元素
}
}
var queueStack = new QueueStack();
queueStack.push(1);
queueStack.push(2);
queueStack.push(4);
console.log(queueStack.top()); // 栈顶是 4
console.log(queueStack.pop()); // 移除 4
queueStack.push(5);
console.log(queueStack.top()); // 栈顶变成 5
queueStack.push(6);
console.log(queueStack.pop()); // 移除 6
console.log(queueStack.pop()); // 移除5
console.log(queueStack.top()); // 栈顶是 2
}
如果你有其他好的方法，欢迎留言
3. 总结
我们利用基础的数组api实现了队列和栈的功能，再来回顾下（敲黑板，划重点了）
- 队列最大的特点就是先进先出，主要的两个操作是入队和出队，和栈一样，是个受限制的数据结构。
- 队列既可以用数组实现，也可以用链表实现，用数组实现的叫顺序队列，用链表实现的叫链式队列(后续更新)
- 栈最大的特点就是先进后出，主要的两个操作是出栈和入栈，也是一个受限制的数据结构。
- 和队列一样，既可以用数组实现，也可以用链表实现。不管基于数组还是链表，入栈、出栈的时间复杂度都为 O(1)，队列也是如此。
当然还有其他的队列和栈，我这里只介绍到了基础的实现。这个硬骨头，还需慢慢啃。
4. 重点
如果有错误或者错别字，还请给我留言指出，谢谢。
网友评论