本系列博客习题来自《算法(第四版)》,算是本人的读书笔记,如果有人在读这本书的,欢迎大家多多交流。为了方便讨论,本人新建了一个微信群(算法交流),想要加入的,请添加我的微信号:zhujinhui207407 谢谢。另外,本人的个人博客 http://www.kyson.cn 也在不停的更新中,欢迎一起讨论
知识点
- 两个栈实现的队列
题目
1.4.27 两个栈实现的队列。用两个栈实现一个队列,使得每个队列操作所需要的堆栈操作均摊后为一个常数。提示:如果将所有元素压入栈再弹出,它们的顺序就被颠倒了。如果再次重复这个过程,它们的顺序则会复原。
1.4.27 Queue with two stacks. Implement a queue with two stacks so that each queue operation takes a constant amortized number of stack operations. Hint: If you push elements onto a stack and then pop them all, they appear in reverse order. If you repeat this process, they’re now back in order.
分析
这道题要写出来不难,但要符合“均摊后是一个常数”比较复杂。下面我们演示一下优化过程。
首先,我们使用两个栈,暂且命名为stack1和stack2,我们可以这么操作:stack1用于存储数据,stack2用于缓存。因此不难得出如下代码:
public class QueueWithTowStacks<T> {
private Stack<T> stack1 ;
private Stack<T> stack2 ;
public QueueWithTowStacks(){
stack1 = new Stack<T>();
stack2 = new Stack<T>();
}
public void enqueue(T item){
stack1.push(item);
}
public T dequeue(){
if (stack1.size() < 1 && stack2.size() < 1)
{
System.out.println("Queue is empty");
return null;
}
//把stack1清空
while (stack1.size() > 1){
T element = stack1.pop();
stack2.push(element);
}
T ele = stack1.pop();
//把stack2 清空
while (stack2.size() > 0){
T element = stack2.pop();
stack1.push(element);
}
return ele;
}
public static void main(String[] args){
QueueWithTowStacks gfg = new QueueWithTowStacks();
gfg.enqueue("我的");
gfg.enqueue("名字");
gfg.enqueue("叫");
gfg.enqueue("顶级程序员不穿女装");
gfg.enqueue("微博:https://m.weibo.cn/p/1005056186766482");
System.out.print(gfg.dequeue());
System.out.print(gfg.dequeue());
System.out.print(gfg.dequeue());
System.out.print(gfg.dequeue());
System.out.print(gfg.dequeue());
}
}
以上代码在这里可以找到:QueueWithTowStacks.java
关于栈(Stack)的实现,如果大家还有疑问的,可以查看我之前的博客:算法练习(26):Stack概念(1.3.1-1.3.2),里面给出了栈的具体实现。
我们可以发现,每次enqueue是常数级别的,但每次dequeue就比较复杂,需要遍历两个stack,假设Queue的总长度为N,那么每次dequeue需要线性级别的复杂度,所以跟题目的要求显然不符合,所以我们接着优化。
其实在做这一题之前,我们可以看到书中有类似的描述,关于均摊分析的:
书中关于均摊分析的描述中,说道了动态调整数组的平均次数为常数。所以我们可以把这个思想用到这道题中:
出队时,判断s2是否为空,如不为空,则直接弹出顶元素;如为空,则将s1的元素逐个“倒入”s2,把最后一个元素弹出并出队。这样一来避免了反复“倒”栈,仅在需要时才“倒”一次。
答案
public class QueueWithTwoStacksFaster<T> {
private Stack<T> stack1 ;
private Stack<T> stack2 ;
public QueueWithTwoStacksFaster(){
stack1 = new Stack<T>();
stack2 = new Stack<T>();
}
public void enqueue(T item){
stack1.push(item);
}
public T dequeue() throws Exception {
if (stack1.size() < 1 && stack2.size() < 1)
{
throw new Exception("Queue is empty");
}
T ele = null;
//Stack2为空,则将Stack1倒入Stack2
if (stack2.size() < 1){
while (stack1.size() > 1){
T element = stack1.pop();
stack2.push(element);
}
ele = stack1.pop();
}else{
ele = stack2.pop();
}
return ele;
}
public static void main(String[] args){
QueueWithTwoStacksFaster queueWithTwoStacksFaster = new QueueWithTwoStacksFaster();
queueWithTwoStacksFaster.enqueue("我的");
queueWithTwoStacksFaster.enqueue("名字");
queueWithTwoStacksFaster.enqueue("叫");
queueWithTwoStacksFaster.enqueue("顶级程序员不穿女装");
queueWithTwoStacksFaster.enqueue("微博:https://m.weibo.cn/p/1005056186766482");
try {
System.out.print(queueWithTwoStacksFaster.dequeue());
System.out.print(queueWithTwoStacksFaster.dequeue());
System.out.print(queueWithTwoStacksFaster.dequeue());
System.out.print(queueWithTwoStacksFaster.dequeue());
System.out.print(queueWithTwoStacksFaster.dequeue());
} catch (Exception e) {
e.printStackTrace();
}
}
}
代码索引
广告
我的首款个人开发的APP壁纸宝贝上线了,欢迎大家下载。